zstd 的熵编码:FSE/ANS 为什么比 Huffman 更接近熵

← 上一篇 gzip 内部:一个 deflate 块里的 LZ77 加 Huffman

状态里存符号

实测 · 本机执行输出

  初始状态 x = 16;从最后一个符号开始往前编码(ANS 先进后出):x' = (x // f) × M + (x % f) + 累积频率
    编码 "a"(f=3,累积=0):x = 16 → (16 // 3) × 8 + 16 % 3 + 0 = 41  (x 变大 2.56 倍,-log2 概率 = 1.42 位,log2(变大倍数) = 1.36)
    编码 "a"(f=3,累积=0):x = 41 → (41 // 3) × 8 + 41 % 3 + 0 = 106  (x 变大 2.59 倍,-log2 概率 = 1.42 位,log2(变大倍数) = 1.37)
    编码 "c"(f=2,累积=6):x = 106 → (106 // 2) × 8 + 106 % 2 + 6 = 430  (x 变大 4.06 倍,-log2 概率 = 2.00 位,log2(变大倍数) = 2.02)
    编码 "b"(f=3,累积=3):x = 430 → (430 // 3) × 8 + 430 % 3 + 3 = 1148  (x 变大 2.67 倍,-log2 概率 = 1.42 位,log2(变大倍数) = 1.42)
    编码 "a"(f=3,累积=0):x = 1148 → (1148 // 3) × 8 + 1148 % 3 + 0 = 3058  (x 变大 2.66 倍,-log2 概率 = 1.42 位,log2(变大倍数) = 1.41)
    编码 "c"(f=2,累积=6):x = 3058 → (3058 // 2) × 8 + 3058 % 2 + 6 = 12238  (x 变大 4.00 倍,-log2 概率 = 2.00 位,log2(变大倍数) = 2.00)
    编码 "b"(f=3,累积=3):x = 12238 → (12238 // 3) × 8 + 12238 % 3 + 3 = 32636  (x 变大 2.67 倍,-log2 概率 = 1.42 位,log2(变大倍数) = 1.42)
    编码 "a"(f=3,累积=0):x = 32636 → (32636 // 3) × 8 + 32636 % 3 + 0 = 87026  (x 变大 2.67 倍,-log2 概率 = 1.42 位,log2(变大倍数) = 1.41)
  最终 x = 87026(17 位);解码时 x % 8 落在哪个符号的区间就是哪个符号:abcabcaa(还原 x = 16,与初始状态 16 相同)

ANS 用一个整数状态保存已经编码的符号:编码符号 s,状态乘以约 1/概率;解码看状态模 M 落在哪个区间,得到符号再还原。符号越罕见,状态涨得越多,所花的位数就是该符号的 -log2 概率,可以是分数位。

接近熵

实测 · 本机执行输出

  数据                             熵下限   Huffman      rANS Huffman 多出   rANS 多出   解码
  0.5 / 0.5                    32768     32768     32772       0.0%     0.01%   往返一致
  0.9 / 0.1                    15407     32768     15410     112.7%     0.02%   往返一致
  0.99 / 0.01                   2612     32768      2616    1154.4%     0.15%   往返一致
  0.999 / 0.001                  346     32768       350    9369.0%     1.14%   往返一致
  16 个符号 均匀                   131071    131072    131074       0.0%     0.00%   往返一致
  指数衰减的 20 个符号                 65525     65526     65572       0.0%     0.07%   往返一致
  products 文本(256 KiB)        168116    168967    168122       0.5%     0.00%   往返一致

rANS 在 0.9/0.1 的分布上只比熵多 0.02%(Huffman 多 112.7%),在 products 文本上几乎等于熵(多 0.00%)。偏斜越大、符号越少,Huffman 浪费越多。

量化精度

实测 · 本机执行输出

  数据                          M=2^6      M=2^8     M=2^10     M=2^12     M=2^14        熵下限
  0.99 / 0.01                  2744       2698       2694       2694       2694       2690
  0.999 / 0.001                 952        460        402        390        390        387
  指数衰减的 20 个符号                74860      67180      65774      65518      65470      65457
  products 文本                189202     168786     168162     168122     168128     168116

频率要缩放到总和为 2^k。k 太小,小概率被舍入,0.999/0.001 的信源在 2^6 时是 952 字节(熵 387),2^12 是 390。12 位左右基本够用。

tANS 与 FSE

实测 · 本机执行输出

  数据                           熵下限   Huffman  rANS(12)    tANS R=6    tANS R=8   tANS R=10   tANS R=11   tANS R=12   往返
  0.9 / 0.1                   3878      8192      3882        3883        3880        3880        3880        3880   全部一致
  0.99 / 0.01                  672      8192       676         695         677         674         674         674   全部一致
  16 个符号 均匀                  32766     32768     32770       32769       32769       32769       32768       32768   全部一致
  指数衰减的 20 个符号               16375     16377     16386       18020       16701       16434       16399       16385   全部一致
  products 文本(64 KiB)        41972     42189     41978       47301       42196       41978       41981       41973   全部一致

tANS 把状态转移预先算成表:每个状态给出符号、要读的位数和新状态基数。解码只查表、读位,没有除法。表大小 2^10–2^12 就贴着熵;太小(R=6)会有明显损失。FSE 是 zstd 采用的 tANS 实现,我按它的符号散布方式(步长 (L>>1)+(L>>3)+3,按记忆写出,表能铺满且往返一致)实现。

分数位

实测 · 本机执行输出

  归一化频率 {'a': 7, 'b': 5, 'c': 4};散布步长 (16>>1)+(16>>3)+3 = 13;表中符号序列:aabcabcabcabcaab
    状态   符号    读位数      新状态基数   新状态范围
     0    a      2         12   [12, 15]
     1    a      1          0   [0, 1]
     2    b      2          4   [4, 7]
     3    c      2          0   [0, 3]
     4    a      1          2   [2, 3]
     5    b      2          8   [8, 11]
     6    c      2          4   [4, 7]
     7    a      1          4   [4, 5]
     8    b      2         12   [12, 15]
     9    c      2          8   [8, 11]
    10    a      1          6   [6, 7]
    11    b      1          0   [0, 1]
    12    c      2         12   [12, 15]
    13    a      1          8   [8, 9]
    14    a      1         10   [10, 11]
    15    b      1          2   [2, 3]
  符号 a:频率 7/16,各状态读的位数 [2, 1, 1, 1, 1, 1, 1],平均 1.143 位;-log2(概率) = 1.193 位;Huffman 对 a/b/c 的码长是 1/2/2 位
  符号 b:频率 5/16,各状态读的位数 [2, 2, 2, 1, 1],平均 1.600 位;-log2(概率) = 1.678 位;Huffman 对 a/b/c 的码长是 1/2/2 位
  符号 c:频率 4/16,各状态读的位数 [2, 2, 2, 2],平均 2.000 位;-log2(概率) = 2.000 位;Huffman 对 a/b/c 的码长是 1/2/2 位
  (频率高的符号 a,有的状态只读 1 位,有的读 2 位——平均读的位数接近该符号的 -log2 概率,这是 Huffman 做不到的"分数位")

Huffman 给 a/b/c(频率 7/5/4)的码长是 1/2/2 位;FSE 表里 a 的 7 个状态有 6 个读 1 位、1 个读 2 位,平均 1.143 位,更接近 -log2(7/16) = 1.193。

实际收益

实测 · 本机执行输出

  token 流:14994 个 token,字面量/长度符号 14995 个(字母表 82 种),距离符号 9643 个(字母表 30 种),额外位 112028 位 = 14004 字节
  字面量/长度流:熵 9724 字节、Huffman 9768 字节、tANS(R=12)9731 字节(往返一致);距离流:熵 4425、Huffman 4463、tANS(R=10)4432(往返一致)
  合计(含额外位,不含码表):Huffman 28234 字节,tANS 28166 字节,tANS 小 0.2%;对照 zlib 级别 9 实际 28019 字节,zstd-19 实际 24762 字节

对 LZ77 的 token 流(82 种字面量/长度符号加 30 种距离符号),tANS 只比 Huffman 小 0.2%。zstd-19 比 zlib-9 小 11.6%,主要应该来自别的地方(更大的窗口、更好的匹配选择、对“重复使用的距离”的特殊处理等,见第 14、16 篇),这一点我没有逐项拆开验证。ANS 的优势是在符号分布很偏、或者要极快解码的时候。

分步演示

ANS 与 FSE

本步的对象

本文用到的工具与边界

本机 macOS 27 arm64 / Python 3.14.8(系统 Python,自带 compression.zstd)/ zstandard 0.25.0 / lz4 4.4.5 / zstd、lz4、brotli、protoc 命令行(Homebrew);msgpack、protobuf、snappy 等第三方库临时装在临时目录里,用完删除;所有数据都是本机脚本生成的合成数据(固定随机种子),没有使用任何真实网站或用户的数据;计时用 time.perf_counter,取多次中位数,数字每次运行会有小幅抖动。rANS(32 位状态、16 位输出、频率精度可调)和 tANS(表驱动、符号散布方式按 FSE 的做法)都是我手写的 Python 实现,所有编码结果都经过解码往返验证;FSE 的散布步长公式是我按记忆写的,没有对照 zstd 源码;LZ77 token 沿用第 11 篇;zstd 的实际压缩用 zstandard 库;所有数字都是确定性的
没有验证:zstd 内部实际用的 FSE 表格式(归一化频率的存储方式、低概率符号的特殊处理);zstd 的字面量用的是 Huffman 还是 FSE(我没有解析 zstd 帧);zstd 比 gzip 小的各项原因各占多少;ANS 的解码速度(纯 Python 没有意义);交错多路状态(提高并行度)的做法

下一篇 · 数据编码与压缩 14

zstd 的压缩级别:用更多时间换更小的体积到底怎么换