Mordecai J. Golin and Günter Rote:

A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs

  1. Extended abstract in: "Automata, Languages and Programming". Proceedings of the 22nd International Colloquium on Automata, Languages, and Programming (ICALP 95), Szeged, Hungary, July 1995. Editor: F. Gécseg. Lecture Notes in Computer Science 944, Springer-Verlag, 1995, pp. 256-267.
  2. IEEE Transactions on Information Theory 44 (1998), 1770-1781.


We consider the problem of constructing minimum cost prefix-free codes when the encoding alphabet contains letters of unequal length. The complexity of this problem has been unclear for thirty years. The only algorithm known for its solution involves a reduction to integer linear programming, due to Karp (1961).

In this paper we introduce a dynamic programming solution to the problem. It optimally encodes n words in O(nC+2) time, if the costs of the letters are integers between 1 and C. While still leaving open the question of whether the general problem is solvable in polynomial time our algorithm seems to be the first one that runs in polynomial time for fixed letter costs.

Some numerical results are reported, including solutions using Karp's integer programming formulations, which was solved using AMPL and CPLEX. The AMPL model is included in the appendix and in the PostScript-file.

  PostScript file (gzipped)   pdf file (gzipped)   TeX .dvi file (gzipped)
other papers about this subject
Last update: April 4, 2002.