行程长度编码(游程编码)

时间:2013-3-9     作者:smarteng     分类: 经典算法


游程编码RLErun-length encoding),又译行程长度编码,又称变动长度编码法run coding),在控制论中对于二值图像而言是一种编码方法,对连续的黑、白像素数(游程)以不同的码字进行编码。游程编码是一种简单的非破坏性资料压缩法,其好处是加压缩和解压缩都非常快。其方法是计算连续出现的资料长度压缩之,其缺点是对于不重复的资料反而加大容量。

例如有一张图片,以W表示白色,B表示黑色:

 WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

使用这个压缩法便可得到

 12W1B12W3B24W1B14W


更先进的算法如DEFLATE都是基于将重复出现的资料“压缩”的想法。

常见的游程编码格式包括TGAPackbitsPCX以及ILBM

游程长度编码是一种无损数据压缩,非常适合基于调色板的图标图像。但是它并不适用于连续色调图像的压缩,例如日常生活中的照片;JPEG格式是一个反例,JPEG在对图像进行转换和离散化后有效地使用了游程长度压缩。

游程长度编码还用于传真机(并和其他技巧一起组成了修改过的huffman编码)。相对而言,游程长度编码是比较有效的,因为传真的文档主要是黑白的(二值文档)。