Computer Science – Data Structures and Algorithms
Scientific paper
2008-09-26
Computer Science
Data Structures and Algorithms
Scientific paper
Given a probability distribution over a set of n words to be transmitted, the Huffman Coding problem is to find a minimal-cost prefix free code for transmitting those words. The basic Huffman coding problem can be solved in O(n log n) time but variations are more difficult. One of the standard techniques for solving these variations utilizes a top-down dynamic programming approach. In this paper we show that this approach is amenable to dynamic programming speedup techniques, permitting a speedup of an order of magnitude for many algorithms in the literature for such variations as mixed radix, reserved length and one-ended coding. These speedups are immediate implications of a general structural property that permits batching together the calculation of many DP entries.
Golin Mordecai
Xu Xiaoming
Yu Jiajin
No associations
LandOfFree
A Generic Top-Down Dynamic-Programming Approach to 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 A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Generic Top-Down Dynamic-Programming Approach to Prefix-Free Coding will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-712721