Computer Science – Information Theory
Scientific paper
2007-05-02
Computer Science
Information Theory
29 pages;9 figures;
Scientific paper
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.
Golin Mordecai
Jian Li
No associations
LandOfFree
More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-674569