Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/477
Algorithms for Infinite HuffmanCodes
Authors  Golin, Mordecai
Ma, KinKeung 


Issue Date  20032004  
Source  Proceedings of the ACMSIAM Symposium on Discrete Algorithms (SODA'04). 2004  
Summary  Optimal (minimum cost) binary prefixfree codes for infinite sources with geometrically distributed frequencies, e.g., P = {pi(1  p)}∞i=0, 0 < p < 1, were first (implicitly) suggested by Golomb over thirty years ago in the context of runlength encodings. Ten years later Gallager and Van Voorhis exhibited such optimal codes for all values of p. Just recently Merhav, Seroussi and Weinberger extended this further to find optimal binary prefixfree codes for twosided geometric distributions. These codes were derived by cleverly "guessing" optimal codes for finite sources, validating these guesses by using the sibling property of Huffman encoding, and then showing that the finite codes converge in a very specific sense to an optimal infinite one. In this paper we describe the first algorithmic approach to constructing optimal prefixfree infinite codes. Our approach is to define an infinite weighted graph with the property that the least cost infinite path in the graph corresponds to the optimal code. We then show that even though the graph is infinite, the leastcost infinite path has a repetitive structure and that it is therefore possible to not only find this path but to find it relatively efficiently. This approach will work for even more complicated generalizations of geometric sources where solutions can't be guessed as well as in extensions of Huffmancoding for which the Huffman algorithm no longer works, e.g., nonuniform cost encoding alphabet characters and/or other restrictions on the codewords. We illustrate our approach by deriving an algorithm for constructing optimal prefix free codes with a geometric source for the telegraph channel. We also implement our algorithm and show what the constructed codes look like in this case.  
Subjects  
Language  English 

Format  Conference paper  
Access 
Files in this item:
