压缩算法笔记

Know how to solve every problem that has been solved.

What I cannot create I do not understand.

–Richard P. Feynman

上个月因为公司内部的比赛，被迫短时间内了解了一些压缩算法，还动手实现了一些，比如lz77，deflate，bwt，bcm等，不实践不知道，一写代码就发现有些东西你以为你懂了实际上你没懂，加上最近看了已故物理学大师理查德费曼的一系列视频，其中一个细节让我印象深刻，他去世后大家在他办公室的黑板的左上角（这样就可以防止不小心被擦掉）发现他一直保留着上面的两句话。

理查德费曼很小的时候就受到他父亲的教育，明白了知道和理解是两个概念，所以他一直能保持好奇的心态去思考每个问题。
这两句话的本质是一样的，也就是——只有自己能做出来才算真正理解了，要做到这一点就需要知道每个问题背后是如何真正被解决的，而不是只知道个结论，所以理解一个概念的最高境界就是你能教会别人这个概念。

有感于此，特撰此文记录一下这段时间研究压缩算法的过程。

首先介绍一个很好的关于压缩算法的综述性网站Data Compression Explained，这里从最简单的压缩算法一直讲到了state-of-art的压缩算法，其中Compression is an Artificial Intelligence Problem这一小节很值得一读。

其次是一个实现了超多压缩算法的开源库，kanzi-go，这个原版应该是用java实现的，不知道为啥作者又用go全部重写了一遍。
这个库最大的好处就是，你可以任意组合前端的transform和后端的entropy算法，来测试不同的组合对你文件的压缩效果。

deflate=lz77+huffman coding

这个应该是最简单的压缩算法了，很多语言都内置了它的实现，因为他对于文本而言是十分快速有效的，对于我们比赛中用到的数据文件deflate大致能有0.37的压缩率。

lz77算法解释起来非常简单，就是用已经编码部分作为“字典”来继续编码后续的内容。

用mississippi举个例子，假设我们已经编码了miss，这个时候我们要继续往后面编码的时候可以用二元组(jumpBack, matchLen)来尝试减少重复从而压缩数据，其中jumpBack表示需要跳回去多少个字符，matchLen表示匹配多少个字符。

比如此时输出的二元组就可以是(3, 3)，因为我们可以跳回3个字符匹配长度为3的iss，当然也可以是(3, 4)，因为我们可以跳回3个字符匹配长度为4的issi，注意这里的前一个issi的最后一个i和当前新匹配的issi的第一个i实际上是同一个i，这是被允许的。
对于lz77算法而言，目的就是尽可能的让matchLen大，所以这里正确的输出是(3, 4)。

当然考虑到一般不太可能有太长的连续匹配，这里的maxMatchLen可以只设置到256的长度，也就是占用一个byte，同时maxJumpBack也可以根据需要来设置，假设我们用2个byte来存储maxJumpBack，也就是最多在2^16位范围内查找最大匹配。

这样一来，我们用来3个byte去表示一个二元组，那么很显然如果我们表达的matchLen<=3那么这种替换是无效的，不如使用原始长度的字符。所以一般在实现的时候都会直接去找>=4的长度的匹配。

另一方面如果要在2^16位范围内查找最大匹配，普通的字符串匹配效率肯定是很低的，所以我们可以缓存连续4个字符的hash值最近出现的位置，形成一个链表，这样每次要查找最大匹配的时候，先算当前的4字符hash值，然后直接找刚刚维护的链表看看有没有，这样可以大大提升查找效率。

huffman coding这里就不多介绍了，大概思路就是统计词频，然后按词频的降序给予相应的编码长度，保证高频的词语获得较低的编码长度。

OK！我其实看到这里当时就开始写代码了，因为当时的我认为自己已经理解了两个算法，但是当我把第一版代码写完的时候发现，无论如何我都无法获得和golang标准库中实现相同压缩率的结果，而是比0.37要高很多。

这里主要的问题就在于我们混编jumpBack matchLen literal（普通字符）输入到huffman编码中的时候，matchlen和jumpBack会干扰literal的词频统计，同时matchlen和jumpBack本身的词频统计特点本身也和literal不一样。

matchLen的特点是长度短的出现特别多，越长的长度出现的会很少。比如长度为4,5,6,7的matchLen会比长度为8,9的多很多。

而jumpBack又呈现出很大的随机性，因为2^16位范围实在太大了，huffman对于平均词频的文本其实是没啥优势的。

我由于没有直接看deflate的RFC，等我我真正找到这些问题的解决方案，是在对比标准库中的实现——debug调试比较它的matchlen和jumpBack的编码结果之后，这就浪费了很多时间。

其实在deflate的RFC很明确的写到，对于matchlen和jumpBack的编码可以使用一种变长的编码手段，比如将matchLen的范围4-258映射为0-31，长度为4,5,6,7出现的最多，可以分别占据一个值比如映射为0,1,2,3，而8,9可以统一映射为4，再用1个extrabit来表示到底是8还是9。

这么一通类似于预先设计的按频率编码的操作之后，我们在大部分情况下都不需要完整的8个bit来表示matchLen。对于范围更大的jumpBack也是同理，压缩到0-255的范围，再结合extrabit。

此外为了避免huffman coding时matchlen和jumpBack干扰literal的词频统计的问题，我们可以把他们分开用huffman编码。具体操作上是将0-255分配给ascii码的literal，256分配给eof表示文件结束，257-288分配给matchLen，这样对0-288进行词频统计。

解码时候如果发现是257-288，先减去256，再根据具体是多少，先读取extrabit恢复出真正的matchLen，再往后读取jumpBack的编码，这样就恢复了二元组(jumpBack, matchLen)，然后再根据二元组继续解码。

通过这样一通操作，终于能达到和golang标准库中实现相同压缩率了。

当然deflate还有其实进一步减少压缩大小的骚操作，比如由于一般的压缩过程是一个block一个block进行的，而每个block都需要有自己的huffman coding的字典写在前面，这累积起来也有一定的开销，我们可以通过一个叫做正则huffman coding的方案，这样词典部分就可以进一步减少体积。

算术编码

很显然deflate这种古董级别的压缩算法是无法和别人竞争压缩率的，所以我们需要研究更先进的压缩算法。

一般而言，压缩算法根据原理可以分为transform和entropy两大类。一般市面上的压缩算法都会用多个transform阶段最后加上一个entropy阶段组成，可以使用前面提到的kanzi-go库自己搭配一下看看效果。

lz77就是一种transform，其他包括字典、BWT等都是transform。

而huffman coding就是基于entropy，也就是信息熵的压缩算法。huffman算法的问题在于，他无法达到信息论上理论最优。

比如我们有一段bit流streamA，其中每个位置上0的概率是0.99；另一段bit流streamB，其中每个位置上的0的概率是0.51。很明显我们要用huffman coding来表示的话，最终构造的字典是一样的。

站在信息论的角度，streamA明显包含了更少的信息，应该更容易被压缩，试想一下极端情况0出现的概率是1，那么其实我们可以取得无限的压缩率，因为我们只需要输出个长度数据就行了。

而算术编码就很好的解决了以上问题，他的方法就是把输入映射为一个0-1之间的子区间，其中每编码一位，就按照当前bit的值，按照该值的概率缩小当前的区间，直到所有bit编码完，我们会得到一个很小的区间，事实上我们可以输出这个区间上的任意一个数字来作为最后的编码结果。

最终解码时逆向这个过程，就可以一位一位还原输入。

由于算术编码可以达到理论上的最佳压缩率，所以最先进的压缩算法在最后的entropy阶段几乎都是算术编码。

state-of-art的压缩算法

虽然算术编码本身不复杂，但是如何更好的估计概率却是一个十分复杂的事情，理论上来说，如果你能根据已有的内容更准确地估计后续内容出现的概率那么就可以达到更高的压缩率，同时动态调整概率可以在在线处理压缩时效果也更好。

这就是modeling的作用了。而对于不同的输入源，也有不同的modeling可以选择，比如图像就需要二维的model。

最新的压缩算法往往是运用了更复杂modeling的方法，包括一些机器学习的model（比如PAQ8之后），甚至是多种方案的mixing modeling。但这就是另一个复杂的话题了，我也没有足够的时间去理解PAQ算法中全部的model，最终我们的选择的是Burrows-Wheelter Transform变换（PS这个变换也是理解很简单，自己写起来就是很复杂的典型）加上只考虑order0、order1、前两个字符是否相等的一个mix model下的算数编码，感兴趣的话可以看那个网站，有一些简单的介绍。

最后吐槽下，压缩这块真的资料很少，找来找去最后都到一个俄罗斯人的论坛，里面有各路大神发布自己的代码，不得不感叹毛子的数学基础就是强。