A fast algorithm for optimal length-limited Huffman codes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A fast algorithm for optimal length-limited Huffman codes

Full text

Pdf (739 KB)

Source

Journal of the ACM (JACM) archive
Volume 37 , Issue 3 (July 1990) table of contents

Pages: 464 - 473

Year of Publication: 1990

ISSN:0004-5411

Authors

Lawrence L. Larmore	Univ. of California at Irvine
Daniel S. Hirschberg	Univ. of California at Irvine

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 83, Citation Count: 10

Additional Information:

abstract references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/79147.79150 What is a DOI?

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.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	GAREY, M. R. Optimal binary search trees with restricted maximal depth. SIAM J. Comput. 3 (1974), 101-110.
	2	D. S. Hirschberg, A linear space algorithm for computing maximal common subsequences, Communications of the ACM, v.18 n.6, p.341-343, June 1975 [doi>10.1145/360825.360861]
	3	Hu, T. C., AND TAN, K.C. Path length of binary search trees. SIAM J. Appl. Math 22 (1972), 225-234.
	4	Hu, T. C., AND TUCKER, A. C. Optimal computer search trees and variable length alphabetic codes. SIAM J. Appl. Math 21 ( 197 l), 514-532.
	5	HUFFMAN, D.A. A method for the construction of minimum redundancy codes. Proc. Inst. Radio Engineers 40 (1952), I098-1101.
	6	ITAI, A. Optimal alphabetic trees. SIAM J. Comput. 5 (1976), 9-18.
	7	KNUTH, D.E. Optimal binary search trees. Acta Inf. 1 (1971), 14-25.
	8	Donald E. Knuth, Dynamic Huffman coding, Journal of Algorithms, v.6 n.2, p.163-180, June 1985 [doi>10.1016/0196-6774(85)90036-7]
	9	Lawrence L. Larmore, Height restricted optimal binary trees, SIAM Journal on Computing, v.16 n.6, p.1115-1123, December 1, 1987 [doi>10.1137/0216070]
	10	L. L. Larmore, Minimum delay codes, SIAM Journal on Computing, v.18 n.1, p.82-94, Feb. 1989 [doi>10.1137/0218006]
	11	LARMORE, L. L. Optimal length-restricted codes. Colloquium, AT&T Bell Labs, Murray Hill, N.J., January 6, 1988.
	12	WESSNER, R.L. Optimal alphabetic search trees with restricted maximal height. Inf. Proc. Lett. 4 (1976), 90-94.

CITED BY 11

	Ho Chao Huang , Jau-Hsiung Huang , Ja-Ling Wu, Real-time software-based video coder for multimedia communication systems, Proceedings of the first ACM international conference on Multimedia, p.65-73, August 02-06, 1993, Anaheim, California, United States
	Mike Liddell , Alistair Moffat, Length-restricted coding using modified probability distributions, Australian Computer Science Communications, v.23 n.1, p.117-124, January-February 2001
	William Evans , David Kirkpatrick, Restructuring ordered binary trees, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.477-486, January 09-11, 2000, San Francisco, California, United States
	Chi-Ying Tsui , Massoud Pedram , Alvin M. Despain, Technology decomposition and mapping targeting low power dissipation, Proceedings of the 30th international conference on Design automation, p.68-73, June 14-18, 1993, Dallas, Texas, United States
	Lawrence L. Larmore , Teresa M. Przytycka, Parallel construction of trees with optimal weighted path length, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.71-80, July 21-24, 1991, Hilton Head, South Carolina, United States
	Abraham Bookstein , Shmuel T. Klein , Timo Raita, Is Huffman coding dead? (extended abstract), Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.80-87, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States
	William Evans , David Kirkpatrick, Restructuring ordered binary trees, Journal of Algorithms, v.50 n.2, p.168-193, February 2004
	Wade Trappe , Yuke Wang , K. J. Ray Liu, Resource-aware conference key establishment for heterogeneous networks, IEEE/ACM Transactions on Networking (TON), v.13 n.1, p.134-146, February 2005
	John Yiannis , Justin Zobel, Compression techniques for fast external sorting, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.2, p.269-291, April 2007
	Mordecai Golin , Xiaoming Xu , Jiajin Yu, A generic top-down dynamic-programming approach to prefix-free coding, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.758-767, January 04-06, 2009, New York, New York
	Frank Schulz, Trees with exponentially growing costs, Information and Computation, v.206 n.5, p.569-578, May, 2008