游程编码

运行长度编码（英语：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

参见