为什么 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 就没有优势——这时 entropy 正好等于紧凑 fixed-length code，Huffman 退化成 fixed-length code。压缩的本质是利用分布的不均匀。

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