More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding

DOI10.1007/978-3-540-77120-3_30MaRDI QIDQ5387768zbMATH OpenOpenAlexFDO

Authors Jian Li, Mordecai J. Golin

Publication date 27 May 2008

Published in Algorithms and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0705.0253

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Prefix, length-variable, comma-free codes (94A45)

Abstract: 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.

Recommendations

• More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding
• A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs
• Faster algorithm for designing optimal prefix-free codes with unequal letter costs
• A dynamic programming algorithm for constructing optimal prefix-free codes with unequal letter costs
• Prefix codes: equiprobable words, unequal letter costs

Cites work

• A dynamic programming algorithm for constructing optimal prefix-free codes with unequal letter costs
• A Mathematical Theory of Communication
• A Method for the Construction of Minimum-Redundancy Codes
• An efficient algorithm for constructing nearly optimal prefix codes
• Binary prefix codes ending in a "1"
• Channels which transmit letters of unequal duration
• Code and parse trees for lossless source encoding
• Codes: Unequal Probabilities, Unequal Letter Cost
• Coding with digits of unequal cost
• scientific article; zbMATH DE number 3162350 (Why is no real title available?)
• scientific article; zbMATH DE number 3093781 (Why is no real title available?)
• Huffman coding with unequal letter costs
• More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding
• Optimal Alphabetic Trees
• Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property
• Optimum '1'-ended binary prefix codes
• Simple proofs of some theorems on noiseless channels
• Variable length tree structures having minimum average search time

Cited in

(6)

• Faster algorithm for designing optimal prefix-free codes with unequal letter costs
• More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding
• Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property
• Coding with digits of unequal cost
• More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding
• Bounding the inefficiency of length-restricted prefix codes

This page was built for publication: More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5387768)