Maximal codeword lengths in Huffman codes

✍ Scribed by Y.S. Abu-Mostafa; R.J. McEliece

• Book ID: 104351825
• Publisher: Elsevier Science
• Year: 2000
• Tongue: English
• Weight: 332 KB
• Volume: 39
• Category: Article
• ISSN: 0898-1221
• DOI: 10.1016/s0898-1221(00)00119-x

✦ Synopsis

In this paper, we consider the following question about Huffman coding, which is an important technique for compressing data from a discrete source. If p is the smallest source probability, how long, in terms of p, can the longest Huffman codeword be? We show that if p is in the range 0 < p <_ 1/2, and if K is the unique index such that 1/F/¢+3 < p < 1/FK+2, where FK denotes the K th Fibonacci number, then the longest Huffman codeword for a source whose least probability is p is at most K, and no better bound is possible. Asymptotically, this implies the surprising fact that for small values of p, a Huffman code's longest codeword can be as much as 44% larger than that of the corresponding Shannon code. (~) 2000 Elsevier Science Ltd. All rights reserved.