A fast algorithm for optimal length-limited Huffman codes
- 1 July 1990
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 37 (3) , 464-473
- https://doi.org/10.1145/79147.79150
Abstract
An O ( nL )-time algorithm is introduced for constructing an optimal Huffman code for a weighted alphabet of size n , where each code string must have length no greater than L . The algorithm uses O ( n ) space.Keywords
This publication has 10 references indexed in Scilit:
- Minimum Delay CodesSIAM Journal on Computing, 1989
- Height Restricted Optimal Binary TreesSIAM Journal on Computing, 1987
- Dynamic huffman codingJournal of Algorithms, 1985
- Optimal Alphabetic TreesSIAM Journal on Computing, 1976
- Optimal alphabetic search trees with restricted maximal heightInformation Processing Letters, 1976
- A linear space algorithm for computing maximal common subsequencesCommunications of the ACM, 1975
- Optimal Binary Search Trees with Restricted Maximal DepthSIAM Journal on Computing, 1974
- Path Length of Binary Search TreesSIAM Journal on Applied Mathematics, 1972
- Optimal Computer Search Trees and Variable-Length Alphabetical CodesSIAM Journal on Applied Mathematics, 1971
- Optimum binary search treesActa Informatica, 1971