|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE Master Theses >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/5650
|
| Title: | Variants of prefix-free codes |
| Authors: | Chan, Sze-Lok |
| Issue Date: | 1997 |
| Abstract: | 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. |
| Description: | Thesis (M.Phil.)--Hong Kong University of Science and Technology, 1997
ix, 110 leaves : ill. ; 30 cm
HKUST Call Number: Thesis COMP 1997 ChanSL |
| URI: | http://hdl.handle.net/1783.1/5650 |
| Appears in Collections: | CSE Master Theses
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| th_redirect.html | | 0Kb | HTML | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
