克拉夫特不等式

編碼理論克拉夫特不等式給出了一個碼字長度集合存在唯一可解編碼/單義可譯碼uniquely decodable code)的必要條件。因為這個不等式在前綴碼上面應用很多,所以在計算機科學信息學中很常用。

克拉夫特不等式對碼字限制長度以保證前綴編碼的可能性。這個不等式說明碼字長度指數的倒數的分佈和概率質量函數很相似。克拉夫特不等式can be thought of in terms of a constrained budget to be spent on codewords, with shorter codewords being more expensive.

定義

設符號表中的原始符號為

 

在大小為 的字符集上編碼為唯一可解編碼碼字長度為

 

 

反之, 給定一個滿足上述不等式的自然數集合   , 則在大小為 字符集上,存在一組唯一可解編碼符合相應的碼字長度。

外部連結