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

Variants of prefix-free codes

Authors Chan, Sze-Lok
Issue Date 1997
Summary The classic Hufman Coding Problem of finding a minimum cost prefix-free code is almost completely understood. There still exist many variants of this problem which are not as well understood. In this thesis we consider four variants. The first variant requires that none of the codewords ends with a "1". In the literature, the best algorithm known for finding such codes runs in exponential time. The second variant requires that none of the codewords contains "000" as a substring. In the third variant, the size of the encoding alphabets depends on the position of the alphabets within the codewords. In this thesis we use similar approachs to develop simple dynamic programming algorithms for solving these three problems. The running times are O(n3), O(n5) and O(n4) respectively. The fourth variant, requires that the difference between the length of the longest codeword and the shortest codeword can be at most L. In this thesis we develop a simple O(nLlogn) algorithm for solving this problem.
Note Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1997
Language English
Format Thesis
Access View full-text via DOI
Files in this item:
File Description Size Format
th_redirect.html 345 B HTML