An efficient algorithm for constructing nearly optimal prefix codes

Kurt MehlhornIEEE Trans. Information Theory 1980 · OpenReview

Abstract

A new algorithm is presented for constructing nearly optimal prefix codes in the case of unequal letter costs and unequal probabilities. A bound on the maximal deviation from the optimum is derived and numerical examples are given. The algorithm has running time <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(t \cdot n)</tex> , where <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</tex> is the number of letters and <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</tex> is the number of probabilities.
BibTeX
@article{mehlhorn1980efficient,
  author = {Kurt Mehlhorn},
  title = {{An efficient algorithm for constructing nearly optimal prefix codes}},
  journal = {IEEE Trans. Information Theory},
  year = {1980},
  url = {https://openreview.net/forum?id=tZopeWESL5o},
}

Loading related content...

Figure