来自：http://www.cppblog.com/windcsn/archive/2006/01/06/2476.html || http://blog.csdn.net/windcsn/archive/2006/01/06/572389.aspx 3. Rice 对于由大word（例如：16或32位）组成的数据和教低的数据值，Rice编码能够获得较好的压缩比。音频和高动态变化的图像都是这种类型的数据，它们被某种预言预处理过（例如delta相邻的采样）。 尽管哈夫曼编码处理这种数据是最优的，却由于几个原因而不适合处理这种数据（例如：32位大小要求16GB的柱状图缓冲区来进行哈夫曼树编码）。因此一个比较动态的方式更适合由大word组成的数据。 3.1. 原理 Rice编码背后的基本思想是尽可能的用较少的位来存储多个字（正像使用哈夫曼编码一样）。实际上，有人可能想到Rice是静态的哈夫曼编码（例如，编码不是由实际数据内容的统计信息决定，而是由小的值比高的值常见的假定决定）。 编码非常简单：将值X用X个‘1’位之后跟一个0位来表示。 3.2. 实现 在基本压缩库针对Rice做了许多优化： 1． 每个字最没有意义的位被存储为k和最有意义的N-k位用Rice编码。K作为先前流中少许采样的位平均数。这是通常最好使用Rice编码的方法，隐藏噪音且对于动态变化的范围并不导致非常长的Rice编码。 2． 如果rice编码比固定的开端长，T，一个可选的编码：输出T个‘1’位，紧跟（log2(X-T)）个‘1’和一个‘0’位，接着是X-T（最没有意义的(log2(X-T))-1位）。这对于大值来说都是比较高效的代码并且阻止可笑的长Rice编码（最坏的情况，对于一个32位word单个Rice编码可能变成232位或512MB）。 如果开端是4，下面是结果编码表： X bin Rice Thresholded Rice 0 00000 0 0 1 00001 10 10 2 00010 110 110 3 00011 1110 1110 4 00100 11110 11110 5 00101 111110 111110 6 00110 1111110 11111100 +1 7 00111 11111110 11111101 8 01000 111111110 1111111000 +1 9 01001 1111111110 1111111001 10 01010 11111111110 1111111010 -1 11 01011 111111111110 1111111011 -2 12 01100 1111111111110 111111110000 13 01101 11111111111110 111111110001 -1 14 01110 111111111111110 111111110010 -2 15 01111 1111111111111110 111111110011 -3 16 10000 11111111111111110 111111110100 -4 17 10001 111111111111111110 111111110101 -5 18 10010 1111111111111111110 111111110110 -6 19 10011 11111111111111111110 111111110111 -7 20 10100 111111111111111111110 11111111100000 -5 就像你看到的一样，在这个实现中使用threshold方法仅仅两个编码导致一个最坏的情况；剩下的编码产生比标准Rice编码还要短的编码。 3． 最坏的情况，输出。 4. Lempel-Ziv (LZ77) Lempel-Ziv压缩模式有许多不同的变量。基本压缩库有清晰的LZ77算法的实现（Lempel-Ziv，1977），执行的很好，源代码也非常容易理解。 LZ编码器能用来通用目标的压缩，特别对于文本执行的很好。它也在RLE和哈夫曼编码器（RLE，LZ，哈夫曼）中使用来大多数情况下获得更多的压缩。 4.1. 原理 在LZ压缩算法的背后是使用RLE算法用先前出现的相同字节序列的引用来替代。 简单的讲，LZ算法被认为是字符串匹配的算法。例如：在一段文本中某字符串经常出现，并且可以通过前面文本中出现的字符串指针来表示。当然这个想法的前提是指针应该比字符串本身要短。 例如，在上一段短语“字符串”经常出现，可以将除第一个字符串之外的所有用第一个字符串引用来表示从而节省一些空间。 一个字符串引用通过下面的方式来表示： 1． 唯一的标记 2． 偏移数量 3． 字符串长度 由编码的模式决定引用是一个固定的或变动的长度。后面的情况经常是首选，因为它允许编码器用引用的大小来交换字符串的大小（例如，如果字符串相当长，增加引用的长度可能是值得的）。 4.2. 实现 使用LZ77的一个问题是由于算法需要字符串匹配，对于每个输入流的单个字节，每个流中此字节前面的哪个字节都必须被作为字符串的开始从而尽可能的进行字符串匹配，这意味着算法非常慢。 另一个问题是为了最优化压缩而调整字符串引用的表示形式并不容易。例如，必须决定是否所有的引用和非压缩字节应该在压缩流中的字节边界发生。 基本压缩库使用一个清晰的实现来保证所有的符号和引用是字节对齐的，因此牺牲了压缩比率，并且字符串匹配程序并不是最优化的（没有缓存、历史缓冲区或提高速度的小技巧），这意味着程序非常慢。 另一方面，解压缩程序非常简单。 一个提高LZ77速度的试验已经进行了，这个试验中使用数组索引来加速字符串匹配的过程。然而，它还是比通常的压缩程序慢。
评论