Maximal codeword lengths in Huffman codes

Abstract

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 ≤12, and if K is the unique index such that 1F_(K+3)< p ≤1F_(K+2), where F_K denotes the Kth 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.

Additional details