游程编码

运行长度编码(英语:run-length encoding,缩写RLE),又称行程长度编码变动长度编码法,是一种与资料性质无关的无损数据压缩技术,基于“使用变动长度的码来取代连续重复出现的原始资料”来实现压缩。

说明

举例来说,一组资料串"AAAABBBCCDEEEE",由4个A、3个B、2个C、1个D、4个E组成,经过变动长度编码法可将资料压缩为4A3B2C1D4E(由14个单位转成10个单位)。

简言之,其优点在于将重复性高的资料量压缩成小单位;然而,其缺点在于─若该资料出现频率不高,可能导致压缩结果资料量比原始资料大,例如:原始资料"ABCDE",压缩结果为"1A1B1C1D1E"(由5个单位转成10个单位)。

整数(出现次数)表示法

整数变动长度表示法

整数固定长度表示法

4位表示法

顾名思义,利用4个比特来存储整数,以符号C表示整数值。其可表现的最大整数值为15,因此,若资料重复出现次数超过15,便以“分段”方式处理。

假设某资料出现N次,则可以将其分成(N/15)+1段落来处理,其中N/15的值为无条件舍去。例如连续出现33个A:

原始资料:

AAAAAAAAAAAAAAA AAAAAAAAAAAAAAA AAA

压缩结果:

     15A          15A         3A

内部存储码:

1111 01000001 1111 01000001 0011 01000001

15   A    15    A     3     A

8位表示法

同4位表示法的概念,其能表示最大整数为255。假设某资料出现N次,则可以将其分成(N/255)+1段落来处理,其中N/255的值为无条件舍去。

压缩策略

压缩

先使用一个暂存函数Q读取第一个资料,接着将下一个资料与Q值比,若资料相同,则计数器加1;若资料不同,则将计数器存的数值以及Q值输出,再初始计数器为,Q值改为下一个资料。以此类推,完成资料压缩。

以下为简易的算法:

input:AAABCCBCCCCAA
for i=1:size (input)
 if(Q = input(i))
    計數器+1
 else
   output的前項=計數器的值, output的下一項=Q值,
   Q換成input(i),計數器值換成0
 end
end

解压缩

其方法为逐一读取整数(以C表示)与资料(以B表示),将C与B的二进制码分别转成十进制整数以及原始资料符号,最后输出共C次资料B,即完成一次资料解压缩;接着重复上述步骤,完成所有资料输出。

应用

  • 大量白色或黑色的区域单色影像图
  • 电脑生成的同色区块的彩色图像(如建筑绘图纸)
  • TIFF文件
  • PDF文件

参考资料

  1. 资料压缩原理与实务。张真诚,蔡文辉著。松岗电脑图书资料股份有限公司。1994/4/12。
  2. Bassiouni, M.A., "Data Compression in Scientific and Statistical Databases" , IEEE Trans. Software Eng., Vol. SE-11, No. 10, Oct.1985, pp. 1047-1058.
  3. Reghbati, H.K. "An Overview of Data Compression Techniques", Computer, Vol. 14, No. 4, May 1981, pp. 71-76

参见