title: 无损压缩算法理论学习总结 tags: - 整理总结 - 算法 - 无损压缩 categories: 1.编程 date: 2019-04-01 13:44:56 --- # 基本说明 [信息熵](https://www.wikiwand.com/zh-hans/%E7%86%B5_(%E4%BF%A1%E6%81%AF%E8%AE%BA)： 每条消息中包含的信息的平均量。消息的熵乘以消息的长度决定了消息可以携带多少信息。任何无损压缩技术不可能让一比特的消息携带超过一比特的信息。 以下说明中以“压缩”代替“无损压缩” 以本人的理解，可以将压缩算法分为两个层面： 1. 熵编码：根据消息中每个符号出现的概率，然后通过某种映射用更短的符号替代原来的符号，核心在于提高符号的信息熵 2. 字典编码：提取信息中的重复部分作为字典，然后通过字典和某种映射替代这些重复的部分，核心在于替代重复 ## [熵编码](https://www.wikiwand.com/zh-hans/%E7%86%B5%E7%B7%A8%E7%A2%BC%E6%B3%95) [霍夫曼编码](https://www.wikiwand.com/zh-hans/%E9%9C%8D%E5%A4%AB%E6%9B%BC%E7%BC%96%E7%A0%81)： 根据消息中符号出现的频率构建出霍夫曼树，实现频率高的符号编码短，然后根据霍夫曼树得到新的符号替代原来的符号 [算术编码](https://www.wikiwand.com/zh-hans/%E7%AE%97%E6%9C%AF%E7%BC%96%E7%A0%81)： 根据消息中符号出现的概率算出整个消息（符号串）的概率，一个满足（0.0 ≤ n < 1.0）的小数 n ，这个小数n就代表了这个消息 [区间编码](https://www.wikiwand.com/zh-hans/%E5%8C%BA%E9%97%B4%E7%BC%96%E7%A0%81)： 根据消息中符号出现的概率把符号串映射到大区间数值中的一段小区间（多个符号多次细分区），用小区间边缘的数值的唯一前缀就可以代表了这个区间对应的消息（效果其实和算术编码相同） ## [字典编码](https://www.wikiwand.com/en/Dictionary_coder) [RLE](https://www.wikiwand.com/zh-hans/%E6%B8%B8%E7%A8%8B%E7%BC%96%E7%A0%81)（Run-length Encoding）游程编码: 个人把他看作一种比较直觉朴素的字典编码，具体算法就是把字符串中重复出现的多个字符替换为重复次数外加这个字符 [MTF](https://www.wikiwand.com/zh-hans/Move-to-front_transform)(Move-to-front transform): 通过护“recently used symbols”最近访问过的字符栈表，作为一个动态字典，在编码消息时，用字符在栈表中的索引序号替代，同时调整栈表中该字符到栈顶，根据“空间局部性”原理可以实现数据压缩 [LZ77与LZ78](https://www.wikiwand.com/zh/LZ77%E4%B8%8ELZ78)： 典型的字典编码，较早出现并流行的两种通用压缩算法。LZ77：通过滑动窗口"slidingwindow"实现动态字典，用前面出现过的字符串作为字典通过映射（与前一个字符串的距离和字符串长度）替代后面重复出现的字符串；LZ78：提前解析输入数据，生成一个静态字典 ### 相关衍生算法 [LZSS](https://www.wikiwand.com/zh-hans/LZSS)： 衍生于LZ77，能检测到一个替换是否真的减小了文件大小，以及一些别的优化 [LZW](https://www.wikiwand.com/zh/LZW)： 衍生于LZ78，优化了字典编码存储，但由于专利限制了发展，在GIF中被使用 # 综合通用无损压缩算法 [DEFLATE](https://www.wikiwand.com/zh/DEFLATE)： 先用LZ77（或 LZSS）算法预处理，然后用霍夫曼编码对压缩后的 literal、length、distance 编码优化，如今最流行的通用压缩算法之一 [bzip2](https://www.wikiwand.com/en/Bzip2)： 涉及多种算法，主要流程包括先使用 Run-length Encoding 游程编码对原始数据进行处理，然后通过 [Burrows-Wheeler Transform](https://www.wikiwand.com/zh-hans/Burrows-Wheeler%E5%8F%98%E6%8D%A2) 转换（可逆的处理一段输入数据使得相同字符连续出现的次数最大化），再用 Move-to-front transform 转换，然后再次使用Run-length Encoding游程编码处理，接下来还会进行霍夫曼编码以及一系列相关处理，较为复杂，速率劣于DEFLATE但压缩率更高 [LZMA](https://www.wikiwand.com/zh/LZMA)：实现了LZ77修改版以位（bit）而非字节（byte）为单元级别的操作，并通过[马可夫链](https://www.wikiwand.com/zh/%E9%A9%AC%E5%B0%94%E5%8F%AF%E5%A4%AB%E9%93%BE)实现字典索引，速率和压缩率优于bzip2，另有多线程优化的版本LZMA2 [Brotli](https://www.wikiwand.com/zh/Brotli)： 基于LZ77算法的一个现代变体，使用了霍夫曼编码和二阶上下文建模，使用了预定义的120千字节字典包含超过13000个常用单词、短语和其他子字符串，预定义的算法可以提升较小文件的压缩密度。总体速率接近于DEFLATE且压缩率接近于LZMA ## 相关常见名词说明 RAR： 商业软件WinRAR提供的压缩文件格式，压缩算法实现带专利（可能衍生自LZSS） Zip： 一种规范开放的压缩文件容器，被多种压缩软件实现，兼容多种压缩算法主要为DEFLATE GZip： gnu/Linux下的文件压缩软件，提供gz压缩格式，压缩算法基于DEFLATE 7-Zip： 开源跨平台压缩软件，提供7z压缩格式，压缩算法主要为Bzip2以及LZMA ## 其他类型通用算法 另有[DMC（动态马可夫压缩）](https://www.wikiwand.com/zh-hans/%E5%8B%95%E6%85%8B%E9%A6%AC%E5%8F%AF%E5%A4%AB%E5%A3%93%E7%B8%AE)，[DeepZip](https://arxiv.org/abs/1811.08162),以及[PPM](https://www.wikiwand.com/en/Prediction_by_partial_matching)和他的改进版[PAQ](https://www.wikiwand.com/en/PAQ)（实现Context mixing 智能地结合多个 (PPM 是单个模型) 统计模型）等算法，基本原理是通过部分数据以及各种算法来预测后续输入的符号，通过这种算法来减少输出数据的熵实现压缩。 # 特定领域压缩算法 快速压缩算法：[QuickLZ](http://www.quicklz.com/)，[LZF](https://github.com/ning/compress)，[LZ4](https://www.wikiwand.com/zh-hans/LZ4)，[Snappy](https://www.wikiwand.com/zh-hans/Snappy)，都衍生自L77算法，具有还不错的压缩率以及极快的压缩解压速率，广泛用于RPC调用时传输数据压缩，LZ4还被用于内存压缩技术 无状态Zip压缩算法：[Stateless ZIP library - SLZ](http://www.libslz.org/)，提供了基于 zlib 实现的流数据压缩器 数值压缩算法：[Varint 与 ZigZag](http://www.360doc.com/content/17/1017/10/33093582_695630243.shtml)，Varint 可以压缩较小的正数，ZigZag 可以处理负数及大整数使之也可以使用 Varint 编码压缩，protobuf和thrift二进制序列化算法中都使用了二者结合的方式来压缩数字类型 JSON字符串压缩算法：[CJSON 和 HPack](https://blog.csdn.net/zhenyu5211314/article/details/52367185)，通过数据格式转换减少字符数实现数据压缩 其他还有各种针对如数据库数据，时序数据，图片，音频，视频等各种数据的无损压缩算法 # 总结与启发 一直以来对无损压缩算法的研究，一方面在提升熵的算法研究到算数编码基本已经到了极限，而另一方面去除信息本身重复部分的算法似乎还有研究空间，甚至有了DeepZip这种通过深度学习算法来寻找数据中隐藏的的重复模式的思路，真不知[魔笛手PiedPiper](http://www.piedpiper.com/)何时就要出现 而换个思路来看，从通用无损压缩算法和特定领域内的压缩算法来区分看的话，特定领域内的压缩算法往往根据特殊的数据内容或场景而实现优于直接使用通用压缩算法的效果（特定领域内数据明确的重复模式，类似Brotli中特定领域内的预定义字典等等），想到是否可以设计出压缩算法的公共框架，而把压缩算法分为具体的几个步骤然后在每个步骤根据实际需求做出更优的实现 参考： [1] 维基百科，相关链接已在正文中给出 [2] [无损数据压缩算法的历史](https://web.archive.org/web/20170330045922/http://blog.jobbole.com/77247/) [3] [ZIP 压缩算法详细分析及解压实例解释](https://web.archive.org/web/20180317013812/http://blog.jobbole.com/76676/)