Please use this identifier to cite or link to this item:

Algorithms for Infinite Huffman-Codes

Authors Golin, Mordecai View this author's profile
Ma, Kin-Keung HKUST affiliated (currently or previously)
Issue Date 2003-2004
Source Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA'04). 2004
Summary Optimal (minimum cost) binary prefix-free 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 run-length 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 prefix-free codes for two-sided 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 prefix-free 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 least-cost 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 Huffman-coding for which the Huffman algorithm no longer works, e.g., non-uniform 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.
Language English
Format Conference paper
Files in this item:
File Description Size Format
Inf_Alg_SODA04.pdf 226786 B Adobe PDF