The WARM-UP Algorithm: A Lagrangian Construction of Length Restricted Huffman Codes
Ruy Luiz Milidiú, Eduardo Sany Laber · SIAM Journal on Computing · 2000
Given an alphabet {a, 1 , . . . ,a n } with the corresponding list of weights [w 1 , . . . ,w n ], and a number $L \geq \lceil \log n \rceil $, we introduce the WARM-UP algorithm, a Lagrangian algorithm for constructing suboptimal length restricted prefix codes. Two implementations of the algorithm are proposed. The first one has time complexity $ O(n \log n + n \log \fMax) $, where {\mbox{$\overline{w}$} } is the highest presented weight. The second one runs in O(nL log (n/L)) time. The number of additional bits per symbol generated by WARM-UP when comparing to Huffman encoding is not greater than ${1/ \psi^{L-\lceil \log (n+ \lceil \log n \rceil -L) \rceil-2}}$. Even though the algorithm is approximated it presents an optimal behavior for practical settings. An important feature of the proposed algorithm is its implementation simplicity. The algorithm is basically a selected sequence of Huffman tree constructions for modified weights. The approach gives some new insights on the problem.