博文
几种压缩算法原理介绍2(2006-02-04 13:55:00)
摘要：来自：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
1......
几种压缩算法原理介绍1(2006-02-04 13:54:00)
摘要：来自：http://www.cppblog.com/windcsn/archive/2006/01/06/2476.html || http://blog.csdn.net/windcsn/archive/2006/01/06/572389.aspx
RLE
RLE又叫Run Length Encoding，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如，JPEG就使用它）。
1.1. 原理
图2.1显示了一个如何使用RLE算法来对一个数据流编码的例子，其中出现六次的符号‘93’已经用3个字节来代替：一个标记字节（‘0’在本例中）重复的次数（‘6’）和符号本身（‘93’）。
RLE解码器遇到符号‘0’的时候，它表明后面的两个字节决定了需要输出哪个符号以及输出多少次。
1.2. 实现
RLE可以使用很多不同的方法。基本压缩库中详细实现的方式是非常有效的一个。一个特殊的标记字节用来指示重复节的开始，而不是对于重复非重复节都coding run。
因此非重复节可以有任意长度而不被控制字节打断，除非指定的标记字节出现在非重复节（顶多以两个字节来编码）的稀有情况下。为了最优化效率，标记字节应该是输入流中最少出现的符号（或许就不存在）。
重复runs能够在32768字节的时候运转。少于129字节的要求3个字节编码（标记+次数+符号），而大雨128字节要求四个字节（标记+次数的高4位|0x80+次数的低4位）。这是通常所有采用的压缩的做法，并且也是相比较三个字节固定编码（允许使用3个字节来编码256个字节）而言非常少见的有损压缩率的方法。
在这种模式下，最坏的压缩结果是：
输出大小=257/256*输入大小+1
2. 哈夫曼
哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多为来表示。
哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。
2.1. 原理
我不打算探究哈夫曼编码的所有实际的细节，但基本的原理是为每个符号找到新的二进制表示，从......