Perl 一句正则表达式 实现RLE压缩算法的 压缩解压

RLE 可能是最简单的压缩算法, 但是应该却非常广泛, 尤其是作为打印机的语言, 它的解压不会给CPU带来任何额外的负担, 也不需要辅助的存储空间. 其基本思想是用数字描述重复的字节.
#0123456789
 AAAAAAAAAABCD
RLE存储上面这个串的做法是
10 个 A + 3个字节的 BCD. 因为BCD没有重复, 却需要一个额外的字节来描述它的长度, 所以此时反而浪费了空间.
一个典型的实现是这样的:
F7 41 02 42 43 44
其中 F7 是一个"负数", 如果某个字节大于127, 则它表示紧邻着它的字节需要重复, 重复的字节数是 256 - 0xF7 + 1 = 10, 这里把0xF7看作无符号数.
接下来的02, 因为小于等于127, 所以它表示接下来的 2 + 1 = 3个字节需要原封不动地COPY到解压串中.

C语言的典型实现无论是解压还是压缩都要大约20-30行左右.

下面是应急用PERL的实现:
sub rle_uncompress
{
  my $ref = shift;
  my $i = 0, $len = length($$ref);
  my $data = "";
  while ($i < $len)
  {
    my $b = substr($$ref, $i, 1);
    my $rep = ord($b) ;
    if ( $rep > 127 ) ##repeated data
    {
      $data .= ( substr($$ref, $i+1 , 1 ) x (256-$rep+1) );
      $i += 2;
    }
    else
    {
      $data .= substr($$ref, $i + 1, $rep + 1);
      $i += ($rep + 2); #data length= $rep + 1. repeat byte: 1
    }
  }
  $$ref = $data;
}

这个实现效率一般, 因为 $data .= 操作会引起大量的内存重新分配.

由于PERL支持扩展的正则表达式, 可以根据前面匹配的内容决定后面要使用的正则式, 还可以动态生成被替换的串.

下面是一个正则表达式搞定 RLE 解压, 当然, 它比较复杂, 看起来也不象只是一条语句. 但它的确是, 这样写是为了可读性.
==================================
my $L = 0;
my $data = "\xf7A\x02BCD";
#根据前面的RLE算法描述, 应该解压后得到 AAAAAAAAAABCD

  $data =~ s/
  (
    \G\C
  )
  ((??{$L=ord($1);($L<128)?'\C{0,'.($L+1).'}':'.';}))
  /
  {
  # print "\$L=$L, \$2=" . ord($2), "\n";
  ($L>127)
    ? $2 x (257-$L)
    : $2;
  }
  /gosex;

print "$data\n";
==================================
我只能说自己搞了半天的作品实在是酷, 写到最后也竟然发现自己给这个正则表达式指定的modifier 正好是go sex 连在一起.

对它的测试我采用了打印机生成的真实PRT文件, 也就是真正要送给打印机的那种字节流, 然后把它转换为一个TIFF文件.  Wow!

把转出来的图片也上传一下.