在编码理论,克拉夫特不等式给出了一个码字长度集合存在唯一可解编码/单义可译码(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)。
定义
设符号表中的原始符号为
在大小为的字符集上编码为唯一可解编码的码字长度为
则
反之, 给定一个满足上述不等式的自然数集合 , 则在大小为字符集上,存在一组唯一可解编码符合相应的码字长度。
外部链接
Wikiwand in your browser!
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.