Computer Science – Data Structures and Algorithms
Scientific paper
2005-09-06
Computer Science
Data Structures and Algorithms
21 pages, a preliminary version appeared in STACS 2006
Scientific paper
A new method for constructing minimum-redundancy binary prefix codes is described. Our method does not explicitly build a Huffman tree; instead it uses a property of optimal prefix codes to compute the codeword lengths corresponding to the input weights. Let $n$ be the number of weights and $k$ be the number of distinct codeword lengths. The running time of our algorithm is $O(16^k \cdot n)$, which is asymptotically faster than Huffman's algorithm for sufficiently small $k$. If the given weights were presorted, our algorithm requires $O(9^k \cdot \log^{2k-1}{n})$ comparisons, which is sub-linear for sufficiently small $k$.
Belal Ahmed
Elmasry Amr
No associations
LandOfFree
Optimal Prefix Codes with Fewer Distinct Codeword Lengths are Easier to Construct 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 Optimal Prefix Codes with Fewer Distinct Codeword Lengths are Easier to Construct, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Prefix Codes with Fewer Distinct Codeword Lengths are Easier to Construct will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-375297