Table of Contents generated with DocToc
数据压缩技术是通过减少数据中的冗余信息,来降低数据所占用存储空间或传输带宽的技术。 常用的数据压缩算法包括霍夫曼编码、LZ77及其变种LZ78、Deflate、Lempel-Ziv-Welch(LZW)、Brotli、Zstandard(Zstd)等.
霍夫曼编码是一种广泛使用的无损数据压缩算法。它的核心思想是根据字符出现的频率来构造最优的二进制树。字符出现频率越高,其对应的二进制编码就越短;反之,编码越长。 这个算法首先统计待压缩数据中各个字符的出现频率,然后根据频率构造一棵最优二进制树,最后根据这棵树给每个字符分配独一无二的二进制编码。
实际应用中,霍夫曼编码被广泛应用于各种文件压缩和网络数据传输中。它之所以如此受欢迎,是因为它的压缩率较高,且是一种无损压缩算法,可以确保数据经压缩后再解压,数据不会有任何损失。其中,JPEG图像压缩和MP3音频压缩就大量使用了霍夫曼编码
LZ77和LZ78是两种经典的字典压缩算法,由以色列科学家Lempel和Ziv在1977年和1978年分别提出。这两种算法的核心思想都是利用之前出现过的数据片段来替代后续出现的重复片段。 与霍夫曼编码相比,LZ77和LZ78更加侧重于找到数据中的重复片段,并用较短的引用来代替这些片段,从而达到压缩的目的。
LZ77算法维护一个称为“滑动窗口”的结构,通过回溯查找之前出现过的字符串,并将其替换为较短的引用。而LZ78算法则是构造一个字典来存储出现过的数据片段,当再次遇到相同的片段时,直接用字典中的索引来表示。这两种算法的变种和改进版,如LZW、Deflate等,都在压缩效率和解压速度上有所优化,广泛应用于文件压缩、图像压缩和网络数据传输等领域
LZ77压缩算法的核心思想是对字符串进行扫描,对于前面已经出现过的子字符串,用(偏移量,匹配的字符串的长度)进行编码。LZ77中有三个重要的概念:短语字典、滑动窗口、前向缓冲区。
-
前向缓冲区:待编码的数据
-
滑动窗口:存放已经编码的数据
-
短语字典:用滑动窗口中的数据更新字典,并与前向缓冲区中的数据进行匹配
步骤1:逐字符扫描前向缓冲区,在滑动窗口中找出匹配的最长子字符串,如果找到,则执行步骤2,如果没有找到,执行步骤3
步骤2:对前向缓冲区中匹配的字符串进行编码并输出,编码的格式为(前向缓冲区中匹配开始位置距离滑动窗口中匹配开始位置的偏移量,匹配的长度),将匹配的字符串移入滑动窗口中,继续执行步骤1
步骤3:将当前字符编码为(0,0,当前字符值)并输出,表示滑动窗口中没有出现过该字符,并将该字符移入到滑动窗口中,继续执行步骤1
Deflate是一种组合了LZ77算法和霍夫曼编码的压缩算法,它在1990年由Phil Katz为ZIP文件格式设计。Deflate算法通过LZ77算法查找并压缩数据中的重复字符串,然后用霍夫曼编码进一步压缩已经压缩过的数据。 这种组合赋予了Deflate既有字典压缩的高效性,又有霍夫曼编码的高压缩率,使得Deflate在压缩比和速度上都表现出色。
Deflate已成为许多压缩软件和格式的标准算法,比如PNG图像格式就采用了Deflate算法进行数据压缩。同时,由于它的开放性和高效性,Deflate也被用在了很多其他领域,包括HTTP网络传输的内容编码中
LZW是LZ78算法的一种变体,由Terry Welch于1984年提出。LZW算法的核心在于构建一个动态的字典来存储输入数据流中出现的所有字符串片段。 当输入数据流中出现了字典中已经存在的字符串片段时,LZW算法仅输出该字符串片段在字典中的索引,而不是整个字符串。这种方法大大减小了数据的体积,实现了压缩。
由于其算法的简洁和效率,LZW被广泛用于计算机图形(如GIF图像格式)、文件压缩(如UNIX的compress命令)等领域。尽管LZW容易实现且压缩效果显著,但是因为存在版权问题,其应用受到了一定限制。
Brotli是由Google开发的一种新的数据压缩算法,旨在进一步优化压缩效率,特别是在网络传输中。Brotli算法建立在LZ77算法、霍夫曼编码和一种叫做静态霍夫曼树的变种之上。 它被设计用来提高网页加载速度,通过更高的压缩比来减少数据的传输量。
Brotli相较于之前的压缩算法,比如Deflate,提供了更高的压缩比和速度,使其非常适合用于移动网络环境下的网页和应用。如今,Brotli已被多个浏览器(如Chrome、Firefox等)和一些Web服务器支持,正逐步成为网络传输中的一个重要标准
Zstandard(Zstd)是由Facebook开发的一种压缩算法,它旨在提供高压缩比同时保持较快的压缩和解压速度。 Zstd结合了多种技术,包括霍夫曼编码、二分查找树以及有限状态熵编码(FSE)。它的设计考虑了多核心处理器的优势,能够在不牺牲压缩比的情况下,提供快速的压缩速度。
Zstd已经被应用于多种场景,包括数据库压缩、日志文件压缩以及为提升软件安装速度的安装包压缩等。由于其出色的性能,Zstd正逐渐成为新一代的压缩标准,被越来越多的软件和服务采用。
压缩库 | 压缩速度 | 解压缩速度 | 压缩比 |
---|---|---|---|
Snappy | 非常快 | 非常快 | 中等 |
gzip | 中等 | 中等 | 高 |
zlib | 中等 | 较快 | 较高 |
zlib压缩是一种无损压缩,底层使用deflate数据流压缩算法
gzip 对于要压缩的文件,首先使用LZ77算法的一个变种进行压缩,对得到的结果再使用Huffman编码的方法(实际上gzip根据情况,选择使用静态Huffman编码或者动态Huffman编码,详细内容在实现中说明)进行压缩。