行程长度编码(游程编码)
时间:2013-3-9 作者:smarteng 分类: 经典算法
游程编码(RLE,run-length encoding),又译行程长度编码,又称变动长度编码法(run coding),在控制论中对于二值图像而言是一种编码方法,对连续的黑、白像素数(游程)以不同的码字进行编码。游程编码是一种简单的非破坏性资料压缩法,其好处是加压缩和解压缩都非常快。其方法是计算连续出现的资料长度压缩之,其缺点是对于不重复的资料反而加大容量。
例如有一张图片,以W表示白色,B表示黑色:
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW
使用这个压缩法便可得到
12W1B12W3B24W1B14W
更先进的算法如DEFLATE都是基于将重复出现的资料“压缩”的想法。
常见的游程编码格式包括TGA,Packbits,PCX以及ILBM。
游程长度编码是一种无损数据压缩,非常适合基于调色板的图标图像。但是它并不适用于连续色调图像的压缩,例如日常生活中的照片;JPEG格式是一个反例,JPEG在对图像进行转换和离散化后有效地使用了游程长度压缩。
游程长度编码还用于传真机(并和其他技巧一起组成了修改过的huffman编码)。相对而言,游程长度编码是比较有效的,因为传真的文档主要是黑白的(二值文档)。