prefix code 与解码：为何唯一可解

variable-length code 有一个直接的问题：codeword 长短不一，中间又不加分隔符，解码器必须能确定一个 codeword 到哪里结束、下一个从哪里开始。Huffman code 天生是 prefix code (prefix-free)：没有任何一个字符的 codeword，是另一个字符 codeword 的前缀，因此边界唯一确定。

之所以天生满足，是因为字符只在叶子上（树由动手建树一页的算法建出）。从根往下走，经过的内部 node 都不是任何字符，只有走到叶子才「落地」成一个字符——而叶子之间互不为祖先，路径自然互不为前缀。于是解码变成一件机械的事：从根开始，读一个 bit 就往左 (0) 或往右 (1) 走一步，一碰到叶子就输出这个字符、回到根，不会有歧义。

1 · 编码：字符 → codeword，首尾相接

把消息里每个字符换成它的 codeword，直接拼起来即可。下面每个字符的 bit 段用深浅交替标出。

2 · 解码：从根逐 bit 下降，到叶子就落地

点「下一步」读入一个 bit，看蓝色路径在树上一步步下降；一旦到达叶子（蓝色实心圈），就输出一个字符并跳回根重新开始。注意：解码过程不需要「往回看」或猜测——走到叶子那一刻就唯一确定了一个字符，这正是 prefix code 的作用。