数据压缩算法-Zstd
2018-03-15 12:03:04 
阿炯
代号为 Zstandard 或者 zstd，是一种快速无损压缩算法，是针对zlib级别的实时压缩方案，以及更好的压缩比。它由一个非常快的熵阶段，由Huff0和FSE库提供。采用C语言开发并在BSD和GPLv2双重许可证协议下授权。旨在提供快速压缩，并实现高压缩比，它既不像LZMA和ZPAQ那样追求尽可能高的压缩比，也不像LZ4那样追求极致的压缩速度。Zstd (Zstandard) 是由 Facebook 开源的快速无损压缩算法，主要应用于 zlib 级别的实时压缩场景，并且具有更好的压缩比。Zstd 还可以以压缩速度为代价提供更强的压缩比，速度与压缩率的比重可通过增量进行配置。
它是由Facebook的Yann Collet开发的一个无损数据压缩算法，Zstandard在设计上与DEFLATE(zip、gzip)算法有着差不多的压缩比，但有更高的压缩和解压缩速度。Zstandard使用字典算法(LZ77)结合熵编码法的有限状态熵(tANS)。它提供了非常宽范围的压缩/速度比，同时支持非常快的解码器。它还为小数据提供了一种特殊模式，称为字典压缩，并且可以从任何样本集创建字典。它支持多达 19 个压缩等级，提供 2.877 的压缩比，高达 430 MB/s 的压缩率和 1110 MB/s 的解压缩速度。
Zstandard, or zstd as short version, is a fast lossless compression algorithm, targeting real-time compression scenarios at zlib-level and better compression ratios. It's backed by a very fast entropy stage.
该项目可生成和解码 .zst、.gz、.xz 和 .lz4 文件的工具。项目是否需要其他程序语言，在 Zstandard 主页上提供已知语言绑定列表。
Zstd还可以以压缩速度为代价提供更强的压缩比。速度与压缩比率可以通过配置实现，在所有设置中，解压速度保持不变，并在所有LZ压缩算法( 比如 zlib 或者 lzma ) 共享的属性中保持不变。
Zstd can also offer stronger compression ratios at the cost of compression speed. Speed vs Compression trade-off is configurable by small increments. Decompression speed is preserved and remains roughly the same at all settings, a property shared by most LZ compression algorithms, such as zlib or lzma.
基准测试
Linux Debian (Linux version 4.8.0-1-amd64) with a Core i7-6700K CPU @ 4.0GHz, using lzbench, an open-source in-memory benchmark by @inikep compiled with GCC 6.3.0.
最新版本的7-Zip ZS已经内置zstd算法支持了，但这是在windows平台上运行的7z软件，Linux上的支持zstd的7z软件可以参看p7zip with Zstandard(不过版本稍旧)。Debian 和 Ubuntu 开发人员 Julian Andres Klode 说到："Canonical计划在Ubuntu Linux操作系统的未来版本中默认实现 Facebook 开源的 zstd 压缩算法"。
Zstd包里面有压缩和解压缩的并行(多线程)实现。从1.3.2版本(2017年10月)开始，zstd 有选择地实现非常长的搜索和重复数据消除（--long，128MiB窗口），类似于rzip或lrzip。
压缩速度在最快和最慢级别之间可以相差20倍或更多，而解压缩速度统统很快，在最快和最慢级别之间相差不到20%。Zstandard命令行有一个“自适应”（--adapt）模式，根据I/O条件改变压缩级别，主要是写入输出的速度。其最大压缩级别下的压缩比接近lzma、lzham和ppmx，并且比lza或bzip2性能更好。Zstandard达到了当前的Pareto边界，因为它解压缩的速度比任何其他当前可用的算法都要快，并且有类似的或者更好的压缩比。
字典对小文件的压缩比有很大的影响，所以Zstandard可以使用用户提供的压缩字典。它还提供了一种训练模式，能够从一组样本生成一个字典。特别是，可以加载一个字典来处理文件之间具有冗余的大型文件集，但不一定在每个文件（例如日志文件）内。
自1.0版本以来，它有额外的专利权许可。自1.3.1版，拿掉此专利权许可，授权改成BSD+GPLv2双授权。
关于对它的实际使用，请参看zstd压缩算法的一些使用案例。
Zstd 是一项性能优秀的压缩技术，与 zlib、lz4、xz 等压缩算法不同，Zstd 寻求的是压缩性能与压缩率通吃的方案。Zstd 还为小数据提供了一种特殊的压缩模式 “字典压缩”，支持以训练方式生成字典文件，以提高对小数据包的压缩率。以下是常见的压缩算法性能对比：
有人对比了 Zstd-LZ4-Zlib-Benchmark 的相关性能指标，从中可以看到更为详细的对比。
最新版本：1.4
zstd 1.4.0 发布了，此版本主要关注于高级 API 的稳定性，高级 API 提供了一种在兼容 API 和 ABI 的情况下，在压缩和解压期间设置特定参数的方法。例如，它允许使用多个线程进行压缩，启用 --longmode，设置帧参数和加载字典。它与 ZSTD_compressStream *() 和 ZSTD_compress2() 兼容。还有一个高级解压 API，允许设置最大内存使用和加载字典等参数。它与现有的解压功能 ZSTD_decompressStream() 和 ZSTD_decompressDCtx() 兼容。旧的流函数都与新 API 兼容，文档提供了新 API 中的等效函数调用。稳定的函数将继续受到支持，但类似 ZSTD_initCStream_usingDict() 这样处于实验阶段的函数最终将被标记为已弃用并删除，以支持新的高级 API。
它在最快的压缩级别变得更快了，测试显示，在 zstd 最快的策略 level 1 的大多数情况下压缩速度都快了 6-8％。它修复了一些错误，包括只能在小众用例中触发的罕见数据损坏错误，当执行以下所有操作时会出现该 bug：使用多线程模式，重叠大小>= 512 MB，使用的 strategy>= ZSTD_btlazy，压缩超过 4 GB。新版本还包括一些性能改进，其中主要的改进是 Zstd 解压速度快了约 7%。
此版本新增了一个实验性的函数 ZSTD_decompressBound()，详情查看更新说明。
2020年12月20日，zstd v1.4.8 正式发布，官方特别推荐升级到此版本，因为在性能、修复错误以及增加新功能方面均有不小的改进，修复了关于内部缓存的问题，详情如下：
改进--long模式
--long模式用于在合理的时间和内存预算内分析大量数据，--long模式算法运行在正则表达式匹配器上，两者均对压缩结果产生影响。不过这两个阶段独立运行，因此导致在高级别的压缩水平下出现细微差异。所以无法在默认情况下一直启用--long模式。新版本修复了此问题，对于压缩级别为 16 以上的压缩，开启--long模式的压缩性能始终比关闭--long模式好。
提升解压小文件块的速度
此版本对解压小文件块的速度进行了优化，具体的提升根据文件块的大小有所不同。
共享线程池(Shared Thread Pool)
这是一项试验性功能。默认情况下，每个压缩上下文可以设置为使用最大可用的线程。但在复杂情况下，可能会有多个压缩上下文并行工作，每个上下文都会使用部分线程。在这种场景中，可能需要控制所有这些压缩上下文使用的线程总数。新增的共享线程池功能支持让所有这些压缩上下文共享同一个线程池，添加ZSTD_CCtx_refThreadPool()参数即可使用。
提升字典压缩速度(Dictionary Compression)
引入的新的实验性字典压缩算法，适用于中档压缩级别，采用了ZSTD_greedy,ZSTD_lazy和ZSTD_lazy2等策略。新算法可以在ZSTD_CDict创建过程中通过选择压缩参数ZSTD_c_enableDedicatedDictSearch来触发。
更多详情请查看这里。
Zstd v1.4.9 已于2021年3月初发布， 这是一个增量版本，其中包括各种改进和错误修复。
>2x Faster Long Distance Mode
归功于许多优化措施，Long Distance Mode (LDM) 速度出现了大大提升。这些优化在保持压缩率的同时极大地加快压缩时间。用 zstd -T0 -1 --long=31 在 Intel I9-9900K上以 3.2GHz 的速度进行基准测试，可以看到。linux对应的版本有 linux 4.0、5.0 和 5.10 git archives 的集合。
新的实验性解压功能：ZSTD_d_refMultipleDDicts
如果启用了高级参数 ZSTD_d_refMultipleDDicts，那么对 ZSTD_refDDict() 的多次调用将在相应的 DCtx 中被执行。用法示例：
ZSTD_DCtx* dctx = ZSTD_createDCtx();
ZSTD_DCtx_setParameter(dctx, ZSTD_d_refMultipleDDicts, ZSTD_rmd_refMultipleDDicts);
ZSTD_DCtx_refDDict(dctx, ddict1);
ZSTD_DCtx_refDDict(dctx, ddict2);
ZSTD_DCtx_refDDict(dctx, ddict3);
...
ZSTD_decompress...
现在可以通过单个 ZSTD_decompress 调用对每个具有自己的 dictID 的多个帧进行解压缩。只要每个帧头的 dictID 引用 DCtx 中的一个 dictID，那么相应的字典就会被用来解压该特定的帧。值得注意的是，statically-allocated DCtx 禁用了此功能。更多的发行说明可查看此处。
最新版本：1.5
zstd 1.5 已于2021年5月中旬正式发布，新版本在性能方面再度带来了令人印象深刻的改进，其中包括：
提升 Middle-Level 压缩的速度
提升 High-Level 压缩的压缩率
更快的解压速度和升级链接库
提升 Middle-Level 压缩的速度：v1.5.0 为压缩策略greedy、lazy和lazy2引入了新的默认匹配查找器（对于大于 256K 的输入，它们映射到 5-12 级）。该优化极大地提升了压缩速度，同时压缩率略有波动（<0.5％），并且内存使用量相等或减少。
提升 High-Level 压缩的压缩率：在新版本中，默认情况下对于 High-Level 级别 (16+) 的压缩， 启用通过块拆分 (block splitting) 以提高压缩率的功能。
更快的解压速度：在此版本中，使用 large window 设置（例如--long或--ultra）压缩的数据的解压缩速度已得到显着提升。具体效果取决于编译器和版本，clang效果通过最好。
更多的细节请查看发行公告。
zstd (Zstandard) v1.5.5 已于2023年4月上旬发布，此版本修复了在高度压缩模式下出现的罕见损坏错误。由于随机出现这种情况的可能性极低，所以在多次模糊测试中都没被发现。直到一名维护者收集到庞大的数据后才设法检测出一个案例。官方建议用户升级到此版本，尤其是使用了高度压缩模式 high compression modes (levels 16+)。其他改进包括：
改进--patch-from模式的内存使用和速度：v1.5.5 为 posix 和 windows 引入了内存映射字典。此功能允许 zstd 对大型词典进行内存映射，而不是要求将它们加载到内存中。这对于为大型数据集运行补丁的内存受限环境来说可能会有很大的不同。
针对特定场景的中度压缩速度提升：v1.5.0 版中针对 level 5-12 引入的行哈希匹配查找器在 1.5.5 版中得到了改进，提高了其在特定极端情况下的速度。
更多详情请查看发行说明。
v1.5.6 已于2024年3月下旬发布。此次发布的部分原因是 Chrome 123 添加了对 Web 流量的 Zstd 编码支持，Chrome 现在支持使用 Zstandard (zstd) 作为内容编码，以加快页面加载速度并节省带宽。虽然 Chrome 支持 Zstd 编码是件好事，但目前 Web 服务器对 Zstd 编码的支持还很有限。Zstd 团队希望 1.5.6 发布后，新版本能得到更多 Web 浏览器的采用，并继续得到其他软件的支持。
v1.5.6 还添加了一个新的稳定参数 "ZSTD_c_targetCBlockSize"，以更好地处理 Web 浏览器中的增量更新、细粒度二进制大小选择以及其他各种增强功能。现在还能更好地支持 SPARC64、ARM64EC 和 RISC-V 架构，以及 QNX、AIX、Solaris 和 HP-UX 操作系统。详情查看发行说明。
它是由Facebook的Yann Collet开发的一个无损数据压缩算法，Zstandard在设计上与DEFLATE(zip、gzip)算法有着差不多的压缩比，但有更高的压缩和解压缩速度。Zstandard使用字典算法(LZ77)结合熵编码法的有限状态熵(tANS)。它提供了非常宽范围的压缩/速度比，同时支持非常快的解码器。它还为小数据提供了一种特殊模式，称为字典压缩，并且可以从任何样本集创建字典。它支持多达 19 个压缩等级，提供 2.877 的压缩比，高达 430 MB/s 的压缩率和 1110 MB/s 的解压缩速度。
Zstandard, or zstd as short version, is a fast lossless compression algorithm, targeting real-time compression scenarios at zlib-level and better compression ratios. It's backed by a very fast entropy stage.
该项目可生成和解码 .zst、.gz、.xz 和 .lz4 文件的工具。项目是否需要其他程序语言，在 Zstandard 主页上提供已知语言绑定列表。
Zstd还可以以压缩速度为代价提供更强的压缩比。速度与压缩比率可以通过配置实现，在所有设置中，解压速度保持不变，并在所有LZ压缩算法( 比如 zlib 或者 lzma ) 共享的属性中保持不变。
Zstd can also offer stronger compression ratios at the cost of compression speed. Speed vs Compression trade-off is configurable by small increments. Decompression speed is preserved and remains roughly the same at all settings, a property shared by most LZ compression algorithms, such as zlib or lzma.
基准测试
Linux Debian (Linux version 4.8.0-1-amd64) with a Core i7-6700K CPU @ 4.0GHz, using lzbench, an open-source in-memory benchmark by @inikep compiled with GCC 6.3.0.
| Compressor name | Ratio | Compression | Decompress. |
|---|---|---|---|
| zstd 1.1.3 -1 | 2.877 | 430 MB/s | 1110 MB/s |
| zlib 1.2.8 -1 | 2.743 | 110 MB/s | 400 MB/s |
| brotli 0.5.2 -0 | 2.708 | 400 MB/s | 430 MB/s |
| quicklz 1.5.0 -1 | 2.238 | 550 MB/s | 710 MB/s |
| lzo1x 2.09 -1 | 2.108 | 650 MB/s | 830 MB/s |
| lz4 1.7.5 | 2.101 | 720 MB/s | 3600 MB/s |
| snappy 1.1.3 | 2.091 | 500 MB/s | 1650 MB/s |
| lzf 3.6 -1 | 2.077 | 400 MB/s | 860 MB/s |
最新版本的7-Zip ZS已经内置zstd算法支持了，但这是在windows平台上运行的7z软件，Linux上的支持zstd的7z软件可以参看p7zip with Zstandard(不过版本稍旧)。Debian 和 Ubuntu 开发人员 Julian Andres Klode 说到："Canonical计划在Ubuntu Linux操作系统的未来版本中默认实现 Facebook 开源的 zstd 压缩算法"。
Zstd包里面有压缩和解压缩的并行(多线程)实现。从1.3.2版本(2017年10月)开始，zstd 有选择地实现非常长的搜索和重复数据消除（--long，128MiB窗口），类似于rzip或lrzip。
压缩速度在最快和最慢级别之间可以相差20倍或更多，而解压缩速度统统很快，在最快和最慢级别之间相差不到20%。Zstandard命令行有一个“自适应”（--adapt）模式，根据I/O条件改变压缩级别，主要是写入输出的速度。其最大压缩级别下的压缩比接近lzma、lzham和ppmx，并且比lza或bzip2性能更好。Zstandard达到了当前的Pareto边界，因为它解压缩的速度比任何其他当前可用的算法都要快，并且有类似的或者更好的压缩比。
字典对小文件的压缩比有很大的影响，所以Zstandard可以使用用户提供的压缩字典。它还提供了一种训练模式，能够从一组样本生成一个字典。特别是，可以加载一个字典来处理文件之间具有冗余的大型文件集，但不一定在每个文件（例如日志文件）内。
自1.0版本以来，它有额外的专利权许可。自1.3.1版，拿掉此专利权许可，授权改成BSD+GPLv2双授权。
关于对它的实际使用，请参看zstd压缩算法的一些使用案例。
Zstd 是一项性能优秀的压缩技术，与 zlib、lz4、xz 等压缩算法不同，Zstd 寻求的是压缩性能与压缩率通吃的方案。Zstd 还为小数据提供了一种特殊的压缩模式 “字典压缩”，支持以训练方式生成字典文件，以提高对小数据包的压缩率。以下是常见的压缩算法性能对比：
有人对比了 Zstd-LZ4-Zlib-Benchmark 的相关性能指标，从中可以看到更为详细的对比。
最新版本：1.4
zstd 1.4.0 发布了，此版本主要关注于高级 API 的稳定性，高级 API 提供了一种在兼容 API 和 ABI 的情况下，在压缩和解压期间设置特定参数的方法。例如，它允许使用多个线程进行压缩，启用 --longmode，设置帧参数和加载字典。它与 ZSTD_compressStream *() 和 ZSTD_compress2() 兼容。还有一个高级解压 API，允许设置最大内存使用和加载字典等参数。它与现有的解压功能 ZSTD_decompressStream() 和 ZSTD_decompressDCtx() 兼容。旧的流函数都与新 API 兼容，文档提供了新 API 中的等效函数调用。稳定的函数将继续受到支持，但类似 ZSTD_initCStream_usingDict() 这样处于实验阶段的函数最终将被标记为已弃用并删除，以支持新的高级 API。
它在最快的压缩级别变得更快了，测试显示，在 zstd 最快的策略 level 1 的大多数情况下压缩速度都快了 6-8％。它修复了一些错误，包括只能在小众用例中触发的罕见数据损坏错误，当执行以下所有操作时会出现该 bug：使用多线程模式，重叠大小>= 512 MB，使用的 strategy>= ZSTD_btlazy，压缩超过 4 GB。新版本还包括一些性能改进，其中主要的改进是 Zstd 解压速度快了约 7%。
此版本新增了一个实验性的函数 ZSTD_decompressBound()，详情查看更新说明。
2020年12月20日，zstd v1.4.8 正式发布，官方特别推荐升级到此版本，因为在性能、修复错误以及增加新功能方面均有不小的改进，修复了关于内部缓存的问题，详情如下：
改进--long模式
--long模式用于在合理的时间和内存预算内分析大量数据，--long模式算法运行在正则表达式匹配器上，两者均对压缩结果产生影响。不过这两个阶段独立运行，因此导致在高级别的压缩水平下出现细微差异。所以无法在默认情况下一直启用--long模式。新版本修复了此问题，对于压缩级别为 16 以上的压缩，开启--long模式的压缩性能始终比关闭--long模式好。
提升解压小文件块的速度
此版本对解压小文件块的速度进行了优化，具体的提升根据文件块的大小有所不同。
共享线程池(Shared Thread Pool)
这是一项试验性功能。默认情况下，每个压缩上下文可以设置为使用最大可用的线程。但在复杂情况下，可能会有多个压缩上下文并行工作，每个上下文都会使用部分线程。在这种场景中，可能需要控制所有这些压缩上下文使用的线程总数。新增的共享线程池功能支持让所有这些压缩上下文共享同一个线程池，添加ZSTD_CCtx_refThreadPool()参数即可使用。
提升字典压缩速度(Dictionary Compression)
引入的新的实验性字典压缩算法，适用于中档压缩级别，采用了ZSTD_greedy,ZSTD_lazy和ZSTD_lazy2等策略。新算法可以在ZSTD_CDict创建过程中通过选择压缩参数ZSTD_c_enableDedicatedDictSearch来触发。
更多详情请查看这里。
Zstd v1.4.9 已于2021年3月初发布， 这是一个增量版本，其中包括各种改进和错误修复。
>2x Faster Long Distance Mode
归功于许多优化措施，Long Distance Mode (LDM) 速度出现了大大提升。这些优化在保持压缩率的同时极大地加快压缩时间。用 zstd -T0 -1 --long=31 在 Intel I9-9900K上以 3.2GHz 的速度进行基准测试，可以看到。linux对应的版本有 linux 4.0、5.0 和 5.10 git archives 的集合。
新的实验性解压功能：ZSTD_d_refMultipleDDicts
如果启用了高级参数 ZSTD_d_refMultipleDDicts，那么对 ZSTD_refDDict() 的多次调用将在相应的 DCtx 中被执行。用法示例：
ZSTD_DCtx* dctx = ZSTD_createDCtx();
ZSTD_DCtx_setParameter(dctx, ZSTD_d_refMultipleDDicts, ZSTD_rmd_refMultipleDDicts);
ZSTD_DCtx_refDDict(dctx, ddict1);
ZSTD_DCtx_refDDict(dctx, ddict2);
ZSTD_DCtx_refDDict(dctx, ddict3);
...
ZSTD_decompress...
现在可以通过单个 ZSTD_decompress 调用对每个具有自己的 dictID 的多个帧进行解压缩。只要每个帧头的 dictID 引用 DCtx 中的一个 dictID，那么相应的字典就会被用来解压该特定的帧。值得注意的是，statically-allocated DCtx 禁用了此功能。更多的发行说明可查看此处。
最新版本：1.5
zstd 1.5 已于2021年5月中旬正式发布，新版本在性能方面再度带来了令人印象深刻的改进，其中包括：
提升 Middle-Level 压缩的速度
提升 High-Level 压缩的压缩率
更快的解压速度和升级链接库
提升 Middle-Level 压缩的速度：v1.5.0 为压缩策略greedy、lazy和lazy2引入了新的默认匹配查找器（对于大于 256K 的输入，它们映射到 5-12 级）。该优化极大地提升了压缩速度，同时压缩率略有波动（<0.5％），并且内存使用量相等或减少。
提升 High-Level 压缩的压缩率：在新版本中，默认情况下对于 High-Level 级别 (16+) 的压缩， 启用通过块拆分 (block splitting) 以提高压缩率的功能。
更快的解压速度：在此版本中，使用 large window 设置（例如--long或--ultra）压缩的数据的解压缩速度已得到显着提升。具体效果取决于编译器和版本，clang效果通过最好。
更多的细节请查看发行公告。
zstd (Zstandard) v1.5.5 已于2023年4月上旬发布，此版本修复了在高度压缩模式下出现的罕见损坏错误。由于随机出现这种情况的可能性极低，所以在多次模糊测试中都没被发现。直到一名维护者收集到庞大的数据后才设法检测出一个案例。官方建议用户升级到此版本，尤其是使用了高度压缩模式 high compression modes (levels 16+)。其他改进包括：
改进--patch-from模式的内存使用和速度：v1.5.5 为 posix 和 windows 引入了内存映射字典。此功能允许 zstd 对大型词典进行内存映射，而不是要求将它们加载到内存中。这对于为大型数据集运行补丁的内存受限环境来说可能会有很大的不同。
针对特定场景的中度压缩速度提升：v1.5.0 版中针对 level 5-12 引入的行哈希匹配查找器在 1.5.5 版中得到了改进，提高了其在特定极端情况下的速度。
更多详情请查看发行说明。
v1.5.6 已于2024年3月下旬发布。此次发布的部分原因是 Chrome 123 添加了对 Web 流量的 Zstd 编码支持，Chrome 现在支持使用 Zstandard (zstd) 作为内容编码，以加快页面加载速度并节省带宽。虽然 Chrome 支持 Zstd 编码是件好事，但目前 Web 服务器对 Zstd 编码的支持还很有限。Zstd 团队希望 1.5.6 发布后，新版本能得到更多 Web 浏览器的采用，并继续得到其他软件的支持。
v1.5.6 还添加了一个新的稳定参数 "ZSTD_c_targetCBlockSize"，以更好地处理 Web 浏览器中的增量更新、细粒度二进制大小选择以及其他各种增强功能。现在还能更好地支持 SPARC64、ARM64EC 和 RISC-V 架构，以及 QNX、AIX、Solaris 和 HP-UX 操作系统。详情查看发行说明。
项目主页：