区别:LZ77与LZ4对比LZ4HC(压缩算法)？

Question

我理解LZ77和LZ78算法.我在这里和这里阅读了LZ4 并找到了代码.

这些链接描述了LZ4块格式.但如果有人可以解释(或指导我解释某些资源),那就太好了:

• LZ4与LZ77有何不同？
• LZ4HC与LZ4有什么不同？
• 什么想法使LZ4HC算法如此之快？

Answer 1

LZ4可以快速压缩,每个核心数百MB/s.它适用于您希望压缩非常便宜的应用程序:例如,您尝试使网络或磁盘格式更紧凑但不能在压缩上花费大量CPU时间.这是一个家庭,例如,snappy和LZO.

自然比较点是zlib的DEFLATE算法,该算法使用LZ77和Huffman编码,用于gzip,.ZIP和.PNG格式,以及太多其他需要计算的地方.

这些快速压缩机的不同之处在于

1. 他们使用更快的重复检测代码(通常是一个没有碰撞检测的简单散列表),但是不会搜索多个可能匹配的最佳匹配(这需要时间但会导致更高的压缩),并且找不到一些简短的火柴.
2. 他们只是尝试压缩输入中的重复 - 他们不会试图利用某些字节比其他字节更常见.
3. 与2密切相关,它们一次产生输出字节,而不是位; 允许部分字节代码有时会允许更多的压缩,但需要更多的CPU操作(可能是位移和屏蔽和分支)来编码和解码.
4. 许多实际工作已经用于在现代CPU上快速实现它们.

相比之下,DEFLATE获得更好的压缩效果,但压缩和解压缩速度较慢,而LZMA,bzip2,LZHAM或brotli等高压缩算法往往需要更多时间(尽管Brotli在更快的设置下可以与zlib竞争).高压缩算法之间存在很多差异,但从广义上讲,它们倾向于捕获较长距离的冗余,更多地利用上下文来确定可能的字节,并使用更紧凑但更慢的方式来表示其结果.

LZ4HC是LZ4的"高压缩"变体,我相信,它改变了上面的第1点 - 压缩器在当前和过去的数据之间找到多个匹配,并寻找最佳匹配以确保输出很小.与LZ4相比,这提高了压缩比但降低了压缩速度.然而,减压速度并没有受到伤害,所以如果你压缩一次并且多次减压并且大部分都想要非常便宜的减压,那么LZ4HC会有意义.

请注意,即使是快速压缩器也可能不允许一个内核饱和大量带宽,例如SSD或快速数据中心链路提供的带宽.甚至更快的压缩器具有较低的比率,有时用于临时将数据打包在RAM中.WKdm和Density是两种这样的压缩机; 他们共享的一个特征是一次作用于输入的4字节机器字而不是单个字节.有时,专用硬件可以实现非常快速的压缩,例如三星的Exynos芯片或英特尔的QuickAssist技术.

如果你有兴趣压缩超过LZ4,但CPU时间比放气时间短,LZ4(Yann Collet)的作者写了一个名为Zstd的库; 在其稳定发布时,Facebook发布了他们如何使用它.它使用有限状态机而不是霍夫曼码进行熵编码; 我不是这方面的专家,但至少在RFC中详细描述了算法.zstd的最快模式现在接近LZ4的比率和速度.Apple 在类似的原则上写了lzfse.几年前,谷歌发布了一个名为gipfeli的图书馆,尽管它似乎没有引起太大的关注.还有一些旨在以Zlib格式加速压缩的项目,如SLZ和CloudFlare和Intel的zlib补丁.

与最快的压缩器相比,那些"中型"压缩器增加了一种形式的熵编码,也就是说它们利用了某些字节比其他字节更常见的方式,并且(实际上)在输出中为更常见的字节放置了更少的位值.

如果主要关注的是延迟而不是总CPU时间,并且您正在压缩一个长流,则可以使用并行执行压缩的工具,例如pigz和-Tzstd命令行工具的线程选项.(那里也有各种各样的实验包装工具,但它们更多地用于推动速度或密度的界限,而不是今天使用.)

所以,一般来说,你有不同的应用压缩器用于不同的应用程序:LZ4(甚至更弱的内存压缩器)用于实时压缩,DEFLATE作为平衡压缩的旧标准,Zstd作为积极开发的新型替代品,以及brotli和其他人用于高压缩.当您从LZ4转移到DEFLATE到brotli时,您需要花费更多精力来预测和编码数据,并以某种速度为代价获得更多压缩.

顺便说一句,像brotli和zstd这样的算法通常可以胜过gzip - 在给定的速度下更好地压缩,或者更快地获得相同的压缩 - 但实际上并不是因为zlib 做错了什么.相反,zlib于1995年发布,并为当时的硬件做出了很好的选择:例如,当RAM 成本超过现在的3,000倍时,它的32KB历史窗口是有意义的.今天的CPU也扭曲了其中操作便宜/昂贵的平衡,例如,难以预测的分支今天是一个更大的交易,并且做大量的算术相对便宜.