Loading AI tools
来自维基百科,自由的百科全书
在編碼理論,克拉夫特不等式給出了一個碼字長度集合存在唯一可解編碼/單義可譯碼(uniquely decodable code)的必要條件。因為這個不等式在前綴碼和樹上面應用很多,所以在計算機科學和信息學中很常用。
克拉夫特不等式對碼字限制長度以保證前綴編碼的可能性。這個不等式說明碼字長度指數的倒數的分布和概率質量函數很相似。克拉夫特不等式can be thought of in terms of a constrained budget to be spent on codewords, with shorter codewords being more expensive.
設符號表中的原始符號為
在大小為的字符集上編碼為唯一可解編碼的碼字長度為
則
反之, 給定一個滿足上述不等式的自然數集合 , 則在大小為字符集上,存在一組唯一可解編碼符合相應的碼字長度。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.