Kraft–McMillan 不等式

在无限 $D$ 叉树中，深度 $\ell$ 的一个码字封锁其全部后代，占据总边界空间的 $D^{-\ell }$。前缀码对应互不相交的子树，所以占用比例之和不能超过一。反过来，只要总占用不超过一，就能按长度从短到长把这些子树塞进尚未使用的树空间。

这个不等式只看到长度多重集，看不到具体码符号，也看不到哪个源符号获得哪一长度。可行性与概率加权的最优分配是两个不同问题。

前缀码部分的证明机制 ​

令 $L=\underset{i}{max}{\ell }_i$。把每个长度 ${\ell }_i$ 的码字延伸到深度 $L$，会得到 $D^{L-{\ell }_i}$ 个后代。前缀自由使这些后代集合互不相交，而深度 $L$ 总共只有 $D^L$ 个节点，因此

两边除以 $D^L$ 即得 Kraft 不等式。充分性可把长度排序后按字典序依次选择最左侧尚未被占用的节点；$K\le 1$ 保证每一步都有足够的树空间。

McMillan 部分的证明机制 ​

令 $K=\sum _i{D}^{-{\ell }_i}$。串联 $N$ 个源符号后，全部长度权重之和是 $K^N$。唯一可译性保证不同源串产生不同码串；若最短、最长码长为 $a,b$，总长度只能落在 $Na,\dots ,Nb$。对每个总长度 $r$，至多有 $D^r$ 个不同码串，故该组对 $K^N$ 的贡献至多为 $D^r{D}^{-r}=1$。于是

取 $N$ 次方根并令 $N\to \mathrm{\infty }$，得到 $K\le 1$。

可复算例：可行与不可行长度 ​

二元长度 $(1,2,3,3)$ 满足

可由 0,10,110,111 实现。长度 $(1,2,2,2)$ 则给

所以不存在具有这些长度的二元前缀码，甚至不存在唯一可译码。

边界与失败情形 ​

$K<1$ 仍可行，只表示码树未满；$K=1$ 也不说明码对给定概率分布最优。对 $D$ 元代码必须使用 $D^{-{\ell }_i}$，不能沿用二元的 $2^{-{\ell }_i}$。

允许长度零时，空码字占用 $D^0=1$ 的全部容量，因此集合意义的前缀码只能是 $\{\epsilon \}$。这仍满足 Kraft 的集合与长度结论，却不能表示未知次数的重复源符号；把它用于单符号源须由外部固定消息数或单块边界。前面的 McMillan 及唯一可译长度等价陈述采用正码长。码长还必须是整数，实数解 ${\ell }_i=-{\log }_D{p}_i$ 即使满足形式上的等式，也未必是实际逐符号码长。

把 Kraft 约束与概率 $p_i$ 结合，令 $q_i=D^{-{\ell }_i}/K$，可用KL 非负性理路KL 散度Kullback–Leibler divergence · Relative entropy同一可测空间上分布 P 相对于 Q 的对数 Radon–Nikodym 导数在 P 下的积分。证明任意唯一可译码的平均长度满足

Huffman 编码理路Huffman 编码Huffman coding反复合并最低概率符号构造期望码长最小前缀码的算法。在整数可行长度中求精确的逐符号最优解；无噪声编码定理理路无噪声编码定理Source coding theorem · Noiseless coding theorem独立同分布信源的无损压缩平均码率可以逼近但不能低于其熵。则对长块应用同一约束，把每符号整数舍入损失压到零。

对于程序依次枚举、次序可能无规则的可数编码请求，不能预先排序全部码长。Kraft–Chaitin 构造理路前缀复杂度与 Levin–Schnorr 定理Prefix-free Kolmogorov complexity · Levin–Schnorr theorem · Kraft–Chaitin theorem · 前缀 Kolmogorov 复杂度构造通用前缀机与 Kraft–Chaitin 在线编码，证明无限序列的 Martin-Löf 随机性等价于所有前缀的压缩亏损有统一常数界。维护每种长度至多一个空闲子树，在同一 Kraft 预算下在线分配程序；这把静态码长条件转成有效压缩，并用于证明 Levin–Schnorr 定理。

在算法编码定理理路算法编码定理Algorithmic coding theorem · Levin coding theorem证明通用离散算法概率的负对数等于前缀复杂度加常数，并用阈值编码展示如何把可枚举质量变成短描述。中，Kraft 预算不只约束一份静态码表。下半可计算质量每跨过一个二进阈值，就发出一个新码长请求；所有请求的权重仍有统一上界，因此可在线分配前缀码，得到算法概率的负对数与前缀复杂度相差常数。