前缀码

概述

前缀码（Prefix Code）是一组二进制码字，其中没有任何码字是另一个码字的前缀，保证编码可以即时解码（不需要回溯），是数据压缩的基础编码类型。

一组码字 {c₁, c₂, ..., cₙ} 是前缀码，当且仅当对任意 i ≠ j，cᵢ 不是 cⱼ 的前缀。

例如：{0, 10, 110, 1110, 1111} 是前缀码；{0, 01, 011} 不是（0 是 01 的前缀）。

前缀码的最大优势是即时解码：从左到右逐位读取，一旦匹配到一个完整码字就可以立即输出，无需向前查看或回溯。这使得前缀码非常适合流式解码。

每个前缀码可以表示为一棵二叉树： - 叶子节点对应码字 - 从根到叶子的路径（左=0，右=1）即为码字 - 内部节点不对应任何码字

前缀码的码字长度 l₁, l₂, ..., lₙ 必须满足： $$\sum_{i=1}^{n} 2^{-l_i} \leq 1$$

McMillan (1956) 证明这一约束对所有唯一可译码（不限于前缀码）都成立。这意味着在寻找最优唯一可译码时，只需搜索前缀码就够了。

Shannon-Fano 编码（自顶向下划分）不能保证全局最优。Huffman 编码（自底向上贪心）在所有前缀码中是最优的。