String matching in Lempel-Ziv compressed strings

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

String matching in Lempel-Ziv compressed strings

Full text

Pdf (1.02 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-seventh annual ACM symposium on Theory of computing table of contents

Las Vegas, Nevada, United States

Pages: 703 - 712

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Martin Farach	Rutgers University
Mikkel Thorup	University of Copenhagen

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 44, Citation Count: 21

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/225058.225288 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	A. Amir and G. Benson. Efficient two dimen-sional compressed matching. PTOC. of the ,%d IEEE Data Compression Confe~"ence, pages 279-288, Mar 1992.
	3	Amihood Amir , Gary Benson , Martin Farach, Let sleeping files lie: pattern matching in Z-compressed files, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.705-714, January 23-25, 1994, Arlington, Virginia, United States
	4	Amihood Amir , Gary Benson , Martin Farach, Optimal Two-Dimensional Compressed Matching, Proceedings of the 21st International Colloquium on Automata, Languages and Programming, p.215-226, July 11-14, 1994
	5	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	6	Ming Gu , Martin Farach , Richard Beigel, An efficient algorithm for dynamic text indexing, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.697-704, January 23-25, 1994, Arlington, Virginia, United States
	7	Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
	8	S. Rao Kosaraju. On the entrop!y estimation of low entropy sources. Personal Communica-tion, 1994.
	9	S. Rao Kosaraju. Pattern matching in com-pressed texts. Manuscript, 1994.
	10	A. Lempel and J. Ziv. On the complexity of finite sequences. IEEE Transactions on In-formation Theory, 22:75-81, 1976.
	11	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
	12	Lynn M. Stauffer , Daniel S. Hirschberg, PRAM Algorithms for Static Dictionary Compression, Proceedings of the 8th International Symposium on Parallel Processing, p.344-348, April 01, 1994
	13	James A. Storer, Data compression: methods and theory, Computer Science Press, Inc., New York, NY, 1987
	14	T. A. Welch. A technique for high-performance data compression. IEEE Trans-actions on Computers, 17:8-19, 1984.
	15	J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Trans-actions on Information Theory, IT-23(3):337- 343, 1977.

CITED BY 21

	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
	Takuya Kida , Tetsuya Matsumoto , Yusuke Shibata , Masayuki Takeda , Ayumi Shinohara , Setsuo Arikawa, Collage system: a unifying framework for compressed pattern matching, Theoretical Computer Science, v.298 n.1, p.253-272, 4 April 2003
	Amihood Amir , Gad M. Landau , Dina Sokol, Inplace run-length 2d compressed search, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.817-818, January 09-11, 2000, San Francisco, California, United States
	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
	Foto Afrati , Hans Leiß , Michel de Rougemont, Definability and compression, Fundamenta Informaticae, v.56 n.1,2, p.155-180, July 2003
	Leszek Gasieniec , Igor Potapov, Time/space efficient compressed pattern matching, Fundamenta Informaticae, v.56 n.1,2, p.137-154, July 2003
	Amihood Amir , Gad M. Landau , Dina Sokol, Inplace run-length 2d compressed search, Theoretical Computer Science, v.290 n.3, p.1361-1383, 3 January 2003
	Alberto Apostolico , Maxime Crochemore, String pattern matching for a deluge survival kit, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Wojciech Rytter, Application of Lempel--Ziv factorization to the approximation of grammar-based compression, Theoretical Computer Science, v.302 n.1-3, p.211-222, 13 June 2003
	Kunihiko Sadakane, New text indexing functionalities of the compressed suffix arrays, Journal of Algorithms, v.48 n.2, p.294-313, September 2003
	Amihood Amir , Gad M. Landau , Dina Sokol, Inplace 2D matching in compressed images, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
	Abdelghani Bellaachia , Iehab AL Rassan, Efficiency of prefix and non-prefix codes in string matching over compressed databases on handheld devices, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
	Juhani Karhumäki , Wojciech Plandowski , Wojciech Rytter, The complexity of compressing subsegments of images described by finite automata, Discrete Applied Mathematics, v.125 n.2-3, p.235-254, February 2003
	Amihood Amir , Gad M. Landau , Dina Sokol, Inplace 2D matching in compressed images, Journal of Algorithms, v.49 n.2, p.240-261, November 2003
	Juhani Karhumäki , Wojciech Plandowski , Wojciech Rytter, Pattern-matching problems for two-dimensional images described by finite automata, Nordic Journal of Computing, v.7 n.1, p.1-13, Spring 2000
	Abdelghani Bellaachia , Iehab Al Rassan, String Matching Over Compressed Text on Handheld Devices Using Tagged Sub-Optimal Code (TSC), Real-Time Systems, v.29 n.2-3, p.227-246, March 2005
	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
	Shmuel T. Klein , Dana Shapira, Pattern matching in Huffman encoded texts, Information Processing and Management: an International Journal, v.41 n.4, p.829-841, July 2005
	Pawe Baturo , Wojciech Rytter, Compressed string-matching in standard Sturmian words, Theoretical Computer Science, v.410 n.30-32, p.2804-2810, August, 2009
	Srinidhi Varadarajan , Tzi-cker Chiueh, SASE: implementation of a compressed text search engine, Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems, p.23-23, December 08-11, 1997, Monterey, California
	Michał Stabno , Robert Wrembel, RLH: Bitmap compression technique based on run-length and Huffman encoding, Information Systems, v.34 n.4-5, p.400-414, June, 2009