HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE Conference Papers >

Please use this identifier to cite or link to this item:
Title: Algorithms for infinite Huffman-codes
Authors: Golin, Mordecai J.
Ma, Kin Keung
Keywords: Algorithms
Infinite Huffman codes
Optimal prefix free codes
Issue Date: 2004
Citation: ACM - SIAM Symposium on Discrete Algorithms, New Orleans, 2004, SIAM, Society for Industrial and Applied Mathematics, Philadelphia, USA, 2004
Abstract: 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.
Appears in Collections:CSE Conference Papers

Files in This Item:

File Description SizeFormat
Inf_Alg_SODA04.pdf221KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.