The WARM-UP Algorithm: A Lagrangian Construction of Length Restricted Huffman Codes
Authors:
- Ruy Luiz MilidiúRMRuy Luiz Milidiú
- Eduardo Sany LaberELEduardo Sany Laber
- 1 January 2000
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 30 (5) , 1405-1426
Abstract
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.
Keywords
This publication has 23 references indexed in Scilit:
- Efficient construction of minimum-redundancy codes for large alphabetsIEEE Transactions on Information Theory, 1998
- Constructing Huffman Trees in ParallelSIAM Journal on Computing, 1995
- Finding a minimum-weightk-link path in graphs with the concave Monge property and applicationsDiscrete & Computational Geometry, 1994
- Bounding the Depth of Search TreesThe Computer Journal, 1993
- A fast algorithm for optimal length-limited Huffman codesJournal of the ACM, 1990
- Applying Parallel Computation Algorithms in the Design of Serial AlgorithmsJournal of the ACM, 1983
- Variations on a theme by HuffmanIEEE Transactions on Information Theory, 1978
- Optimal Binary Search Trees with Restricted Maximal DepthSIAM Journal on Computing, 1974
- Path Length of Binary Search TreesSIAM Journal on Applied Mathematics, 1972
- Codes based on inaccurate source probabilitiesIEEE Transactions on Information Theory, 1971