Algorithms for Infinite Huffman-Codes
Ma Kin Keung
HKUST
Friday, Feb 27, 11-2, room 3464





Abstract
--------
Optimal (minimum cost) binary prefix-free codes for infinite sources with
geometrically distributed frequencies, e.g., P = { p^i (1-p) }, were first
(implicitly) suggested by Golomb over thirty years ago in the context of
run-length encodings. Previous work on this problem were non-algorithmic
and very restricted in their applicability. In this talk I will present
the first algorithmic technique for constructing minimum-cost prefix-free
codes. This new technique is applicable to many generalizations of Huffman
coding, e.g., unequal cost letters and restrictions on codewords, that the
previously known technique could not work on. This new technique also works
for a larger set of generalizations of geometric sources than could be
solved for previously.

This is joint work with Mordecai Golin.