区别:LZ77、LZ4、LZ4HC(压缩算法)?

2024-05-14

我了解LZ77和LZ78算法。 我读过有关LZ4的文章here http://www.brutaldeluxe.fr/products/crossdevtools/lz4/index.html and here http://fastcompression.blogspot.co.uk/2011/05/lz4-explained.html并发现其代码 http://code.google.com/p/lz4/source/browse/trunk/lz4hc.h?r=113.

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

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

LZ4 https://github.com/Cyan4973/lz4专为快速压缩而设计,每核每秒数百 MB。它适合需要非常便宜的压缩的应用程序:例如,您试图使网络或磁盘格式更紧凑,但无法在压缩上花费大量 CPU 时间。例如,在一个家庭中,snappy https://github.com/google/snappy/ and LZO http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Oberhumer.

自然的比较点是zlib的放气算法 https://en.wikipedia.org/wiki/DEFLATE,它使用LZ77 https://en.wikipedia.org/wiki/LZ77_and_LZ78 and 霍夫曼编码 https://en.wikipedia.org/wiki/Huffman_coding并用于 gzip、.ZIP 和 .PNG 格式以及许多其他地方。

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

  1. 他们使用更快的重复检测代码(通常是一个简单的哈希表 http://en.wikipedia.org/wiki/Hash_table没有碰撞检测),但不会搜索多个可能的匹配以找到最佳匹配(这将花费时间但会导致更高的压缩),并且无法找到一些短匹配。
  2. 他们只是尝试压缩输入中的重复——他们不会尝试利用某些字节比其他字节更有可能的优势outside的重复。
  3. 与2密切相关,它们一次生成输出字节,而不是位;允许字节的一部分代码有时会允许更多的压缩,但需要更多的 CPU 工作(通常是位移、屏蔽和分支)来编码和解码。
  4. 为了在现代 CPU 上快速实现它们,我们进行了大量的实际工作。

相比之下,DEFLATE 的压缩效果更好,但压缩和解压缩速度较慢,而高压缩算法如LZMA http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Markov_chain_algorithm, bzip2 http://en.wikipedia.org/wiki/Bzip2, LZHAM https://github.com/richgel999/lzham_codec, or brotli https://github.com/google/brotli往往需要更多时间(尽管Brotli 的更快设置可以与 zlib 竞争 https://quixdb.github.io/squash-benchmark/)。高压缩算法之间存在很多差异,但总的来说,它们倾向于捕获较长距离的冗余,更多地利用上下文来确定可能的字节,并使用更紧凑但更慢的方式以位表示结果。

LZ4HC 是 LZ4 的一种“高压缩”变体,我相信它改变了上面的第 1 点——压缩器在当前和过去的数据之间找到多个匹配,并寻找最佳匹配以确保输出较小。这改善了压缩ratio但降低了压缩率speed与LZ4相比。不过,解压速度并没有受到影响,因此,如果您压缩一次并解压多次,并且主要想要极其便宜的解压,那么 LZ4HC 是有意义的。

请注意,即使是快速压缩器也可能不允许一个核心饱和大量带宽,例如 SSD 或快速数据中心内链接提供的带宽。甚至还有速度更快、压缩比更低的压缩机,有时用于暂时将数据打包到RAM中 https://en.wikipedia.org/wiki/Virtual_memory_compression. WKdm https://github.com/berkus/wkdm and Density https://github.com/centaurean/density有两个这样的压缩机;他们共有的一个特点是作用于 4 字节机器字一次输入而不是单个字节。有时专用硬件可以实现非常快速的压缩,例如三星 Exynos 芯片 https://github.com/XileForce/Vindicator-S6/blob/master/drivers/memory/exynos-mcomp.c or 英特尔 QuickAssist 技术 http://www.intel.com/content/www/us/en/ethernet-products/gigabit-server-adapters/quickassist-adapter-for-servers.html.

如果您对比 LZ4 压缩更多但 CPU 时间比 deflate 更少的压缩感兴趣,LZ4 (Yann Collet) 的作者编写了一个名为的库Zstd https://github.com/facebook/zstd——这是一个Facebook 在其稳定版本上发布的博客文章 https://code.facebook.com/posts/1658392934479273/smaller-and-faster-data-compression-with-zstandard/, 背景有限状态机 http://fastcompression.blogspot.com/2013/12/finite-state-entropy-new-breed-of.html用于紧凑地编码重复信息,以及RFC 中的详细描述 https://datatracker.ietf.org/doc/html/draft-kucherawy-dispatch-zstd. Its 快速模式 https://github.com/facebook/zstd/releases/tag/v1.3.4可以在一些类似 LZ4 的用例中工作。 (此外,苹果开发了lzfse https://github.com/lzfse/lzfse基于类似的原则,谷歌开发了gipfeli https://github.com/google/gipfeli作为“中型”包装机。两者似乎在外界都没有多大用处。)此外,有几个项目旨在提供更快/更轻的 DEFLATE:SLZ http://1wt.eu/projects/libslz/, CloudFlare 和 Intel 对 zlib 的补丁 http://www.snellman.net/blog/archive/2015-06-05-updated-zlib-benchmarks/。 (也曾有过快速工作减压在大型现代 CPU 核心上 https://dougallj.wordpress.com/2022/08/20/faster-zlib-deflate-decompression-on-the-apple-m1-and-x86/.)

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

如果您要压缩一个长流,并且使用更多内核来加快速度可能会有所帮助,则可以通过 gzip 进行并行压缩pigz http://zlib.net/pigz/和 zstd 通过命令行工具-T选项(以及在库中)。 (有various http://conorstokes.github.io/compression/2016/02/15/an-LZ-codec-designed-for-SSE-decompression实验性的packers http://mattmahoney.net/dc/那里也有,但它们的存在更多是为了突破速度或密度的界限,而不是为了今天的使用。)

因此,一般来说,您可以为不同的应用程序提供一系列相当不错的替代压缩器:

  • 对于非常快的压缩:LZ4、zstd 的最低设置,甚至较弱的内存压缩器
  • 对于平衡压缩:DEFLATE 是旧标准;中低设置下的 Zstd 和 brotli 是新用途的良好替代品
  • 对于高压缩:brotli 或 Zstd 高设置
  • 对于非常高的压缩(例如压缩一次并提供多次的静态内容):brotli

当您从 LZ4 到 DEFLATE 到 brotli 时,您需要付出更多的努力来预测和编码数据,并以一定的速度为代价获得更多的压缩。

顺便说一句,像 brotli 和 zstd 这样的算法通常可以胜过 gzip——在给定速度下压缩得更好,或者更快地获得相同的压缩——但这实际上并不是因为 zlib 做了任何事情wrong。主要秘密可能是较新的算法可以使用更多内存:zlib 可以追溯到 1995 年(DEFLATE 可以追溯到 1995 年)1993 https://en.wikipedia.org/wiki/PKZIP#PKZIP)。那时候的内存cost https://jcmit.net/memoryprice.htm> 是现在的 3,000 倍,因此只保留 32KB 的历史记录是有意义的。 CPU 随着时间的推移而发生的变化也可能是一个因素:大量算术(如有限状态机中使用的)比以前相对便宜,并且不可预测ifs(分支机构)相对较贵。

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

区别:LZ77、LZ4、LZ4HC(压缩算法)? 的相关文章

随机推荐