Mordecai J. Golin and Günter Rote:
A dynamic programming algorithm for constructing optimal prefix-free
codes
for unequal letter costs
- 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.
- IEEE Transactions on Information Theory 44
(1998),
1770-1781.
Abstract
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.
Last update: April 4, 2002.