We address the problem of designing optimal prefix-free codes over
an encoding alphabet with unequal integer letter costs. The most efficient
algorithm proposed so far has O(n
^{C+2}
) time complexity,
where n is the number of codewords and C is the maximum letter cost. For the
special case when the encoding alphabet is binary, a faster solution was
proposed, namely of O(n
^C
) time complexity, based on a more
sophisticated modeling of the problem, and on exploiting the Monge property of
the cost function. However, those techniques seemed not to extend to the
r-letter alphabet. This work proves that, on the contrary, the generalization
to the r-letter case is possible, thus leading to a O(n
^C
)
time complexity algorithm for the case of arbitrary number of letters.
