查看“︁克拉夫特不等式”︁的源代码

在[[编码理论]]，'''克拉夫特不等式'''给出了一个[[码字]]长度集合存在[[唯一可解编码]]/[[单义可译码]]（[[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]]）。

== 定义 ==
设符号表中的原始符号为
:<math>S=\{\,s_1,s_2,\ldots,s_n\,\}</math>

在大小为<math>r</math>的字符集上编码为[[唯一可解编码]]的[[码字]]长度为

:<math>\ell_1,\ell_2,\ldots,\ell_n.</math>

则

:<math>\sum_{i=1}^{n} r^{-\ell_i} \leqslant 1.</math>

反之, 给定一个满足上述不等式的自然数集合 <math>\ell_1,\ell_2,\ldots,\ell_n</math> , 则在大小为<math>r</math>字符集上，存在一组[[唯一可解编码]]符合相应的[[码字]]长度。

== 外部連結 ==
* [http://www.nist.gov/dads/HTML/kraftsinqlty.html Kraft's inequality (NIST)] {{Wayback|url=http://www.nist.gov/dads/HTML/kraftsinqlty.html |date=20090127030544 }}

[[Category:编码理论]]
[[Category:不等式]]