数据压缩----游程编码

比特流中最简单的冗余形式是一串重复的比特，利用这种冗余来压缩数据的经典方法是游程编码。

例如有一串比特流：0000000000000001111111000000011111111111，该比特流中有15个0，然后是7个1，然后是7个0，然后是11个1。因为0和1总是交替出现的，我们只要表示出游程长度即可。上面的比特流可用游程编码压缩为：1111011101111011（15=1111，7=0111，7=0111，11=1011）。

为了有效地实现该压缩方法，需要回答下面三个问题：

1. 应该用多少比特记录游程长度？
2. 某个游程长度超过了能够记录的最大长度怎么办？
3. 当游程长度所需的比特数小于记录长度的比特数怎么办？

这些问题的回答是：

1. 游程长度应该在0-255之间，使用8位编码；
2. 在需要的情况下使用长度为0的游程来保证所有游程的长度小于256；
3. 较小的游程也会编码，虽然这样可能使输出变得更长。

游程编码被广泛使用于保存图像和扫描文档。不适用于比特流不含较长游程的情况（比如典型的英文文档）。

游程编码的实现非常简单：

压缩操作：

读取一个比特，如果它和上个比特值不同，保存（写入）当前计数器的值并将计数器清零；如果它和上个比特值相同，分两种情况：计数器还未到最大值，则直接增加计数器的值即可；如果计数器已经为最大值，则写入计数器的值并再写入一个0，然后计数器归0.

解压操作：

读取一个游程的长度，将当前比特按照长度复制并输出，转换比特值并继续，直到结束。