LZ77、LZ4和LZ4HC（压缩算法）的区别是什么？

Question

我了解LZ77和LZ78算法。 我在这里和这里读到了有关LZ4的内容，并在这里找到了它的代码。

这些链接描述了LZ4块格式。 但如果有人能解释一下（或指导我查找某些资源以进行解释）以下几点，那将非常好:

• LZ4与LZ77有何不同？
• LZ4HC与LZ4有什么区别？
• 什么想法使得LZ4HC算法如此快速？

- ghost204nit

---

你有多个问题交织在一起。必须写一个10页的回复来涵盖所有问题。 - swdev

@swdev（尽管你说得对，但我尝试写了那个长长的回复 :)） - twotwotwo

Answer 1

LZ4 是一种快速压缩算法，每个核心可达到数百 MB/s 的压缩速度。它适用于需要非常便宜的压缩的应用程序：例如，您正在尝试使网络或磁盘格式更紧凑，但不能花费大量 CPU 时间进行压缩。它与 snappy 和 LZO 等算法属于同一类型。

自然的比较点是 zlib 的 DEFLATE 算法，它使用 LZ77 和 Huffman 编码，并被用于 gzip、.ZIP 和 .PNG 格式等太多地方以至于无法计数。

这些快速压缩器之间的区别在于：

1. 他们使用重复检测代码，通常是一个没有冲突检测的简单哈希表，速度更快，但不会在多个可能的匹配项中搜索最佳匹配项（这需要时间但可以获得更高的压缩率），并且无法找到一些短匹配项。
2. 他们只尝试压缩输入中的重复内容，而不尝试利用某些字节比其他字节更有可能出现的情况 在 重复之外。
3. 与第二点密切相关，他们一次生成字节输出，而不是位；允许分数字节码有时可以实现更好的压缩，但需要更多的CPU工作（通常是位移和掩码和分支）来编码和解码。
4. 大量的实际工作已经投入到使它们在现代CPU上实现快速。

相比之下，DEFLATE 获得更好的压缩率，但压缩和解压速度较慢，而像 LZMA、bzip2、LZHAM 或 brotli 这样的高压缩算法往往需要更多时间（尽管 Brotli 在更快的设置下可以与 zlib 竞争）。高压缩算法之间存在很大差异，但总体上，它们往往捕获更长距离的冗余，更充分地利用上下文来确定哪些字节是可能的，并使用更紧凑但更慢的方式将结果表达为位。

LZ4HC是LZ4的“高压缩”变种，我认为它改变了上述第一点——压缩器在当前数据和过去数据之间找到多个匹配项，并寻找最佳匹配项以确保输出尽可能小。这提高了压缩比，但与LZ4相比降低了压缩速度。但解压速度不会受到影响，因此，如果您只需要进行一次压缩并且多次解压缩，而且大多数情况下需要极其便宜的解压缩，则使用LZ4HC是有意义的。

请注意，即使是快速的压缩器也可能无法使一个核心饱和大量带宽，例如SSD或快速数据中心链接提供的带宽。甚至有更快的压缩器，比如用于临时将数据打包到RAM中的WKdm和Density，它们共享的一个特点是一次处理4字节的机器字而不是单独的字节。有时候专门的硬件可以实现非常快的压缩，例如三星的Exynos芯片或Intel的QuickAssist技术。

如果您想要比LZ4更加压缩，但CPU时间比deflate少的话，LZ4的作者Yann Collet编写了一个名为Zstd的库--这里有一个Facebook在其稳定版本发布时的博客文章，介绍了用于紧凑编码重复信息的有限状态机的背景知识，以及在RFC中的详细描述。它的快速模式可以在某些类似于LZ4的用例中使用。(此外，苹果公司基于类似原则开发了lzfse，而谷歌公司则开发了gipfeli作为“中等”压缩器。两者似乎在外部世界中并没有得到很多使用。) 此外，一些项目旨在提供更快/更轻的DEFLATE：SLZ，由CloudFlare和Intel提供的zlib补丁。(还进行了针对大型现代CPU核心的快速解压缩工作。)

与最快的压缩器相比，这些“中等”打包程序添加了一种形式的熵编码，也就是说，它们利用了某些字节比其他字节更常见的特点，并且（实际上）在输出中为更常见的字节值放置较少的位。

如果您正在压缩一个长流，并且使用更多核心可以加快速度，则通过pigz和zstd通过命令行工具的-T选项（以及库中）提供并行压缩。 （还有各种实验性打包程序，但它们更多地存在于推动速度或密度的边界，而不是今天的使用。）

因此，总体而言，您对于不同应用程序有一个相当好的备选压缩程序谱系：

• 对于非常快的压缩：LZ4、zstd 的最低设置，甚至更弱的内存压缩器
• 对于平衡的压缩：DEFLATE 是旧标准；Zstd 和 Brotli 在低到中等设置上是新用途的良好替代品
• 对于高度压缩：Brotli，或 Zstd 在高设置上
• 对于非常高的压缩（例如静态内容只压缩一次并多次提供服务）：Brotli

当您从 LZ4 到 DEFLATE 再到 Brotli 时，您会增加更多预测和编码数据的努力，并在某些速度上获得更多的压缩。

作为旁注，像Brotli和Zstd这样的算法通常可以优于gzip——在给定速度下更好地压缩，或者更快地获得相同的压缩效果——但这并不是因为zlib做错了什么。主要的秘密可能是新算法可以使用更多的内存：zlib可以追溯到1995年（DEFLATE到1993年）。当时，RAM的成本比今天高出3000倍以上，因此保留32KB的历史记录是有意义的。随着时间的推移，CPU的变化也可能是一个因素：有限状态机中使用的大量算术运算相对便宜，而不可预测的if语句（分支）相对更昂贵。

- twotwotwo

---

请再翻译一页，您忘记描述LZ77及其差异了 :-) - swdev

@twotwotwo 写得很好。我知道这可能超出了范围，但是 https://github.com/pieroxy/lz-string 呢？你认为这个算法比 LZ4 更快吗？ - NiCk Newman

@NiCkNewman -- 由于必须在JS虚拟机中运行，因此受到限制，而LZ4可以使用优化的C或汇编语言。 JavaScript引擎在处理任务时表现出色，但仍不能像优化本地代码一样。它可能会更慢。尽管如此，对于你特定的任务而言，它仍然可能是正确的工具。 - twotwotwo

我同意，添加lz77/gzip会很棒。它与lzma有何不同。 - Evan Carroll

@EvanCarroll DEFLATE是一种LZ算法，它使用霍夫曼编码将常见字节编码为较少的位数。这是gzip中使用的算法，并且有一些关于它与高压缩算法的区别的概括。这可能不是太多具体信息的正确位置；如果您需要这些信息，可以从维基百科或其他资源开始研究，并在遇到需要定义的术语时继续研究。 - twotwotwo

我是LZ-String的作者。它并不比LZ4更快，因为它基本上是一个带有一些技巧来适应字符串输出的LZW实现。我选择这个非常古老的算法，是因为当我写这个库时它是没有专利保护的，并且非常容易实现。从速度上来看，它可能与zlib相当，但在压缩比方面却更差。 - pieroxy