Mordecai J. Golin and Günter Rote:
A dynamic programming algorithm for constructing optimal prefix-free
for unequal letter costs
- Extended abstract in: "Automata, Languages and Programming".
of the 22nd International Colloquium on Automata, Languages, and
(ICALP 95), Szeged, Hungary, July 1995. Editor: F. Gécseg.
Notes in Computer Science 944, Springer-Verlag, 1995, pp. 256-267.
- IEEE Transactions on Information Theory 44
We consider the problem of constructing minimum cost prefix-free codes
when the encoding alphabet contains letters of unequal length. The
of this problem has been unclear for thirty years. The only algorithm
for its solution involves a reduction to integer linear programming,
to Karp (1961).
In this paper we introduce a dynamic programming solution to the
It optimally encodes n words in O(nC+2)
if the costs of the letters are integers between 1 and C. While
still leaving open the question of whether the general problem is
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
integer programming formulations, which was solved using AMPL and
The AMPL model is included in the appendix and in the PostScript-file.
Last update: April 4, 2002.