Fast searching on compressed text allowing errors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast searching on compressed text allowing errors

Full text

Pdf (1.19 MB)

Source

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

Melbourne, Australia

Pages: 298 - 306

Year of Publication: 1998

ISBN:1-58113-015-5

Authors

Edleno Silva de Moura	Depto. de Ciência da Computaçã, Univ. Federal de Minas Gerais, Brazil
Gonzalo Navarro	Depto. de Ciencias de la Computación, Univ. de Chile, Chile
Nivio Ziviani	Depto. de Ciência da Computaçã, Univ. Federal de Minas Gerais, Brazil
Ricardo Baeza-Yates	Depto. de Ciencias de la Computación, Univ. de Chile, Chile

Sponsors

University of Melbourne : University of Melbourne
SIGIR: ACM Special Interest Group on Information Retrieval

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 31, Citation Count: 10

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/290941.291013 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.

	AB92	A. Amir and G. Benson. Efficient twodimensional compressed matching. Proc. Second IEEE Data Compression Conference, pages 279-288, Mar. 1992.
	ABF96	Amihood Amir , Gary Benson , Martin Farach, Let sleeping files lie: pattern matching in Z-compressed files, Journal of Computer and System Sciences, v.52 n.2, p.299-307, April 1996 [doi>10.1006/jcss.1996.0023]
	ANZ97	M.D. Aratljo, G. Navarro and N. Ziviani. Large text searching allowing errors. In R. Baeza-Yates, editor, Proc. of the Fourth South American Workshop on String Processing, Carleton University Press International Informatics Series, v. 8, pages 2-20, 1997.
	BYG92	Ricardo Baeza-Yates , Gaston H. Gonnet, A new approach to text searching, Communications of the ACM, v.35 n.10, p.74-82, Oct. 1992 [doi>10.1145/135239.135243]
	BYN96	Ricardo A. Baeza-Yates , Gonzalo Navarro, A Faster Algorithm for Approximate String Matching, Proceedings of the 7th Annual Symposium on Combinatorial Pattern Matching, p.1-23, June 10-12, 1996
	BYN97a	Ricardo A. Baeza-Yates , Gonzalo Navarro, Multiple Approximate String Matching, Proceedings of the 5th International Workshop on Algorithms and Data Structures, p.174-184, August 06-08, 1997
	BYN97b	Ricardo Baeza-Yates , Gonzalo Navarro, Block addressing indices for approximate text retrieval, Proceedings of the sixth international conference on Information and knowledge management, p.1-8, November 10-14, 1997, Las Vegas, Nevada, United States [doi>10.1145/266714.266719]
	BYR92	Ricardo A. Baeza-Yates , Mireille Régnier, Average running time of the Boyer-Moore-Horspool algorithm, Theoretical Computer Science, v.92 n.1, p.19-31, Jan. 6, 1992 [doi>10.1016/0304-3975(92)90133-Z]
	BMN+93	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]
	BSTW86	Jon Louis Bentley , Daniel D. Sleator , Robert E. Tarjan , Victor K. Wei, A locally adaptive data compression scheme, Communications of the ACM, v.29 n.4, p.320-330, April 1986 [doi>10.1145/5684.5688]
	FT95	Martin Farach , Mikkel Thorup, String matching in Lempel-Ziv compressed strings, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.703-712, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225288]
	GBY91	G. H. Gonnet , R. Baeza-Yates, Handbook of algorithms and data structures: in Pascal and C (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
	Har95	D.K. Harman. Overview of the Third Text REtrieval Conference. In Proc. Third Text REtrieval Conference (TREC-3), pages 1-19, National Institute of Standards and Technology Special Publication 500-207, Gaithersburg, Maryland, 1995.
	Hea78	H. S. Heaps, Information Retrieval: Computational and Theoretical Aspects, Academic Press, Inc., Orlando, FL, 1978
	HL90	Daniel S. Hirschberg , Debra A. Lelewer, Efficient decoding of prefix codes, Communications of the ACM, v.33 n.4, p.449-459, April 1990 [doi>10.1145/77556.77566]
	HC92	R.N. Horspool and G. V. Cormack. Constructing Word-Based Text Compression Algorithms. IEEE Proc. Second Data Compression Conference, pages 62-81, 1992.
	Huf52	D.A. Huffman. A method for the construction of minimum-redundancy codes. Proc. of the Institute of Electrical and Radio Engineers, 40(9): 1090-1101, 1952.
	Man97	Udi Manber, A text compression scheme that allows fast searching directly in the compressed file, ACM Transactions on Information Systems (TOIS), v.15 n.2, p.124-136, April 1997 [doi>10.1145/248625.248639]
	MW93	U. Manber and S. Wu. Glimpse: a tool to search through entire file systems. Tech. Report 93-34, Dept. of Computer Science, Univ. of Arizona, Oct 1993.
	Mof89	A. Moffat, Word-based text compression, Software—Practice & Experience, v.19 n.2, p.185-198, February 1989 [doi>10.1002/spe.4380190207]
	MNZ97	E. de Moura, G. Navarro and N. Ziviani. Indexing compressed text. In R. Baeza-Yates, editor, Proc. of the Fourth South American Workshop on String Processing, Carleton University Press International Informatics Series, v.8, pages 95-111, 1997.
	MNZB98	E. de Moura, G. Navarro, N. Ziviani and R. Baeza-Yates. Direct Pattern Matching on Compressed Text. Tech. Report 03-98, Dept. of Computer Science, Univ. Federal de Minas Gerais, Brazil, Apt 1998.
	SK64	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]
	Sun90	Daniel M. Sunday, A very fast substring search algorithm, Communications of the ACM, v.33 n.8, p.132-142, Aug. 1990 [doi>10.1145/79173.79184]
	WM92	Sun Wu , Udi Manber, Fast text searching: allowing errors, Communications of the ACM, v.35 n.10, p.83-91, Oct. 1992 [doi>10.1145/135239.135244]
	Zip49	G. Zipf. Human Behaviour and the Principle of Least Effort. Addison-Wesley, 1949.
	ZL76	J. Ziv and A. Lempel. On the complexity of finite sequences. IEEE Transactions on Information Theory, 22: 75-81, 1976.
	ZL77	J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3): 337- 343, 1977.
	ZL78	J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding. IEEE Transactions on Information Theory, 24(5): 530-536, 1978.
	ZM95	Justin Zobel , Alistair Moffat, Adding compression to a full-text retrieval system, Software—Practice & Experience, v.25 n.8, p.891-903, Aug. 1995 [doi>10.1002/spe.4380250804]

CITED BY 10

	Raymond Wan , Alistair Moffat, Interactive phrase browsing within compressed text, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.410-411, September 2001, New Orleans, Louisiana, United States
	R. Yugo Kartono Isal , Alistair Moffat, Word-based block-sorting text compression, Australian Computer Science Communications, v.23 n.1, p.92-99, January-February 2001
	Ricardo Baeza-Yates , Alistair Moffat , Gonzalo Navarro, Searching large text collections, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Paolo Ferragina , Giovanni Manzini, An experimental study of an opportunistic index, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.269-278, January 07-09, 2001, Washington, D.C., United States
	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
	Nieves R. Brisaboa , Antonio Fariña , Gonzalo Navarro , José R. Paramá, Efficiently decodable and searchable natural language adaptive compression, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil
	Shmuel T. Klein, Skeleton Trees for the Efficient Decoding of Huffman Encoded Texts, Information Retrieval, v.3 n.1, p.7-23, July 2000
	Gonzalo Navarro , Edleno Silva De Moura , Marden Neubert , Nivio Ziviani , Ricardo Baeza-Yates, Adding Compression to Block Addressing Inverted Indexes, Information Retrieval, v.3 n.1, p.49-77, July 2000
	Nieves R. Brisaboa , Antonio Fariña , Susana Ladra , Gonzalo Navarro, Reorganizing compressed text, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore