为什么 fixed-length code 浪费

计算机存文本，最 naive 的办法是每个字符占一样多的位：ASCII 用 8 bit，哪怕只出现 4 种字符——2 bit 就够编号了。但即便压到「刚好够用的 fixed-length code」，仍然浪费：因为字符出现得有多有少，出现 100 次的 $e$ 和只出现 1 次的 $z$ 占同样的位数，并不划算。

Huffman 的想法很朴素：越常见的字符，codeword 越短。把省下来的位让给罕见字符，总长度就降下来了。

1 · 关键直觉

frequency 越不均匀，Huffman 相对 fixed-length code 省得越多。反过来，若所有字符出现次数一样，variable-length code 基本没有优势：字符种数是 2 的幂时 Huffman 恰好退化成等长码（实测 abcd 每字符 2 bit，与 entropy 相等）；不是 2 的幂时它仍略优于等长码但也贴不上 entropy（abc 每字符 1.667 bit，entropy 1.585，等长码要 2 bit；abcde 则是 2.4 对 2.322 对 3）。压缩的本质是利用分布的不均匀。

任何无损编码都不可能短于 Shannon entropy 给出的理论下界，而 Huffman 永远紧贴它——每符号差距不到 1 bit。