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

More efficient algorithms and analyses for unequal letter cost prefix-free coding

Authors Golin, Mordecai View this author's profile
Li, Jian
Issue Date 2008
Source IEEE transactions on information theory , v. 54, (8), 2008, AUG, p. 3412-3424
Summary There is a large literature devoted to the problem of finding an optimal (min-cost) prefix-free code with an unequal letter-cost encoding alphabet of size. While there is no known polynomial time algorithm for solving it optimally, there are many good heuristics that all provide additive errors to optimal. The additive error in these algorithms usually depends linearly upon the largest encoding letter size. This paper was motivated by the problem of finding optimal codes when the encoding alphabet is infinite. Because the largest letter cost is infinite, the previous analyses could give infinite error bounds. We provide a new algorithm that works with infinite encoding alphabets. When restricted to the finite alphabet case, our algorithm often provides better error bounds than the best previous ones known.
ISSN 0018-9448
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus