Kraft不等式

概述

Kraft 不等式指出前缀码的码字长度 l₁, ..., lₙ 必须满足 Σ 2^(-lᵢ) ≤ 1，McMillan (1956) 将其推广到所有唯一可译码，确定了前缀码码长的可行空间。

$$\sum_{i=1}^{n} 2^{-l_i} \leq 1$$

McMillan (1956) 证明：Kraft 不等式对所有唯一可译码（uniquely decodable codes），而不仅仅是前缀码，都成立。这意味着在寻找最优唯一可译码时，只需搜索前缀码就够了——Huffman 编码因此是所有唯一可译码中最优的。

把每个码字想象成二叉树中的一条路径。2^(-lᵢ) 是深度为 lᵢ 的节点占整棵二叉树"空间"的比例。所有码字占的空间之和不能超过 1（整棵树）。