克拉夫特不等式

在编码理论，克拉夫特不等式给出了一个码字长度集合存在唯一可解编码/单义可译码（uniquely decodable code）的必要条件。因为这个不等式在前缀码和树上面应用很多，所以在计算机科学和信息学中很常用。

克拉夫特不等式对码字限制长度以保证前缀编码的可能性。这个不等式说明码字长度指数的倒数的分布和概率质量函数很相似。克拉夫特不等式can be thought of in terms of a constrained budget to be spent on codewords, with shorter codewords being more expensive.

• 如果克拉夫特不等式中严格成立，相应的编码有冗余（redundancy）。
• 如果克拉夫特不等式中等式成立，相应的编码被称作complete code。
• 如果克拉夫特不等式不成立，相应的编码不是唯一可解编码（uniquely decipherable）。

定义

设符号表中的原始符号为

$S=\{\,s_{1},s_{2},\ldots ,s_{n}\,\}$

在大小为$r$的字符集上编码为唯一可解编码的码字长度为

$\ell _{1},\ell _{2},\ldots ,\ell _{n}.$

则

$\sum _{i=1}^{n}r^{-\ell _{i}}\leqslant 1.$

反之, 给定一个满足上述不等式的自然数集合 $\ell _{1},\ell _{2},\ldots ,\ell _{n}$ , 则在大小为$r$字符集上，存在一组唯一可解编码符合相应的码字长度。

外部链接

• Kraft's inequality (NIST) （页面存档备份，存于互联网档案馆）