|
HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1783.1/702
|
| Title: | Optimal prefix-free codes for unequal letter costs : dynamic programming with the Monge property |
| Authors: | Bradford, Phil
Golin, Mordecai J.
Larmore, Lawrence L.
Rytter, Wojciech |
| Keywords: | Dynamic programming
Huffman codes
Lopsided trees
Monge matrix
Monotone matrix
Prefix-free codes |
| Issue Date: | 2000 |
| Series/Report no.: | HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2000-05 |
| Abstract: | In this paper we discuss the problem of finding optimal prefix-free codes for unequal letter costs, a variation of the classical Huffman coding problem. Our problem consists of finding a minimal cost prefix-free code in which the encoding alphabet consists of unequal cost (length) letters, with lengths α and β. The most efficient algorithm known previously requires O(n2+max(α,β)) time to construct such a minimal-cost set of n codewords, provided α and β are integers. In this paper we provide an O(nmax(α,β)) time algorithm. Our improvement comes from the use of a more sophisticated modeling of the problem, combined with the observation that the problem possesses a "Monge property" and that the SMAWK algorithm on monotone matrices can therefore be applied. |
| URI: | http://hdl.handle.net/1783.1/702 |
| Appears in Collections: | CSE TCSC Research Reports
|
Files in This Item:
| File |
Description |
Size | Format |
|---|
| 200005.pdf | | 349Kb | Adobe PDF | View/Open |
|
All items in this Repository are protected by copyright, with all rights reserved.
|
