Is Huffman coding dead? (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Is Huffman coding dead? (extended abstract)

Full text

Pdf (735 KB)

Source

Annual ACM Conference on Research and Development in Information Retrieval archive
Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval table of contents

Pittsburgh, Pennsylvania, United States

Pages: 80 - 87

Year of Publication: 1993

ISBN:0-89791-605-0

Authors

Abraham Bookstein
Shmuel T. Klein
Timo Raita

Sponsor

SIGIR: ACM Special Interest Group on Information Retrieval

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 59, Citation Count: 2

Additional Information:

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/160688.160697 What is a DOI?

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	Abramson N., Information Theory and Coding, McGraw-Hill, New York (1965).
	2	Bauer F.L., Goos G., Informatik, Eine einffthrende Ubersicht, Erster Teil, Springer Verlag, Berlin (1973).
	3	Timothy C. Bell , Alistair Moffat , Craig G. Nevill-Manning , Ian H. Witten , Justin Zobel, Data compression in full-text retrieval systems, Journal of the American Society for Information Science, v.44 n.9, p.508-531, Oct. 1993 [doi>10.1002/(SICI)1097-4571(199310)44:9<508::AID-ASI2>3.0.CO;2-A]
	4	Abraham Bookstein , Shmuel T. Klein, Compression, information theory, and grammars: a unified approach, ACM Transactions on Information Systems (TOIS), v.8 n.1, p.27-49, Jan. 1990 [doi>10.1145/78915.78917]
	5	Abraham Bookstein , Shmuel T. Klein, Models of bitmap generation: a systematic approach to bitmap compression, Information Processing and Management: an International Journal, v.28 n.6, p.735-748, Nov.–Dec. 1992 [doi>10.1016/0306-4573(92)90065-8]
	6	Abraham Bookstein , Shmuel T. Klein , D. A. Ziff, A systematic approach to compressing a full-text retrieval system, Information Processing and Management: an International Journal, v.28 n.6, p.795-806, Nov.–Dec. 1992 [doi>10.1016/0306-4573(92)90069-C]
	7	Bookstein A., Klein S.T., Raita T., Ravlchandra Rao I.K.~ P atll M.D.s Can random fluctuations be exploited in data compres~ sion, Proc. DCC'93 (1993).
	8	Chevion D.~ Karnin E.D., Walach A.C.~ High efficiency, multiplication free approximation of arithmetic coding, Proc. DCC'91 (1991) 43-52.
	9	Y. Choueka , S. T. Klein , Y. Perl, Efficient variants of Huffman codes in high level languages, Proceedings of the 8th annual international ACM SIGIR conference on Research and development in information retrieval, p.122-130, June 05-07, 1985, Montreal, Quebec, Canada [doi>10.1145/253495.342777]
	10	Ferguson T. J., Rabinowitz J. H., Selfsynchronizing Huffman codes, IEEE Trans. on Inf. Th. IT-30 (1984) 687-693.
	11	Fraenkel A.S., All about the Responsa Retrieval Project you always wanted to know but were afraid to ask, Expanded Summary, Jurimettics Y. 16 (1976) 149-156.
	12	Fraenkel A.S.~ Klein S.T.~ Bounding the depth of search trees, to appear in The Computer Journal (1993).
	13	H. F. Gaines, Cryptanalysis a Study of Ciphers and Their Solutions, Dover Publications, Incorporated, 1939
	14	Gallager R.G., Variations on a theme by Huffman, IEEE Trans. on inf. Th., IT-24 (1978) 668-674.
	15	Gilbert E.N., Codes based on inaccurate source probabilities, IEEE Trans. on Inf. Th. IT-17 (1971) 304-314
	16	Gilbert E.N., Moore E.F., VariabIe-Iengthbinary encodings, The Bell System Technical Journal 38 (1959) 933-968.
	17	H. S. Heaps, Information Retrieval: Computational and Theoretical Aspects, Academic Press, Inc., Orlando, FL, 1978
	18	Herdan G., The Advanced Theory of Language as Choice and Chance, Springer-Verlag, New York (1966).
	19	Paul G. Howard , Jeffrey S Vitter, Practical Implementations of Arithmetic Coding, Brown University, Providence, RI, 1991
	20	Huffman D., A method for the construction of minimum redundancy codes, Proc. of the IRE 40 ( 9s2) 1098-1101
	21	Shmuel T. Klein , Abraham Bookstein , Scott Deerwester, Storing text retrieval systems on CD-ROM: compression and encryption considerations, ACM Transactions on Information Systems (TOIS), v.7 n.3, p.230-245, July 1989 [doi>10.1145/65943.65946]
	22	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	23	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]
	24	Lawrence L. Larmore , Daniel S. Hirschberg, A fast algorithm for optimal length-limited Huffman codes, Journal of the ACM (JACM), v.37 n.3, p.464-473, July 1990 [doi>10.1145/79147.79150]
	25	Debra A. Lelewer , Daniel S. Hirschberg, Data compression, ACM Computing Surveys (CSUR), v.19 n.3, p.261-296, Sept. 1987 [doi>10.1145/45072.45074]
	26	Moffat A., Zobel J.~ Coding for compression in full-text retrieval systems, Proc. DCC'92 (1992) 72-81.
	27	Mark Nelson, The Data Compression Book, Henry Holt and Co., Inc., New York, NY, 1991
	28	Pesonen J., Word inflexions and their letter and syllable structure in Finnish newspaper text, Research Rep. 6/1971, Dept. of Special Education, University of Jyr~skylh, Finland (in Finnish, with English summary).
	29	Rissanen J.J.~ Generalized Kraft inequality and arithmetic coding, IBM J. Res. Dev. 20 (1976) 198-203.
	30	Rissanen J.J., Langdon G.G., Arithmetic coding, IBM J. Res. Dev. 23 (1979) 149-162.
	31	Eugene S. Schwartz , Bruce Kallick, Generating a canonical prefix encoding, Communications of the ACM, v.7 n.3, p.166-169, March 1964 [doi>10.1145/363958.363991]
	32	Teuhola J., Ralta T., Piecewise arithmetic coding, Proc. DCC'91 (1991) 33-42.
	33	Van Leeuwen J., On the construction of Huffman trees, Proc. 3rd ICALP Conference, Edinburgh University Press (1976) 382-410.
	34	Jeffrey Scott Vitter, Design and analysis of dynamic Huffman codes, Journal of the ACM (JACM), v.34 n.4, p.825-845, Oct. 1987 [doi>10.1145/31846.42227]
	35	Ian H. Witten , Radford M. Neal , John G. Cleary, Arithmetic coding for data compression, Communications of the ACM, v.30 n.6, p.520-540, June 1987 [doi>10.1145/214762.214771]

CITED BY 2

	Kihong Kim , Sang K. Cha , Keunjoo Kwon, Optimizing multidimensional index trees for main memory access, ACM SIGMOD Record, v.30 n.2, p.139-150, June 2001
	M. Zaki , M. Sayed, The use of genetic programming for adaptive text compression, International Journal of Information and Coding Theory, v.1 n.1, p.88-108, March 2009