无损压缩算法原理

压缩一般分为两个步骤，建模和编码。一个完美的模型可以描述数据流是如何产生的，相当于一个python类里面的generator。只需要这个generator就可以产生所有数据，从而大大降低需要传输的数据。例如 如果需要传输的数据序列是1 1 2 3 5 … 6765 ，那么可以用一个“斐波那契数”来精准表达这个传输的序列。在实际应用中，很难得到这样的精准模型，因此一般都是近似的为数据构建一个数学模型。例如英文文章可以认为是一个字典模型，我们只要有字典以及对应的编号，就能还原出信息；在编码步骤中，信息将会被映射到一个编码中。可以认为是一种字典的映射，为了保证解码时信息的还原，必须要求解码时的信息映射是一一对应的。前缀码是一种比较常用的编码方式。已经证明 [McEliece 1977]，对于任何可以唯一解码的非前缀代码，都可以找到具有相同码字长度的前缀代码。

需要把无损压缩算法与我们平常使用的无损压缩格式区分开，因为无损压缩工具一般都是多种压缩算法重叠使用的，而不是单一的压缩算法。只是不同的工具侧重点不一样，一般压缩算法可以被描述成三元组< 压缩速率，解压速率，压缩率> 目前还没有哪种压缩算法能够达到三者同时最优。

编码技术

Huffman coding

霍夫曼编码是一种熵编码，这种编码方式就是需要知道每个字符(symbol)出现的频率（需要扫描所有数据一次），然后构建哈夫曼二叉树。构建过程就是每次挑选出现频率最低的两个节点作为树的左右子节点，并且将它们合并成新的节点，新节点频率是它两之和。构建好huffman树后，就可以进行huffman编码，从根节点开始，左边支路编码为0，右边支路编码为1。然后再扫描一次数据，得到最优编码。缺点是耗时长，需要扫描两遍数据。因此有相关动态的huffman编码工作来提升它的性能，可能压缩率会有所下降。

这个句子“this is an example of a huffman tree”中得到的字母频率来建构霍夫曼树。句中字母的编码和频率如图所示。编码此句子需要135 bit（不包括保存树所用的空间）

构建完霍夫曼树后，就根据霍夫曼树进行编码

而解码的过程则是需要根据霍夫曼树进行解码，因此可能需要额外传输霍夫曼树（除非使用公共的霍夫曼树）。

缺点：对于具有均匀概率分布的一组符号，霍夫曼编码是无效的。

Arithmetic Coding

算术编码是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息编码为一个数，一个满足（0.0 ≤ n < 1.0）的小数n。这里以一个简单的例子来说明算术编码的原理

例: 对一个简单的信号源进行观察，得到的统计模型如下：

• 60%的机会出现符号 中性
• 20%的机会出现符号 阳性
• 10%的机会出现符号 阴性
• 10%的机会出现符号 数据结束符

根据这个统计模型，编码器可以将当前的区间分为若干子区间，子区间长度与对应符号的概率成正比。当前要编码的符号对应的子区间成为下一步编码中的初始区间。

例:对于前面提出的4符号模型：

• 中性对应的区间是[0, 0.6)
• 阳性对应的区间是[0.6, 0.8)
• 阴性对应的区间是[0.8, 0.9)
• 数据结束符对应的区间是[0.9, 1)

编码的过程其实就是确定最终小数所在的区间，解码过程则是根据小数所在的区间进行解码。

假设我们的信号是“中性 阴性 数据结束符”，接下来看看对这个信号进行算数编码的过程

首先初始区间是[0,1)，第一个字符“中性”使得编码后的区间在[0,0.6)，然后第二个字符“阴性”使得编码后的区间进一步在[0,0.6) 的 [0.8, 0.9]这个区间，也就是[0+0.6*0.8,0+0.6*0.9) = [0.48,0.54)这个区间。最后一个字符“数据结束符”使得整个区间进一步在[0.48,0.54)的[0.9,1) 这个区间，也就是[0.48+(0.54-0.48)*0.9,0.54)=[0.534, 0.540)这个区间。因此任意在这个区间内的数都可以还原这个信息。

在解码的过程中，假设我们拿到的数是0.538，首先他出现在初始区间[0, 0.6) 中，我们知道第一个符号肯定是“中性”，然后它又出现在[0,0.6)的[0.8, 0.9)这个区间中，我们知道第二个符号肯定是“阴性”，以此类推。

与霍夫曼编码相比，算术编码还能接受条件概率，即前面出现的字符会影响后面出现字符的概率这种情况。而原始的霍夫曼编码则是在符号之间相互独立、且分布不同时才能达到比较好的压缩效果。

Lempel-Ziv Codes

与霍夫曼编码相比，LZW编码法被视作将不同长度字符串以固定长的码编码（霍夫曼编码将固定长度字符用不同长度的码编码）。其优点在于此方法只需存储一个相当小的表格，即可存储资料还原时相对应的值，所以所需成本相对地低；然而，这种算法的设计着重在实现的速度，由于它并没有对数据做任何分析，所以并不一定是最好的算法（参考LZMA，LZ77）。

编码过程：

1. 初始化字典使其包含所有字符串的单一字符（例如ascii码）
2. 在字典中寻找配当前输入的最长字符串W
3. 将该字符串对应的字典编码作为结果输出，并且将W从输入中移除
4. 将W+W后面的那个字符添加到字典
5. 返回第二步

解码过程

解码过程通过从编码后的输入中读取一个值，在字典中找到对应的项目并进行输出。这种编码方式并不需要传输字典，因为字典可以在解码过程中构造出来：当解码一个值并输出一个字符串后，解码器将它与后面值的字符串的第一个字符进行拼接，作为新的字典项目放入字典中。然后处理下一值，直到全部处理完。

举个例子：假设要编码的字符串是"TOBEORNOTTOBEORTOBEORNOT#"

编码过程如表

解码过程如下

在实际的应用中，很多压缩算法库会对lz编码后的结果再次进行huffman之类的编码。

压缩算法

LZ77 、LZ78以及LZO

lz77和lz78都是基于字典的编码，lz77则会在压缩过程中维护一个滑动窗口，因此解码的时候必须从输入的起始位置开始。从概念上讲，lz78允许在解压时随机访问输入，如果整个字典都预先知道的话。然而在实际应用中，字典是在编码和解码过程中构造的。前面介绍的lz coding就是lz78编码。这里主要讲下lz77的思想：对于重复出现的字符串，我们只需要用一对<offset,length> 的数字就可以表示。例如“Hello world, hello ketty.”，对于第二个hello，我么可以用<13, 5> 来表示，表示它前面13个字符开始的5个字符（即第一个hello）。但是也可能找不到前面匹配的字符，因此使用一个三元组来表示，如利用<0,0,D>表示D本身。

具体实现则是使用滑动窗口，维护一个search buffer 和 look-ahead buffer。search buffer+look-ahead buffer的长度就是滑动窗口的大小。search buffer就是用来查找前面出现的字符，因为lz77的编码思想就是将前面出现的字符的位置以及长度来替代当前的字符，所以对于很长的文本必须限定搜索空间，这个搜索空间就是search buffer。look-ahead buffer则包含当前字符的后面的连续字符。一般我们使用的gzip算法默认配置32KB的滑动窗口，其中绝大部分用于存储search buffer，固定长度存储look-ahead buffer （例如 262个字符）。像gzip格式实现的是lz77+huffman，这种组合就成为deflate压缩算法。

LZO则是控制hash表的大小，并且代码实现上使用宏来减少函数的调用开销，主要通过一些工程上的优化来使得压缩算法更快。

BWT

也被称为块排序压缩，是一个被应用在数据压缩技术（如bzip2）中的算法。该算法于1994年被Michael Burrows和David Wheeler在位于加利福尼亚州帕洛阿尔托的DEC系统研究中心发明[1]。它的基础是之前Wheeler在1983年发明的一种没有公开的转换方法。

当一个字符串用该算法转换时，算法只改变这个字符串中字符的顺序而并不改变其字符。如果原字符串有几个出现多次的子串，那么转换过的字符串上就会有一些连续重复的字符，这对压缩是很有用的。该方法能使得基于处理字符串中连续重复字符的技术（如MTF变换和游程编码）的编码更容易被压缩。

变换过程：

算法将输入字符串的所有循环字符串按照字典序排序，并以排序后字符串形成的矩阵的最后一列为其输出。

还原过程：

基于上述的BWT变换过程，以字符串“banana”为例，我们得到了变换结果annb$aa。其还原过程见以下过程：

1.1 基于原字符串矩阵的最后一列为annb$aa，我们进行该列进行排序，得到$aaabnn,并将其作为还原矩阵的第一列

1.2 经过1.1的转移、排序和组合，我们得到了7对邻接字符串：<a$> <na> <na> <ba> <$b> <an> <an>，将这7对邻接字符串进行排序后，得到<$b> <a$> <an> <an> <ba> <na> <na>，由此，我们得到了还原矩阵的第二列b$nnaaa。

1.3 经过1.2的转移、排序和组合，我们得到了7对邻接字符串：<a$b> <na$> <nan> <ban> <$ba> <ana> <ana>，将这7对邻接字符串进行排序后，得到<$ba> <a$b> <ana> <ana> <ban> <na$> <nan>，由此，我们得到了还原矩阵的第三列abaan$n 依此类推

PPM

部分匹配预测 (PPM) 是一种基于上下文建模和预测的自适应统计数据压缩技术。 PPM 模型使用未压缩符号流中的一组先前符号来预测流中的下一个符号。 PPM 算法还可用于在聚类分析中将数据聚类为预测分组。例如，如果“compr”在前面出现了，则接下来出现“e”的概率就很高。PPM维护一个上下文信息来估计下一个输入字符的出现概率。算术编码就很适合这种情况，就如文中所提到的。详细来说，长的上下文将提升预估的概率，但是需要更多的时间。该方案一般有比较大的内存需求，因此具体的实现方案出现的并不多。具体实现在细节上差异会很大，目前比较知名的是PPMd，这个算法相关的介绍也比较少，因此我也没弄明白咋回事。它的应用场景却是存在的，就是WinRAR这个软件使用的就是PPMd算法。

参考

• https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch
• https://zh.wikipedia.org/wiki/%E7%AE%97%E6%9C%AF%E7%BC%96%E7%A0%81
• https://zh.wikipedia.org/wiki/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81
• https://zh.wikipedia.org/wiki/Burrows-Wheeler%E5%8F%98%E6%8D%A2
• https://en.wikipedia.org/wiki/Prediction_by_partial_matching
• Barr, Kenneth C., and Krste Asanović. “Energy-aware lossless data compression.” ACM Transactions on Computer Systems (TOCS) 24.3 (2006): 250-291.