数据压缩之ROLZ字典编码

RichSelian

数据压缩之ROLZ字典编码

<div class="postbody"><div id="cnblogs_post_body">　　在字典编码中，最常用的恐怕要算LZ77编码了。LZ77的思想很简单，就是用一个<offset, length>元组来表示当前位置的字节串在前offset个字节中出现过。正是由于这个简单的思想，所有基于LZ77实现的实用算法都有着不错的解压速度。经典的使用LZ77编码的压缩算法有zip/gz的deflate算法，7z的lzma算法等。
　　在对LZ77算法研究中，我们也发现算法中的一些不足之处，LZ77最明显的不足是offset值的过度零散导致对<offset, length>元组的后续处理效果不好。例如处理一个16MB的数据块，一个<offset, length>中offset的取值就有16777216种之多，虽然可以对offset进行分段处理，但还是或多或少会影响到压缩率的提升。
　　于是我们有了ROLZ算法，ROLZ全称是Reduced Offset Lempel Ziv，即减少了offset的LZ编码。在ROLZ中，重复串出现的位置不再是用相对当前的偏移量offset，而是用一个表项编号index来表示。
　　在详细介绍ROLZ算法之前，我们先介绍一个压缩算法中常用的概念——上下文（context），上下文就是当前编码位置之前的内容，在实际应用中，我们只取当前编码位置前k个字符做为上下文，称为k阶上下文。上下文是提高压缩率的一个重要工具，例如字符串"queen"，如果用一般的统计模型来处理，由于英语中字母"u"出现频率不高，我们可能会给"u"分配一个长的前缀编码。但考虑一阶上下文"q"，在英语中"q"后面出现"u"的概率非常高，我们就会给"u"分配相对较短的前缀编码，从而利用上下文提高了编码效率。
　　在编码中，我们总会保存每个上下文的一些信息，但是当上下文阶数k >= 3时，上下文的个数会急剧升高，当k=4时就已经有256^4 = 4GB的上下文各数。所以对于较长的上下文，我们往往取一个对前k个字符的一个Hash值作为上下文，这样的结果是可能几个完全不同的上下文会占用相同的存储空间，导致上下文的预测准确率有所降低，但这种做法满足了程序对内存的要求，实际中也被广泛使用。
　　现在进入正题，在ROLZ算法中，我们会建立一张二维表rolz_table[context][index]，在处理完每个位置后，我们将这个位置存入对应上下文的桶中，以下就字符串"construct- destruct"举个例子（考虑一阶上下文，假设当前编码到位置12）：
<div class="cnblogs_code">0 1 2 3 4 5 6 7 8 9 10 11 $ 13 14 15 16 17c o n s t r u c t - d  e  s t  r  u  c  ttable["c"] = {8, 1}table["o"] = {2}table["n"] = {3}table["s"] = {4}table["t"] = {9, 5}table["r"] = {6}table["u"] = {7}table["-"] = {10}table["d"] = {11}