Huffman 编码树 · 拆解 huffman coding
「常见的字符编短、罕见的编长」是无损压缩的基本思路。本系列从 fixed-length code 的浪费出发, 用 priority queue 逐步合并建出 Huffman 树, 再理解 prefix code 为何能无歧义地走树解码, 最后考察它在 gzip / PNG / JPEG / MP3 中的实际使用。每页都能改输入、点单步、逐 bit 看树上的下降路径。 建树依赖「反复取最小」这一操作, 不熟悉时可先看优先队列系列。
为什么 fixed-length code 浪费
改一句话的字符 frequency，实时对比「每字符 8 bit 的 ASCII」与「按 frequency 定制的 variable-length code」各占多少 bit，并标出 Shannon entropy 这条理论下界。
动手建树：每次合并两个最小
核心算法。把字符摆成一排 priority queue，点「下一步」逐步取出 frequency 最小的两点合并、回插，看树自底向上一点点长出来，直到只剩根。
prefix code 与解码：为何唯一可解
编码把每个字符替换成它的 codeword；解码则从根开始逐 bit 下降，到叶子输出一个字符再回根。逐 bit 高亮树上路径，直观理解「没有 codeword 是另一个的前缀」如何保证唯一可解。
应用实例：它的实际使用场景
一个实时压缩 demo（贴文本看压缩率 vs entropy），外加四个真实场景拆解：DEFLATE(gzip/zlib/PNG)、JPEG、MP3/AAC、以及 canonical Huffman 与「为何现代格式开始用 ANS / 算术编码」。
石子合并：压缩之外，同一个 Huffman
几堆石子两两合并、代价为两堆之和，求最小总代价——其实就是 Huffman 建树。切换「最小优先 / 最大优先」单步合并，看顺序如何决定总代价，并理解它和「连接绳子 / 多路归并」是同一个内核。
hierarchical softmax：把 Huffman 树搬进神经网络
word2vec 用 Huffman 树把 O(V) 的 softmax 拆成 ≈log V 次二选一。点词看「路径=σ 决策序列」，对比扁平 vs 平衡树 vs Huffman 的每步计算量；再看一串 σ 相乘为何自动 normalize、省掉对 V 个词的归一化。在这里，深度对应的代价是 GPU 上的乘加次数。