A Fast Algorithm For Optimum Height-Limited Alphabetic Binary Trees
Authors:
- Lawrence L. LarmoreLLLawrence L. Larmore
- Teresa M. PrzytyckaTPTeresa M. Przytycka
- 1 December 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 23 (6) , 1283-1312
Abstract
In this paper, an $O(nL\log n)$-time algorithm is presented for construction of an optimal alphabetic binary tree with height restricted to L. This algorithm is an alphabetic version of the Package Merge algorithm, and yields an $O(nL\log n)$-time algorithm for the alphabetic Huffman coding problem. The Alphabetic Package Merge algorithm is quite simple to describe, but appears hard to prove correct. Garey [SIAM J Comput., 3 (1974), pp. 101–110] gives an $O(n^3 \log n)$-time algorithm for the height-limited alphabetic binary tree problem. Itai [SIAM J. Comput., 5 (1976), pp. 9–18] and Wessner [Inform. Process. Lett., 4 (1976), pp. 90–94] independently reduce this time to $O(n^2 L)$ for the alphabetic problem. In [SIAM J. Comput., 16 (1987), pp. 1115–1123], a rather complex $O(n^{{3 / 2}} L\log ^{{1 / 2}} n)$ -time “hybrid” algorithm is given for length-limited Huffman coding. The Package Merge algorithm, discussed in this paper, first appeared in [Tech. Report, 88-01, ICS Dept. Univ. of California, Irvine, CA], but without proof of correctness.
Keywords
This publication has 12 references indexed in Scilit:
- Efficient Parallel Algorithms for String Editing and Related ProblemsSIAM Journal on Computing, 1990
- A fast algorithm for optimal length-limited Huffman codesJournal of the ACM, 1990
- Height Restricted Optimal Binary TreesSIAM Journal on Computing, 1987
- A New Algorithm for Minimum Cost Binary TreesSIAM Journal on Computing, 1977
- Optimal Alphabetic TreesSIAM Journal on Computing, 1976
- Optimal alphabetic search trees with restricted maximal heightInformation Processing Letters, 1976
- Optimal Binary Search Trees with Restricted Maximal DepthSIAM Journal on Computing, 1974
- Optimal Computer Search Trees and Variable-Length Alphabetical CodesSIAM Journal on Applied Mathematics, 1971
- Codes based on inaccurate source probabilitiesIEEE Transactions on Information Theory, 1971
- Optimum binary search treesActa Informatica, 1971