Rice编码是一种压缩编码,它的基本思想类似于哈夫曼编码,即尽可能的用较少的位来存储多个字。
简介
Rice编码背后的基本思想是尽可能的用较少的位来存储多个字(正像使用哈夫曼编码一样)。实际上,有人可能想到Rice是静态的哈夫曼编码(例如,编码不是由实际数据内容的统计信息决定,而是由小的值比高的值常见的假定决定)。
编码非常简单:将值X用X个‘1’位之后跟一个0位来表示。
对于由大word(例如:16或32位)组成的数据和教低的数据值,Rice编码能够获得较好的压缩比。音频和高动态变化的图像都是这种类型的数据,它们被某种语言预处理过(例如delta相邻的采样)。
尽管哈夫曼编码处理这种数据是最优的,却由于几个原因而不适合处理这种数据(例如:32位大小要求16GB的柱状图缓冲区来进行哈夫曼树编码)。因此一个比较动态的方式更适合由大word组成的数据。
实现
在基本压缩库针对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,下面是结果编码表:
就像你看到的一样,在这个实现中使用threshold方法仅仅两个编码导致一个最坏的情况;剩下的编码产生比标准Rice编码还要短的编码。