AG 1, AG 4, RG1, MMCI, AG 3, AG 5, SWS   Info

AG Audience

English

30 Minutes

Saarbrücken

A new method for constructing minimum-redundancy prefix codes is described. This method does not explicitly build a Huffman tree; instead it uses a property of optimal codes to find the codeword length of each weight. The running time of the algorithm is shown to be $O(n k)$, which is asymptotically faster than Huffman's algorithm when $k=o(\log{n})$, where $n$ is the number of weights and $k$ is the number of distinct codeword lengths.

We also sketch a matching lower bound of $\Omega(n k)$ for any such construction algorithm, indicating that our algorithm is asymptotically optimal in terms of $n$ and $k$.

Amr Elmasry

--email hidden

passcode not visible

logged in users only

Prefix codes - Huffman tree - Distribution-sensitive algorithms