Faster Algorithm for Designing Optimal Prefix-Free Codes with Unequal Letter Costs
Titel:
Faster Algorithm for Designing Optimal Prefix-Free Codes with Unequal Letter Costs
Auteur:
Dumitrescu, Sorina
Verschenen in:
Fundamenta informaticae
Paginering:
Jaargang 73 (2006) nr. 1-2 pagina's 107-117
Jaar:
2006-08-28
Inhoud:
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.
Tijdschrift beschrijving