克拉夫特不等式

在編碼理論，克拉夫特不等式給出了一個碼字長度集合存在唯一可解編碼/單義可譯碼（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) （頁面存檔備份，存於互聯網檔案館）