文本压缩算法的对比和选择

Dear 丶 2022-06-12 04:36 162阅读 0赞

本文主要粗略介绍数据压缩主要算法类别，以及最新针对Web文本资源的zStd和Brotli算法的设计要点。为Web业务应用如何使用它们替换传统gzip提供些参考。最后是一个文本有损压缩的尝试。

在数据压缩领域里，文本压缩的历史最久，从Morse到Huffman和算术编码(Arithmetic coding)，再到基于字典和上下文的压缩算法。各种算法不断改进，从通用算法，到现在更具针对性的算法，结合应用场景的垂直化的趋势越来越明显。所以**在选择或者评价压缩算法，一定要结合实际应用场景加以考虑，包括字符集、内容的大小、压缩及解压的性能、以及各端支持情况**。

## 数据压缩算法 ##

一套完整的压缩算法，实际以下几个部分：  
![algorithm][]

其中除编码外的三项目的都是找到一个适于编码的表示方法，而编码则是以简化的方法进行输出。最典型的建模方法是基于字符的概率统计，而基于上下文的建模方法(Context Modeling)则是从文本内容出发，它们追求的目标都是让字符的出现概率越不平均越好。转换方法是最具代表性的是基于词典的转换，比如庞大的LZ族系。Huffman和算术编码则是常见的编码方法。

因为语言本身的特性，基于上下文的建模方法(Context Modeling，如PPM\*系列算法)可以得到更好的压缩比，但却由于它的性能问题却很普及。当前比较流行的压缩算法中其突破的核心只有两个:

*  ANS (FSE是它的一个实现): Facebook zStd, Apple的lzfse等
 *  Context Modeling + LZ77 (编码是Huffman): Brotli

下图为六种算法的压缩比测试的结果，分别针对一本英文小说，一本中文小说，和一份较小(4KB+)的中文混合的JSON数据。  
![comparison][]  
*\*其中PPM是Context Modeling的代表。*  
可以看到算法对字符集(中文与英文)和大小都是敏感的，表现各不相同。

### 算法思想的简单概括 ###

**Huffman编码**受到了Morse编码的影响，背后的思想就是将最高概率出现的字母以最短的编码表示。比如英文中字母e出现概率为12%，字母z的出现概率还不到1%。

**算法编码以及区间编码**，它们是利用字符概率分布，将字符组合转变为概率的层次划分，最终转换一个固定的数字(算术编码和区间编码最大差别就在于一个使用小数，另一个使用整数)。可以对应下图考虑下AAAA，以及AAB的编码输出 (在0-1的轴上找到一个数字来表示。)。  
![arithmetic][]

上面这两类算法一直霸占着算法编码领域，各种拥有大量的变形。从实用效果上，算术编码的压缩比一般要好于Huffman。但Huffman的性能要优于算术编码，两者都有自适应的算法，不必依赖全文进行概率统计，但毕竟算术编码还是需要更大的计算量。

**ANS**是前两类编码算法战争的终结者。它在2014年被提出来，随后很快就得到了大量应用。本质上属于算术编码，但它成功地找到了一个用**近似概率**表示的表格，将原来的概率计算转换为查表。所以它是一个达到Huffman编码效率的算术编码方法。\*\*[FSE(Finite State Entropy)][FSE_Finite State Entropy]\*\*是ANS最为著名的实现。

之前提过**建模方法**，要追求字符出现概率的不平均。比如**动态马尔可夫压缩(DMC, dynamic Markov coding)**。仍以英为例，全文来看，字母e出现概率最高，但是在首字母这种状态下，字母t的出现概率可以接近17%。就是字母在是否首字母的两种状态下是有两种概率分布的：  
![markov][]  
*\*非首母下，各字母的出现概率有可能还有变化。*

**基于上下文的建模**，可以想象下成语填空或者诗词填空，其中有一个条件概率的问题。在下图中，如果单个字符看，我们只能从整体汉字的概率分布来考虑`人`后面的字。如果从词的角度发出，后面确实可能会出现几个概率较大的单字，这是一阶上下文。再进一步，如果之前出现过单字`华`，这是二阶上下文(2nd order)，后面文字出现的概率又会发生变化。如果再往前取一个单字又是`中`，那么不单是后面单字`民`的概率极高，而且再往后有三个字的出现概率也是奇高的。在随后编码时，我们就可以为它找出一个最短的表示。  
![context][]  
实际应用不可能让算法先要理解文字，绝大部分情况也不可能为此先建一个语料库，即使有语料库，其处理性能仍然会是很大的问题。其实我们也不需要得到极为精确的相关性，只要快速掌握到一定的模式就足够了。好像学生根本不需要做大规模的训练，就能很快注意到老师的口头禅或者常用语，进而学得有模有样。所以可行的算法只需要基于一部分内容的上下文进行预测，这就是\*\*PPM（部分匹配预测，prediction by partial match）\*\*以及各种演进版本。

**转换(Transform)里词典方法很好理解，就不介绍了，已经是应用最为广泛技术。而文本压缩基本目标是无损压缩，所以去冗余**这项我们最后再谈。

### 内容字符集与大小的影响 ###

我们思考一个问题：为什么各种算法对内容字符集和大小的效果不同？

字符集的差异很好理解，由前面提到的信息熵决定。有很多人在连续很多年都讨论过这个问题，也有非常精确的汉字信息熵的评价。单纯从当前编码的角度来看，就是作为中文基础单元的单字数远比英文中基本字母多得多。大的字符集很自然就使得字符间的概率差异较小，所以此时Huffman和算术编码这类依赖于概率统计的算法对于中文压缩都远不及对英文压缩的效果。

回头再看下上面算法对比结果。当纯英文时，算术编码压缩比优于Huffman。遇到大字符集的中文时，基本和Huffman一样了。这两个算法在这个测试场景没有拉来明显差距，可以动手换个二进数据再对比一下。

如果遇到中英文混合，且内容较小的JSON数据时，算术编码就歇菜了。

内容大小的影响是来自于算法本身的`学习成本`。从统计的角度看，内容大小代表了样本的多寡，会直接影响统计结果。以基于概率统计的算法为例，如果极少字符，有利于编码。但同时没有足够的数据量，字符间没法形成概率分布的差异，又不利于编码。两者共同决定最终了压缩比。

在测试数据里**基于上下文建模的PPM**表现明显优于Huffman和算术编码。说明虽然仅仅在局部理解字符出现的相关性，就已经能够很好地优化效果了。即使是小数据，也远高于前面两类的效果。

到这里，请思考一个问题：

*  **什么方法能降低压缩算法的学习成本？**

那么我们需要先定义:

*  字符集是什么？它的规模多大？字符的概率分布如何？
 *  内容会多大？  
    *\*效率和费用的问题，我们不讨论了。*  
    这个时候**转换**就能发挥最大的功效了，特别预设字典类的算法。

下面是一更为具体的问题，也可以练习一下:  
*如果我们要设计一个极短文本（如100字以内）的压缩算法，什么会是最为效的算法？*

## Brotli与zStd的对比和选择 ##

在Web应用场景下，压缩算法要追求的是更小且更快（对于流式数据，还有吞吐量的要求，另有算法应对），算法主要在压缩比和性能之间寻求平衡。目前页面上的各种文本资源主要还是使用gzip压缩，自zStd和Brotli推出后，我们该如何选择呢？

如果你只想了解一下两者的选择，可以跳过下面关于两者对比的一节。

### Brotli与zStd的对比 ###

Brotli算法可以理解为LZ\* + Context Modeling + Huffman编码。这是一个极为完整的无损压缩算法，三个部分全涉及到了。它的compression level分为11级，一般测试而言它的level 5可以达到gzip 9的效果。主要特色包括:

*  词典的Sliding Window扩充到16MB
 *  针对6国常用词及HTML&JS常用关键词的静态(预置)词典
 *  基于二阶上下文建模 (2nd order context modeling)  
    注意context modeling的性能很弱，如果对压缩性能要求不高（如本地PC压缩），可以把level调到6以上测试下。目前Chromium-based的浏览都默认支持Brotli。

zStd是基于FSE(ANS的一个实现)，针对MB级别以上的数据，最为有效。 但是对于小数据，它特别提供一个词典方法（回顾下前面关于小数据压缩的问题）。 这个方法需要针对目标数据做训练，就能生成这个词典。使用的方法如下:

1) 词典训练
    zstd --train FullPathToTrainingSet/* -o dictionaryName
    
    2)  压缩
    zstd -D dictionaryName FILE
    
    3) 解压
    zstd -D dictionaryName --decompress FILE.zst

这种方法的一个局限就是应用的范围，需要既要有相对稳定的内容，又要有客户端的支持。

### Brotli和zStd的选择 ###

如果两个可以同时选择时：  
**较大的文本数据，选择zStd。较小的数据，选择Brotli或者zStd的词典模式。**  
大和小的边界需要根据内容测试来定义。500KB左右，zStd的表现一般会超过Brotli。

**不要使用默认值对比。**  
Brotli默认的compression level是它的最大值，即11。而zstd默认是3, gzip默认为6。

以下是使用UC头条的33条数据，大小在3~26KB，包括HTML和JSON数据，在Mac Pro上做的对比测试。  
针对性能，直接使用工具对每个文件调用一次，最后加总时间的方法进行测试，并不是工具批次处理功能，所以存在一定的优化空间，特别是Brotli这种需要加载预置词典的算法。

从完成全部文件压缩所用时间上看，zstd/brotli对比gzip的耗时都有一定的增加。zstd-10和brotli-6基本接近:  
![cost][]

但从压缩比上看，brotli-6的效果就要优于zstd-10了:  
![ratio][]

## 算法选择需要考虑的因素 ##

所以本文写到这里，可以得出结论只有一个，**选择一个文本压缩算法最有效的方式是实验**，而且不要轻人别人的测试结果，如果不知道为什么？麻烦回到最上方，重新读一遍。只能通过实验，才能得出一个更为有效的算法以及参数的选择。

*  **压缩比** 确定出目标内容，并按涉及的字符集和大小，按组合和梯度做好测试。
 *  **压缩性能 & 解压性能** 执行压缩和解压的设备各是什么？性能带来的延迟影响有多大？
 *  **各端支持的情况** 特别是客户端、浏览器上的支持情况。
 *  **内容动态性** 即目标内容变化频率。比如实时压缩，且吞吐量较大，你就要评估下LZ4算法。其它情况要用好缓存和CDN。
 *  **专利费用** 比如算术编码是用专利费用的，而区间编码则是免费的。

## 文本的有损压缩? ##

开篇也提到了针对场景的压缩算法研究是目前的趋势，特别是找到更有效的建模方法。传统意义上理解数据压缩，包括文本压缩都应当是无损的。但其实也有一种场景是需要有损压缩的。

比如早期电报，惜字如金。在现在的场景下，内容的概要处理就是有损压缩的一个典型需求。内容的大爆发之后就有内容的进一步管理和挖掘的问题。内容的概要处理一是方便展示，二是方便检索和归类。

借助现在NLP领域的成果，我们可以很轻松地对句子结构和成分进行分析。可以在句子中定位出介词短语(PP)，量词短语（QP），动词短语（VP），又或者名词短语（NP）等。基于这个结果，可以定位出句子的主要成分，然后把修饰成分作为冗余去掉（**去冗余**）。

以句子`从乐视危机、易到事件，再到资金冻结、机构撤资，最近半年，乐视就像一部跌宕起伏的电视剧，作为乐视的创始人，贾跃亭一次又一次被推上风口浪尖。`为例:  
![nlp][]

我们去掉修饰短语，使用图中标出的名词及动词短语，就很容易得到核心成份:  
`贾跃亭被推上风口浪尖。`

示例使用R及Standford CoreNLP包在Mac OS下完成，源码在[GitHub][]上。

虽然目前这种处理的性能还是达到产品化要求，但相关的应用已经近在眼前。

--------------------

因为非压缩领域的专业人员，本文只是一段时间学习的总结。一定有错误和理解不透的地方，欢迎指正!

--------------------

2021毕业生阿里校招，有兴趣可以私信联系！感谢！

[algorithm]: /images/20220612/3d093e1eb8ff422b90b0aefa0776a7cc.png
[comparison]: /images/20220612/54510d3f3ef94a71a6c6eadf824ee39c.png
[arithmetic]: /images/20220612/91f95578dd5c4609bfb14736ca991cbf.png
[FSE_Finite State Entropy]: https://github.com/Cyan4973/FiniteStateEntropy
[markov]: /images/20220612/8013a771071f4322ae6c420efbe5fd56.png
[context]: /images/20220612/8696488330e14c85abf87634eef508c8.png
[cost]: /images/20220612/5958087494194e56b414c4bf78e881d2.png
[ratio]: /images/20220612/3ce00a45bd8a4a7a9bf2b4ed040f8ed3.png
[nlp]: /images/20220612/15992fcaf01743a3a9412ab0faadec51.png
[GitHub]: https://github.com/HorkyChen/LossyTextCompression