Maximal codeword lengths in Huffman codes

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...

Full description

Saved in:
Bibliographic Details
Published in:Computers & mathematics with applications (1987) 2000, Vol.39 (11), p.129-134
Main Authors: Abu-Mostafa, Y.S., McEliece, R.J.
Format: Article
Language:English
Subjects:
Data compression
Fibonacci numbers
Huffman codes
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 K+3 < p ≤ 1 F K+2 , where F K 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.
ISSN:0898-1221
1873-7668
DOI:10.1016/S0898-1221(00)00119-X