A DYNAMIC-PROGRAMMING ALGORITHM FOR CONSTRUCTING OPTIMAL PREFIX-FREE CODES WITH UNEQUAL LETTER COSTS

We consider the problem of constructing prefix-free codes of minimum c ost when the encoding alphabet contains letters of unequal length. The complexity of this problem has been unclear for thirty years with the only algorithm known for its solution involving a transformation to i nteger linear programming. In this paper we introduce a new dynamic pr ogramming solution to the problem. It optimally encodes n words in O ( n(C+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 o ne that runs in polynomial time for fixed letter costs.