lossless-compression - : LZ77 vs. LZ4 与 LZ4HC(压缩算法)的区别？

Question

我了解 LZ77 和 LZ78 算法。
我读到 LZ4 here和 here并找到 code for it .

这些链接描述了 LZ4 块格式。但是，如果有人可以解释(或指导我进行一些资源解释)，那就太好了:

LZ4和LZ77有什么不同？

LZ4HC 与 LZ4 有何不同？

什么想法让LZ4HC算法这么快？

Answer 1

LZ4旨在快速压缩，每个内核数百 MB/s。它非常适合需要非常便宜的压缩的应用程序:例如，您试图使网络或磁盘格式更紧凑，但无法承受在压缩上花费大量 CPU 时间。它在一个家庭中，例如，snappy和 LZO .
自然的比较点是zlib的DEFLATE algorithm , 使用 LZ77和 Huffman coding并且用于 gzip、.ZIP 和 .PNG 格式，以及其他太多数不胜数的地方。
这些快速压缩器的不同之处在于:

他们使用更快的重复检测代码(通常是一个简单的 hashtable，没有碰撞检测)，但不会搜索多个可能的匹配项以找到最佳匹配项(这需要时间但会导致更高的压缩)，并且无法找到一些简短的比赛。

他们只尝试压缩输入中的重复——他们不会尝试利用某些字节比重复之外的其他字节更有可能。

与 2 密切相关，它们一次生成输出字节，而不是位；允许部分字节代码有时会允许更多的压缩，但需要更多的 CPU 工作(通常是位移、掩码和分支)来编码和解码。

许多实际工作已经用于在现代 CPU 上快速实现它们。

相比之下，DEFLATE 的压缩效果更好，但压缩和解压缩速度较慢，而高压缩算法如 LZMA , bzip2 , LZHAM , 或 brotli往往需要更多时间(尽管 Brotli at its faster settings can compete with zlib )。高压缩算法之间有很多变化，但总的来说，它们倾向于捕获更远距离的冗余，更多地利用上下文来确定可能的字节，并使用更紧凑但更慢的方式以位表示其结果。
LZ4HC 是 LZ4 的“高压缩”变体，我相信它改变了上面的第 1 点——压缩器在当前和过去的数据之间找到不止一个匹配项，并寻找最佳匹配项以确保输出很小。与 LZ4 相比，这提高了压缩率，但降低了压缩速度。不过，解压速度不会受到影响，因此，如果您压缩一次并解压多次，并且主要想要非常便宜的解压，那么 LZ4HC 是有意义的。
请注意，即使是快速压缩器也可能不允许一个核心使大量带宽饱和，例如 SSD 或快速数据中心链接提供的带宽。甚至还有更低速比的更快压缩机，有时用于 temporarily pack data in RAM . WKdm和 Density是两台这样的压缩机；他们共有的一个特点是一次处理 4 字节的机器字输入，而不是单个字节。有时专用硬件可以实现非常快的压缩，例如 Samsung's Exynos chips或 Intel's QuickAssist technology .
如果您对压缩比 LZ4 多但比 deflate 占用更少的 CPU 时间感兴趣，LZ4 的作者 (Yann Collet) 编写了一个名为 Zstd 的库。 --这里有一个 blog post from Facebook at its stable release , 关于 finite state machines 的背景用于对重复的信息进行紧凑编码，以及 detailed description in an RFC .它的 fast modes可以在一些 LZ4-ish 用例中工作。 (此外，Apple 开发了 lzfse，基于类似的原则，Google 开发了 gipfeli 作为“中等”打包程序。两者似乎在外部世界中都没有得到太多使用。)此外，有几个项目旨在提供更快/更轻的 DEFLATE: SLZ和 patches to zlib by CloudFlare and Intel .
与最快的压缩器相比，那些“中等”压缩器添加了一种熵编码形式，也就是说它们利用了一些字节比其他字节更常见的方式，并且(实际上)在输出中为更常见的字节放置了更少的位值。
如果延迟而不是总 CPU 时间是您的主要关注点，并且您正在压缩一个长流，那么有一些工具可以并行进行压缩，例如 pigz和 -T zstd 命令行工具的线程选项。 (也有 various 实验性 packers，但它们的存在更多是为了插入速度或密度的界限，而不是今天使用。)
因此，总的来说，对于不同的应用程序，您有相当多的替代压缩器:

对于非常快的压缩:LZ4、zstd 的最低设置，甚至更弱的内存压缩器

对于平衡压缩:DEFLATE 是旧标准；中低设置的 Zstd 和 brotli 是新用途的不错选择

对于高压缩:brotli 或高设置下的 Zstd

对于非常高的压缩(例如压缩一次并提供多次的静态内容):brotli

当您从 LZ4 到 DEFLATE 再到 brotli 时，您会付出更多的努力来预测和编码数据，并以一定的速度为代价获得更多的压缩。
顺便说一句，像 brotli 和 zstd 这样的算法通常可以胜过 gzip——在给定的速度下压缩得更好，或者更快地获得相同的压缩——但这实际上并不是因为 zlib 做错了什么。主要的 secret 可能是较新的算法可以使用更多内存:zlib 日期为 1995(并且 DEFLATE 为 1993 )。那时的 RAM cost是今天的 3,000 倍以上，所以只保留 32KB 的历史记录是有意义的。随着时间的推移 CPU 的变化也可能是一个因素:大量的算术(如在有限状态机中使用的)比以前更便宜，而且不可预测 if s(分支)相对更贵。