Optimal Prefix Codes with Fewer Distinct Codeword Lengths are Faster to Construct
<|reference_start|>Optimal Prefix Codes with Fewer Distinct Codeword Lengths are Faster to Construct: 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 as produced by the algorithm for the optimum codes. The running time of our algorithm is $O(k \cdot n)$. Following our previous work in \cite{be}, no algorithm can possibly construct optimal prefix codes in $o(k \cdot n)$ time. When the given weights are presorted our algorithm performs $O(9^k \cdot \log^{2k}{n})$ comparisons.<|reference_end|>
@article{belal2005optimal,
    title={Optimal Prefix Codes with Fewer Distinct Codeword Lengths are Faster to
  Construct},
    author={Ahmed Belal and Amr Elmasry},
    journal={arXiv preprint arXiv:cs/0509015},
    year={2005},
    archivePrefix={arXiv},
    eprint={cs/0509015},
    primaryClass={cs.DS cs.IT math.IT}
}