比特流中最简单的冗余形式是一串重复的比特,利用这种冗余来压缩数据的经典方法是游程编码。
例如有一串比特流:0000000000000001111111000000011111111111,该比特流中有15个0,然后是7个1,然后是7个0,然后是11个1。因为0和1总是交替出现的,我们只要表示出游程长度即可。上面的比特流可用游程编码压缩为:1111011101111011(15=1111,7=0111,7=0111,11=1011)。
为了有效地实现该压缩方法,需要回答下面三个问题:
这些问题的回答是:
游程编码被广泛使用于保存图像和扫描文档。不适用于比特流不含较长游程的情况(比如典型的英文文档)。
游程编码的实现非常简单:
压缩操作:
读取一个比特,如果它和上个比特值不同,保存(写入)当前计数器的值并将计数器清零;如果它和上个比特值相同,分两种情况:计数器还未到最大值,则直接增加计数器的值即可;如果计数器已经为最大值,则写入计数器的值并再写入一个0,然后计数器归0.
解压操作:
读取一个游程的长度,将当前比特按照长度复制并输出,转换比特值并继续,直到结束。