Generating a canonical prefix encoding

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Generating a canonical prefix encoding

Full text

Pdf (340 KB)

Source

Communications of the ACM archive
Volume 7 , Issue 3 (March 1964) table of contents

Pages: 166 - 169

Year of Publication: 1964

ISSN:0001-0782

Authors

Eugene S. Schwartz	IIT Research Institute, Chicago, IL
Bruce Kallick	IIT Research Institute, Chicago, IL

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 49, Citation Count: 14

Additional Information:

abstract references cited by index terms 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/363958.363991 What is a DOI?

ABSTRACT

Computer programs for generating a minimum-redundancy exhaustive prefix encoding are described. One program generates a Huffman frequency tree, another determines the structure functions of an encoding, and a third program assigns codes.

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	SHANNON, C. E. A mathematical theory of communication. Bell System Tech. J. 27 (1948), 379-423, 623-656.
	2	FANO, R. M. Res. Lab. for Electronics, Mass. Inst. Technology, Techn. Rep. No. 65, 1949.
	3	HUFFMAN, D. A. A method for the construction of minimumredundancy codes. Proc. IRE 40 (1952), 1098-1101.
	4	GILBERT, E. N. AND MOORE, E. F. Variable length binary encodings. Bell System Tech. J. 38 (1959), 933-967.
	5	KARP, R. S. Minimum-redundancy coding for the discrete noiseless channel. Trans. IRE, IT-7 (1961), 27-38.
	6	SCHWARTZ, E. S. An adaptive information transmission system employing minimum-redundancy word codes. Armour Research Foundation, Techn. Doc. Bep. ASD-TDR-62- 265, Pt. 11, June 1963.
	7	SCHWARTZ, E. S. An optimum encoding with minimum longest code and total number of digits. Inform. Contr. (to be published).

CITED BY 14

	A. Mulawa , Marek Machura, ACM Algorithm 450: Rosenbrock Function Minimization, Communications of the ACM, v.16 n.8, p.482-483, Aug. 1973
	J. M. Yohe, Algorithm 428: Hu-Tucker minimum redundancy alphabetic coding method [Z], Communications of the ACM, v.15 n.5, p.360-362, May 1972
	J. G. Byrne, Remark on Algorithm 428 [Z], Communications of the ACM, v.16 n.8, p.490, Aug. 1973
	Daniel S. Hirschberg , Debra A. Lelewer, Efficient decoding of prefix codes, Communications of the ACM, v.33 n.4, p.449-459, April 1990
	Edleno Silva de Moura , Gonzalo Navarro , Nivio Ziviani , Ricardo Baeza-Yates, Fast searching on compressed text allowing errors, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.298-306, August 24-28, 1998, Melbourne, Australia
	Edleno Silva de Moura , Gonzalo Navarro , Nivio Ziviani , Ricardo Baeza-Yates, Fast and flexible word searching on compressed text, ACM Transactions on Information Systems (TOIS), v.18 n.2, p.113-139, April 2000
	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
	Mario Latendresse , Marc Feeley, Generation of fast interpreters for Huffman compressed bytecode, Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators, p.32-40, June 12-12, 2003, San Diego, California
	Dana Shapira , Ajay Daptardar, Adapting the Knuth-Morris-Pratt algorithm for pattern matching in Huffman encoded texts, Information Processing and Management: an International Journal, v.42 n.2, p.429-439, March 2006
	Shlomo Weiss , Shay Beren, Class-Based Decompressor Design for Compressed Instruction Memory in Embedded Processors, IEEE Transactions on Computers, v.52 n.11, p.1495-1500, November 2003
	James F. Wade , Paul D. Stigall, Instruction design to minimize program size, ACM SIGARCH Computer Architecture News, v.3 n.4, p.41-44, December 1974
	Debra A. Lelewer , Daniel S. Hirschberg, Data compression, ACM Computing Surveys (CSUR), v.19 n.3, p.261-296, Sept. 1987
	Mario Latendresse , Marc Feeley, Generation of fast interpreters for Huffman compressed bytecode, Science of Computer Programming, v.57 n.3, p.295-317, September 2005
	Shmuel T. Klein, Skeleton Trees for the Efficient Decoding of Huffman Encoded Texts, Information Retrieval, v.3 n.1, p.7-23, July 2000