Linear Algorithm for Data Compression via String Matching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear Algorithm for Data Compression via String Matching

Full text

Pdf (508 KB)

Source

Journal of the ACM (JACM) archive
Volume 28 , Issue 1 (January 1981) table of contents

Pages: 16 - 24

Year of Publication: 1981

ISSN:0004-5411

Authors

Michael Rodeh	IBM Israel Scientific Center, Technion City, Haifa, Israel
Vaughan R. Pratt	Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA
Shimon Even	Department of Computer Science, Technion-IIT, Haifa, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 85, Citation Count: 23

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/322234.322237 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	ELIAS, P. Universal codeword sets and representations of the integers. IEEE Trans. Inf. Theory 1T- 21 (March 1975), 194-203.
	3	S. Even , M. Rodeh, Economical encoding of commas between strings, Communications of the ACM, v.21 n.4, p.315-317, April 1978 [doi>10.1145/359460.359480]
	4	LEMPEL, A., AND ZIV,' J. Oil the complexity of finite sequences. 1EEE Trans. Inf. Theory IT-22 (Jan. 1976), 75-8 I.
	5	LEVlUSTEIN, V.E. On the redundancy and delay of separable codes for the natural numbers. Probl. Cybernetics 20 (1968), 173-179 (in Russian).
	6	Edward M. McCreight, A Space-Economical Suffix Tree Construction Algorithm, Journal of the ACM (JACM), v.23 n.2, p.262-272, April 1976 [doi>10.1145/321941.321946]
	7	PRATT, V.R. Applications of the Weiner repetition finder. Unpublished paper, Cambridge, Mass., May 1973.
	8	RODEH, M. A fast test for unique decipherability based on suffix trees. Tech. Rep. TR-70, IBM Israel Scientific Center, Haifa, Israel, March 1979.
	9	SHPERLING, I. On the asymptotic complexity of sequences. Tech. Rep., Faculty of Electrical Engineering, Technion, Haifa, Israel, Dec. 1975 (in Hebrew).
	10	WEINER, P. Linear pattern matching algorithm. IEEE 14th Ann. Symp. on Switching and Automata Theory, Oct. 1973, pp. I-! !.
	11	Ziv, J., AND LEMPEL, A. A universal algorithm for sequential data compression. 1EEE Trans. Inf. Theory IT-23 (May 1977), 337-343.
	12	ZIv, J. AND LEMPEL, A. Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theory IT-24 (Sept. 1978), 530-536.

CITED BY 23

	M. E. Gonzalez Smith , J. A. Storer, Parallel algorithms for data compression, Journal of the ACM (JACM), v.32 n.2, p.344-373, April 1985
	Wojciech Szpankowski, (Un)expected behavior of typical suffix trees, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.422-431, September 1992, Orlando, Florida, United States
	Yossi Matias , Nasir Rajpoot , Cenk Sahinalp, The Effect of Flexible Parsing for Dynamic Dictionary-Based Data Compression, Journal of Experimental Algorithmics (JEA), 6, p.10-es, 2001
	James A. Storer , Thomas G. Szymanski, Data compression via textual substitution, Journal of the ACM (JACM), v.29 n.4, p.928-951, Oct. 1982
	E. R. Fiala , D. H. Greene, Data compression with finite windows, Communications of the ACM, v.32 n.4, p.490-505, April 1989
	Christopher W. Fraser , Eugene W. Myers , Alan L. Wendt, Analyzing and compressing assembly code, ACM SIGPLAN Notices, v.19 n.6, p.117-121, June 1984
	Ramesh Hariharan, Optimal parallel suffix tree construction, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.290-299, May 23-25, 1994, Montreal, Quebec, Canada
	Brenda S. Baker, A theory of parameterized pattern matching: algorithms and applications, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.71-80, May 16-18, 1993, San Diego, California, United States
	Udi Manber , Gene Myers, Suffix arrays: a new method for on-line string searches, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.319-327, January 22-24, 1990, San Francisco, California, United States
	Timothy C. Bell , Ian H. Witten, The relationship between greedy parsing and symbolwise text compression, Journal of the ACM (JACM), v.41 n.4, p.708-724, July 1994
	Joong Chae Na , Alberto Apostolico , Costas S. Iliopoulos , Kunsoo Park, Truncated suffix trees and their application to data compression, Theoretical Computer Science, v.304 n.1-3, p.87-101, 28 July 2003
	Mikhail J. Atallah , Stefano Lonardi, Authentication of LZ-77 compressed data, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida
	Timothy Bell , Ian H. Witten , John G. Cleary, Modeling for text compression, ACM Computing Surveys (CSUR), v.21 n.4, p.557-591, Dec. 1989
	Roman Kolpakov , Gregory Kucherov, Finding approximate repetitions under Hamming distance, Theoretical Computer Science, v.303 n.1, p.135-156, 28 June 2003
	Peter Johansen, Adaptive Pattern Recognition, Journal of Mathematical Imaging and Vision, v.7 n.4, p.325-339, Oct. 1997
	Dan Gusfield , Jens Stoye, Linear time algorithms for finding and representing all the tandem repeats in a string, Journal of Computer and System Sciences, v.69 n.4, p.525-546, December 2004
	Jean-Pierre Duval , Roman Kolpakov , Gregory Kucherov , Thierry Lecroq , Arnaud Lefebvre, Linear-time computation of local periods, Theoretical Computer Science, v.326 n.1-3, p.229-240, 20 October 2004
	A. Blumer , J. Blumer , A. Ehrenfeucht , D. Haussler , R. McConnell, Building a complete inverted file for a set of text files in linear time, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.349-358, December 1984
	Graham Cormode , S. Muthukrishnan, Substring compression problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Strahil Ristov, LZ trie and dictionary compression, Software—Practice & Experience, v.35 n.5, p.445-465, 25 April 2005
	Debra A. Lelewer , Daniel S. Hirschberg, Data compression, ACM Computing Surveys (CSUR), v.19 n.3, p.261-296, Sept. 1987
	Nathanael J. Brittain , Mahmoud R. El-Sakka, Grayscale true two-dimensional dictionary-based image compression, Journal of Visual Communication and Image Representation, v.18 n.1, p.35-44, February, 2007
	Sabrina Mantaci , Antonio Restivo , Marinella Sciortino, Distance measures for biological sequences: Some recent approaches, International Journal of Approximate Reasoning, v.47 n.1, p.109-124, January, 2008