✦ LIBER ✦
Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property
✍ Scribed by Phil Bradford; Mordecai J. Golin; Lawrence L. Larmore; Wojciech Rytter
- Publisher
- Elsevier Science
- Year
- 2002
- Tongue
- English
- Weight
- 293 KB
- Volume
- 42
- Category
- Article
- ISSN
- 0196-6774
No coin nor oath required. For personal study only.
✦ Synopsis
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 n 2+max α β time to construct such a minimal-cost set of n codewords, provided α and β are integers. In this paper