Paper Info
Title
The WARM-UP Algorithm: A Lagrangian Construction of Length Restricted Huffman Codes
Abstract
Given an alphabet {a,1, . . . ,an} with the corresponding list of weights [w1, . . . ,wn], 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.
Year
DOI
Venue
2000
10.1137/S009753979731981X
SIAM J. Comput.
Keywords
DocType
Volume
corresponding list,warm-up algorithm,lagrangian construction,length restricted huffman codes,huffman tree construction,huffman encoding,nl log,proposed algorithm,log n,additional bit,time complexity,lagrangian algorithm,huffman codes,golden ratio
Journal
30
Issue
ISSN
Citations 
5
0097-5397
9
PageRank 
References 
Authors
0.84
13
2
Name
Order
Citations
PageRank
Ruy Luiz Milidiú119220.18
Eduardo Sany Laber222927.12