《数据压缩入门》简读 · 三味冰淇淋

简简单单对Colt McAnlis写的《数据压缩入门》前几章有关无损数据压缩部分进行一个简读。不得不说我看的这本，图灵程序设计丛书，中国工信出版集团与人民邮电出版社出版的这本真有点臭，翻译有点问题，还总能看到错误。

要讲怎么把数据压缩得更小，自然了解数据是什么，怎么样存在着。

信息在计算机中以二进制形式存在，这点不消多说。这篇文章中，作者默认读者有着一定的计算机基础，那么读者肯定知道生活中的十进制数是可以,且需要转化为二进制数存在计算机当中的。

但问题是，该怎么知道一个符号需要几个二进制位来表示呢？

五类压缩算法：变长编码（VLC），统计压缩，字典编码，上下文模型，多上下文模型信息熵：度量消息所携带信息内容的方法一个数的熵：该数对应的log2(n)的值为其的熵。用来表示该数所需要的最少二进制位。一个集合中的熵：K是系数，pi为p出现的概率，logpi为p的熵。但熵仅在乎概率而不在乎排序/上下文这样的语境，对这些信息加以利用，我们可以突破熵的限制。

“熵”这个概念在很多领域都有自己的应用，而在信息论里，香农给它的定义是这样的：

一个数的熵为该数对应的log2(n)的值。用来表示该数所需要的最少二进制位。

这是一个数字的熵，而对于一个数据集X的熵，定义是这样的：

此处有图，但还没搞好怎么插进来，反而把原来的hexo文件夹搞崩了，牛逼

看上去有点复杂？其实很简单，就是该数据集中，每个符号的出现概率，乘上这个概率以二为底的对数(lb)，求和后取相反数。

听上去还是晕乎乎的？没关系，知道有这个概念就ok了，更重要的是熵有什么意义。前面说一个数的熵是表示该数需要的最少二进制位，而一个数据集的熵就是该数据集中表示这组数据每个符号平均需要的二进制位数。打个比方 [A,B,B,C,C,C,D,D,D,D] 这样一个数据集，它的熵是-1.8455，意味着每个每个符号最少平均需要1.8455个二进制位来表示。

而在计算机当中肯定会和理论有所冲突，比如数字10的熵为3.321，计算机怎么能用3.321个位来表示一个数呢。所以便向上取整，用4个位来表示10。

并且假设我们在计算机中想存储一个10，则二进制形式则为1010，但计算机又怎么知道这是个”10”，而不是两个”2”（10）呢？

不论是像这样取整的问题，还是避免歧义的问题，都是理论和实际的差距。香农用熵告诉我们，一个数据集的二进制大小是有限制的，最小也小不过它的熵。

真的是这样吗？我们明知山有虎，偏向虎山行，就要试着去打破这个魔咒看看。

VLC(variable-length codes)，变长编码，的核心思想是根据符号在全文中出现的概率为其分配不同长度的编码。出现概率更大的符号就给予更短的编码，自然整体编码的长度就变小了。然后提供一个对应的编码表，就可以正确的逆向解码。

VLC进行编码时要注意不能产生歧义，故要使用编码的前缀性质，其中最著名最常见的方式便是霍夫曼编码。

根据概率模型去构建一个VLC时所用的工具称为统计编码，霍夫曼编码就是其中重要的一部分。但霍夫曼编码的局限性在于其最好情况出现在每个符号的出现概率都坐落在2的负整数次幂上，因为每次至少分配一个1或者0。

算数编码则提供了另一种解决思路，它将整个数据转换为一个很长的数值，根据每个字符出现的概率不断分段以编码。

形象一点来说，如果把整个数据视为一条绳子，每出现一个字符就根据其出现的概率减去固定长度的一段，剪到最后的一小段绳子就是最后编码完成的数据（这里的一小段在概念上是一个小数点后很多位的小数，计算机中会把小数点去掉，所以就成为了一个很长的数字）。而解码的过程就是把这条绳子剪掉的部分一截一截加上去。

现在有一个更好的统计编码算法，被称为非对称数字系统（ANS）。说起来可能有点复杂，扔两张PPT试着理解一下，核心思想是围绕着一张表来逐位输出，压缩的原理也是“出现可能性越小的符号列高越低，逐位输出的二进制位数就越多”。

此处有图，但还没搞好怎么插进来，反而把原来的hexo文件夹搞崩了，牛逼此处有图，但还没搞好怎么插进来，反而把原来的hexo文件夹搞崩了，牛逼

值得一提的是，当今最好用的两大压缩算法之一zstd算法，就使用了ANS。另 一个最好的压缩算法是lz4，在下文也有所介绍。二者在压缩速度与压缩率上各有千秋，但总的来说这二者都是从速度和压缩率上全面暴打了别的压缩算法。

没怎么看懂，但核心思想也是根据概率建表，经过一通神奇的操作后把表和编码一起输出，就能得到压缩数据。解码也是根据表进行逆向工程。

以上的内容都是基于“把整个数据看一遍，根据每个符号出现概率进行编码压缩”的思路上进行的，但实际上会出现“数据源源不断的流入，无法直接将其扫一遍”的场景。进一步的，符号在数据流中不同的部分出现的概率很大可能是不同的，一个符号可能在前一部分很少出现，但过了一会开始频繁出现，这种现象与计算机的局部性原理很像，书中被作者称为局部偏态 。

在这种情况下，若仍希望通过统计编码进行压缩，则所用的方法被称为自适应统计编码。

自适应VLC编码的思想与VLC基本相同，只不过要边读符号，边动态的计算该符号的出现概率，并动态的为其编码。如读入并输出了一个“B”后，发现“B”的出现概率超过了“A”，则将二者的编码进行对换。而解码时从头演变一次就可以了。

在自适应编码过程中也有可以额外操作的空间，比如编码过程中在需要的时候可以设置一个 RESET 重置标记来表示编码表被重置了，要从零开始建表，以此防止输出流的熵变得失控。

自适应算数编码和自适应VLC编码的思想基本是一样的，就不多说了。

以上都是“针对单个符号进行编码”的内容，但事实上很多符号经常组合在一起出现，比如英语中的单词。那么我们能不能利用这个性质呢？于是有了 字典转换。

大名鼎鼎的LZ算法就属于字典转换的范畴，介绍起来可能有点复杂，试着简述一下：

首先设置一个滑动窗口，并把这个窗口分为左右两部分。左边时已经处理过的搜索缓冲区，右边是待处理的先行缓冲区。这个窗口就在整个数据流中从左往右（从头到尾）滑动，然后有以下处理：

1.对于先行缓冲区的第一个字符，假设这里是字母X，从搜索缓冲区尾部开始寻找其第一个匹配。

2.若没找到，则输出。若找到匹配，再去看先行缓冲区的下一个字符，看刚刚匹配的位置下一个字符是否依然匹配。如果不匹配了就再往前找，直到搜索到搜索缓冲区头部也没找到为止。如果依然匹配就再往下一个字符，重复到不匹配为止。也就是寻找最长的字符串匹配。

3.寻找最长字符串匹配完成后，输出找到匹配的位置以及匹配的字符串长度。

简单画个图：

TOBEORNO | TOBEAAA

根据上述流程，匹配的最长字符串应该是“TOBE”所以会输出,意味向前数8个字符后四个字符为匹配项。然后移动窗口到这个位置：

TOBEORNOTOBE | AAA

这样的输出肉眼可见比原数据小得多，但更妙的是，这样的输出还可以通过VLC或别的方法进行进一步压缩。

另一种基于语境、上下文进行压缩的方法叫做 上下文数据转换。

我曾经想象的一种压缩方式看书时发现实际存在，叫做RLE。一言以蔽之就是：

AAAAABBBCCCC -> (A,5)(B,3)(C,4)

很好理解吧，但其中有消除歧义的问题需要解决，就不赘述了。

增量编码也好理解：

(4,5,6,7,8,8,8) ->(4,1,1,1,1,0,0,0)

通过加上前面一位来获得真实值。但这样简单的编码方式很多时候并不好用，于是出现了XOR增量编码，参照系增量编码等。更重要的是，经过这样转换的数据可以进一步进行压缩。

MTF（前移编码）和计算机里的局部性原理很像，认为出现过的字符很可能再次出现。所以维护一个有向列表，每出现一个字符就从列表中找到他的索引值并输出，再将这个字符移到列表头。

一个很有趣的算法，BWT，可以找出原数据的一种排列，让相同的符号更加靠近，这样就可以更好的进行压缩。这一行为通常被称为字典序排列。BWT肯定是可逆的（不然不就没有意义了吗），最常见的用法是将数据使用BWT转换后再使用MTF压缩（而不是RLE或LZ，这是有原因的！）。

LZ，RLE，增量编码，BMT都建立在一个假设上：数据的最佳编码方式与它的相邻性有关。

虽然有着很玄学的数学定义，但马尔科夫链在实际层面上也是通过字符出现频率以推测概率，进而动态分配合适的码字。

比如通过对数据建模，发现如果前面是“hell”，那么下一个字符是“e”的概率高达百分之99，那么就可以给它分配最短的码字。

书中对马尔可夫链的评价非常高，原句是“如果不考虑一切其它因素，如时间成本等，那么最优的数据压缩就是个已解决的问题。”

但实际使用太复杂了，就简单的考虑hell后面接o的情况，就需要考虑到26的四次方种情况（每个字母后面都可能接26个字母中的其中一个，并且实际情况中还有各种符号，更加复杂）。所以实际中会使用更简单的方法，如PPM（部分匹配预测算法），或PAQ（上下文混合算法）。

统计编码：VLC编码，算数编码，ANS，自适应统计编码（VLC,算数）字典转换：LZ上下文数据转换：行程编码（RLE），增量编码，前移编码（MTF），伯罗斯-惠勒变换（BWT）马尔科夫链

操作类型，复杂度，应用场景

时间复杂度：VLC,算数编码，ANS ： O(n)自适应统计编码： O(n) ，实际上耗时可能比普通的统计编码长，因为每读入一个符号就要计算然后编码一次。LZ：O(n)RLE，增量编码，MTF：O(n)

静态VLC，算术编码：少量数据，复杂度更低自适应…：大量数据或多媒体文件，以及更好的压缩率和运行时性能。字典转换：位于“单词”的背景下的场景（但实际上LZ4在各种场景都基本表现很不错对吧）增量编码：多用于数值型的数据。RLE：适用于大量字符连续重复出现的场景。MFT：相同符号集中的场景

原文作者：Dath Chou

原文链接：https://harlequinicecream.com/2023/02/27/%E3%80%8A%E6%95%B0%E6%8D%AE%E5%8E%8B%E7%BC%A9%E5%85%A5%E9%97%A8%E3%80%8B%E7%AE%80%E8%AF%BB/

发表日期：February 27th 2023, 9:08:55 pm

更新日期：February 27th 2023, 11:46:46 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可，图转侵删致歉。