京公网安备11010502063487号Huffman 编码是 gzip、zstd 等压缩器里的熵编码部分:出现越多的符号用越短的码。这篇自己写出来,看它离熵多近、什么时候浪费,以及它在整个压缩里到底贡献了多少。
出现次数 {'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2};0 阶熵 2.0404 bit/符号,共 11 个符号 → 理论下限 22.44 位
第 1 步:合并 "c"(1)+ "d"(1)→ "cd"(2)
第 2 步:合并 "b"(2)+ "r"(2)→ "br"(4)
第 3 步:合并 "cd"(2)+ "br"(4)→ "cdbr"(6)
第 4 步:合并 "a"(5)+ "cdbr"(6)→ "acdbr"(11)
码长 {'a': 1, 'b': 3, 'c': 3, 'd': 3, 'r': 3};规范码 {'a': '0', 'b': '100', 'c': '101', 'd': '110', 'r': '111'}
编码后 23 位 = 2.88 字节(定长 8 位是 88 位;平均码长 2.0909 bit,熵 2.0404 bit);编码结果 01001110101011001001110反复取出现次数最少的两个符号合并,合并的次数就是码长:出现多的符号码短,出现少的码长。abracadabra 的 11 个符号编码成 23 位(定长 88 位),平均码长 2.0909 bit,熵 2.0404 bit。
不同的字节值 59 种;熵 5.1347 bit/字节;Huffman 平均码长 5.1620 bit/字节(差 0.0273,约 0.53%);最短码 3 位,最长码 11 位 编码后 676591 字节(熵下限 673018 字节,原 1048576 字节,压缩比 1.550×) 最常出现的 6 个字节及其码长:'"'(12.2%)→3 位、'e'(6.1%)→4 位、'a'(5.9%)→4 位、't'(4.9%)→4 位、':'(4.4%)→5 位、'i'(4.4%)→5 位
products 文本用到 59 种字节值,Huffman 平均码长 5.1620 bit/字节,比熵只多 0.53%,但只靠字节频率压缩比只有 1.55×。Huffman 已经几乎榨干了字节频率,剩下的压缩来自别处。
分布 熵 Huffman 平均码长 多出 合并 2 个符号 合并 4 个符号 0.5 / 0.5 1.0000 1.0000 0.0% 平均每符号 1.0000( 0.0%) 平均每符号 1.0000( 0.0%) 0.9 / 0.1 0.4690 1.0000 113.2% 平均每符号 0.6450( 37.5%) 平均每符号 0.4925( 5.0%) 0.99 / 0.01 0.0808 1.0000 1137.7% 平均每符号 0.5150(537.4%) 平均每符号 0.2727(237.5%) 0.999 / 0.001 0.0114 1.0000 8666.0% 平均每符号 0.5015(4296.1%) 平均每符号 0.2523(2111.2%) 0.7 / 0.2 / 0.1 1.1568 1.3000 12.4% 平均每符号 1.1650( 0.7%) 平均每符号 1.1639( 0.6%) (把多个符号合成一个大符号再 Huffman,每个符号的平均码长逼近熵,代价是码表按符号个数的幂次增长)
Huffman 每个符号至少一位。概率 0.9/0.1 的二元信源熵只有 0.469 bit,Huffman 用 1 位,多 113.2%。合并多个符号可以逼近熵但码表指数增长。zstd 的 FSE/ANS 用另一种办法解决(第 13 篇)。
编码解码往返(前 100000 字节):一致;编码后 515264 位 = 64408 字节 码表只存码长:59 个符号用到的码长(每个 4 位,没出现的符号码长 0,共 256 个位置)= 128 字节;若把整棵树存下来(每个符号 1 字节符号值 + 1 字节码长)约 118 字节 把 256 个码长当作字节数组,再用 deflate 压一下:69 字节(deflate 对码长序列自己也用了游程 + Huffman 来存)
解码端只要知道每个符号的码长,就能按固定规则重建同一套码,所以码表只存码长。码表是每个块都要付的固定成本,deflate 还要把码长序列再压缩一遍。
最大码长限制 实际最长码 平均码长 bit/字节 比不限制多
99 11 5.1620 0.000%
15 11 5.1620 0.000%
11 11 5.1620 0.000%
9 9 5.1647 0.053%
8 8 5.1762 0.276%
(这里用"反复把次数减半直到最长码不超过限制"的简单办法,deflate 和 zstd 用的是更精细的算法,结果会略好一些)deflate 把码长限制在 15 位,zstd 限制在 11 位,让解码用小的查找表。对这份数据限制到 9 位只多 0.053%,代价很小。
Z_DEFAULT_STRATEGY(LZ77 + Huffman) 213985 字节 压缩比 4.90× Z_FILTERED 216278 字节 压缩比 4.85× Z_HUFFMAN_ONLY(只做 Huffman) 677871 字节 压缩比 1.55× Z_RLE 677720 字节 压缩比 1.55× 我算的 Huffman 理论大小 676591 字节(不含码表);Z_HUFFMAN_ONLY 多出的部分是 deflate 的块头和码表
只做 Huffman(zlib 的 Z_HUFFMAN_ONLY)是 1.55×,加上 LZ77 匹配是 4.90×。gzip 的高压缩比主要来自 LZ 匹配把重复内容替换掉,Huffman 再把剩下的符号编码得更紧。LZ77 见下一篇。