43

我了解 LZ77 和 LZ78 算法。我在这里和这里阅读了 LZ4并找到了它的代码。

这些链接描述了 LZ4 块格式。但是，如果有人可以解释（或引导我到一些资源解释），那就太好了：

  • LZ4与LZ77有何不同？
  • LZ4HC 与 LZ4 有何不同？
  • 是什么想法让 LZ4HC 算法这么快？
4

1 回答 1

104

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 时间比 deflate 更少感兴趣，LZ4 (Yann Collet) 的作者写了一个名为Zstd的库——这是来自 Facebook 的稳定版本的博客文章，关于有限状态机的背景用于对重复信息进行紧凑编码，并在 RFC 中进行详细描述。它的快速模式可以在一些 LZ4-ish 用例中工作。（此外，Apple 以类似的原则开发了lzfse，而 Google 开发了gipfeli作为“中等”打包程序。在外界似乎都没有得到太多使用。）此外，一些项目旨在提供更快/更轻的 DEFLATE：SLZ和CloudFlare 和 Intel 对 zlib 的补丁。

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

如果您正在压缩一个长流，并且使用更多内核加快速度可能会有所帮助，则可以通过pigz和 zstd 通过命令行工具的-T选项（以及在库中）使用并行压缩。（那里也有各种实验性的打包机，但它们的存在更多是为了突破速度或密度的界限，而不是今天使用。）

因此，一般来说，您可以为不同的应用程序提供相当多的替代压缩器：

  • 对于非常快速的压缩：LZ4，zstd 的最低设置，甚至更弱的内存压缩器
  • 对于平衡压缩：DEFLATE 是旧标准；中低设置的 Zstd 和 brotli 是新用途的不错选择
  • 对于高压缩：brotli，或 Zstd 高设置
  • 对于非常高的压缩率（例如压缩一次并提供多次的静态内容）：brotli

当你从 LZ4 到 DEFLATE 到 brotli 时，你会付出更多的努力来预测和编码数据，并以一些速度为代价获得更多的压缩。

顺便说一句，像 brotli 和 zstd 这样的算法通常可以胜过 gzip——在给定的速度下压缩得更好，或者更快地获得相同的压缩——但这实际上并不是因为 zlib做错了什么。主要的秘密可能是较新的算法可以使用更多内存：zlib 可以追溯到 1995 年（和 DEFLATE 到1993 年）。那时 RAM的成本是今天的 3,000 倍以上，因此只保留 32KB 的历史记录是有意义的。CPU 随时间的变化也可能是一个因素：大量的算术（如在有限状态机中使用的）比以前相对便宜，而不可预测if的 s（分支）相对更昂贵。

于 2015-02-20T18:35:44.253 回答