A new approach to text searching

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A new approach to text searching

Full text

Pdf (5.31 MB)

Source

Communications of the ACM archive
Volume 35 , Issue 10 (October 1992) table of contents

Pages: 74 - 82

Year of Publication: 1992

ISSN:0001-0782

Authors

Ricardo Baeza-Yates	Universidad de Chile, Blanco Encalada 2120, Depto. de Ciencias de la Computacion, Santiago, Chile
Gaston H. Gonnet	Informatik, Swiss Technological Institute in Zurich, Switzerland

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 30, Downloads (12 Months): 214, Citation Count: 62

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/135239.135243 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	Karl Abrahamson, Generalized string matching, SIAM Journal on Computing, v.16 n.6, p.1039-1051, December 1, 1987 [doi>10.1137/0216067]
	2	Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
	3	R. A. Baeza-Yates, Improved string searching, Software—Practice & Experience, v.19 n.3, p.257-271, March 1989 [doi>10.1002/spe.4380190305]
	4	Ricardo A. Baeza-Yates, String searching algorithms, Information retrieval: data structures and algorithms, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
	5	Ricardo A. Baeza-Yates, Text-Retrieval: Theory and Practice, Proceedings of the IFIP 12th World Computer Congress on Algorithms, Software, Architecture - Information Processing '92, Volume 1, p.465-476, September 07-11, 1992
	6	R. L. Baeza-Yates, Efficient text searching, University of Waterloo, Waterloo, Ont., Canada, 1989
	7	Ricardo A. Baeza-Yates, String Searching Algorithms Revisited, Proceedings of the Workshop on Algorithms and Data Structures, p.75-96, August 17-19, 1989
	8	Baeza-Yates, R, and Connet, G,H,. Fast string matching with mismatches, Inf. Comput. ( 1992). To be published. Also as Tech. Rep. CS- 88-36. Dept. of Computer Science, Universty of Waterloo, I988,
	9	R. A. Baeza-Yates , G. H. Gonnet, A new approach to text searching, Proceedings of the 12th annual international ACM SIGIR conference on Research and development in information retrieval, p.168-175, June 25-28, 1989, Cambridge, Massachusetts, United States
	10	Baeza-Yates, R. and Gonnet, G. New atgorithm for pattern match ing with and without misnmtches. Tech. Rep. CS-88-37 Department of Computer Science, University of Waterloo, Ontario. Canada, 1988.
	11	Ricardo A. Baeza-Yates , Chris H. Perleberg, Fast and Practical Approximate String Matching, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.185-192, April 29-May 01, 1992
	12	Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
	13	Beate Commentz-Walter, A String Matching Algorithm Fast on the Average, Proceedings of the 6th Colloquium, on Automata, Languages and Programming, p.118-132, July 16-20, 1979
	14	Diane Crawford, Technical correspondence, Communications of the ACM, v.35 n.4, p.132, April 1992 [doi>10.1145/129852.376095]
	15	Fischer, M. and Paterson, M. String matching and other products. In Complexity of Computation, R, Karp, Ed. (SIAM-AMS Proceeding 7), pp. 113-125 Americaa Mathematical Society, Providence, RI., 1974.
	16	Z Galil , R Giancarlo, Improved string matching with k mismatches, ACM SIGACT News, v.17 n.4, p.52-54, Spring 1986 [doi>10.1145/8307.8309]
	17	Gaston H. Gonnet, Unstructured data bases or very efficient text searching, Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems, March 21-23, 1983, Atlanta, Georgia [doi>10.1145/588058.588074]
	18	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
	19	Horspool, R.N. Practical fast searching in strings, Softw. - Pract. Exper. 10 (1980), 501-506.
	20	Andrew Hume , Daniel Sunday, Fast string searching, Software—Practice & Experience, v.21 n.11, p.1221-1248, Nov. 1991 [doi>10.1002/spe.4380211105]
	21	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
	22	B. W. Kernighan , D. M. Ritchie, The C programming language, Prentice-Hall, Inc., Upper Saddle River, NJ, 1978
	23	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	24	Knuth, D,.E,., Morris. J, and Pratt, V. Fast pattern matching in strings,. SiaM J 6 (1977), 323-350
	25	G M Landau , U Vishkin, Efficient string matching with k mismatches, Theoretical Computer Science, v.43 n.2-3, p.239-249, July 1986
	26	Pinter, R. Efficient string matching with don't-are patmrns. In: Combinational Algorithms on Words, A.. Apostolico and Z. Galil, Eds, vol.. F I2 of NAT0 ASI Series, Springer- Vertag, 1985, pp 239-249.
	27	P. D. Smith, Experiments with a very fast substring search algorithm, Software—Practice & Experience, v.21 n.10, p.1065-1074, Oct. 1991 [doi>10.1002/spe.4380211006]
	28	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]
	29	Wu, S, and Manber, U, Fast text searching with errors, Tech. Rep. TR-91-11. Department of Computer Science, University of Ari.- zona., Tucson, Ariz June 1991
	30	Wu, S.. and Manber, U.. Agrep- a fast approximate pattern-matching tool, In Proceedings USENIX Tech.- nical Conferences (Jan. 1992, San Francisco, Calif.), pp. 153-162.

CITED BY 63

	Toshiyuki Masui, An efficient text input method for pen-based computers, Proceedings of the SIGCHI conference on Human factors in computing systems, p.328-335, April 18-23, 1998, Los Angeles, California, United States
	Luc Boasson , Patrick Cegielski , Irène Guessarian , Yuri Matiyasevich, Window-accumulated subsequence matching problem is linear, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.327-336, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Han Kesong , Wang Yongcheng , Chen Guilin, Research on a faster algorithm for pattern matching, Proceedings of the fifth international workshop on on Information retrieval with Asian languages, p.119-124, September 30-October 01, 2000, Hong Kong, China
	Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001
	Gonzalo Navarro , Mathieu Raffinot, Fast and simple character classes and bounded gaps pattern matching, with application to protein searching, Proceedings of the fifth annual international conference on Computational biology, p.231-240, April 22-25, 2001, Montreal, Quebec, Canada
	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
	Charles L. A. Clarke , Gordon V. Cormack, On the use of regular expressions for searching text, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.3, p.413-426, May 1997
	Osamu Maruyama , Hideo Bannai , Yoshinori Tamada , Satoru Kuhara , Satoru Miyano, Fast algorithm for extracting multiple unordered short motifs using bit operations, Information Sciences—Applications: An International Journal, v.146 n.1-4, p.115-126, October 2002
	Panagiotis D. Michailidis , Konstantinos G. Margaritis, Parallel implementations for string matching problem on a cluster of distributed workstations, Neural, Parallel & Scientific Computations, v.10 n.3, p.287-312, September 2002
	Kensuke Baba , Ayumi Shinohara , Masayuki Takeda , Shunsuke Inenaga , Setsuo Arikawa, A note on randomized algorithm for string matching with mismatches, Nordic Journal of Computing, v.10 n.1, p.2-12, Spring 2003
	Ricardo Baeza-Yates , Gonzalo Navarro, New and faster filters for multiple approximate string matching, Random Structures & Algorithms, v.20 n.1, p.23-49, January 2002
	Kimmo Fredriksson, Shift-or string matching with super-alphabets, Information Processing Letters, v.87 n.4, p.201-204, 31 August 2003
	Josué Kuri , Gonzalo Navarro , Ludovic Mé, Fast multipattern search algorithms for intrusion detection, Fundamenta Informaticae, v.56 n.1,2, p.23-49, July 2003
	Maxime Crochemore , Costas S. Iliopoulos , Thierry Lecroq , Yoan J. Pinzon , Wojciech Plandowski , Wojciech Rytter, Occurrence and substring heuristics for δ-matching, Fundamenta Informaticae, v.56 n.1,2, p.1-21, July 2003
	Maxime Crochemore , Costas S. Ilipoulos , Yoan J. Pinzon, Speeding-up Hirschberg and Hunt-Szymanski LCS algorithms, Fundamenta Informaticae, v.56 n.1,2, p.89-103, July 2003
	Nadia Pisanti , Maxime Crochemore , Roberto Grossi , Marie-France Sagot, Bases of Motifs for Generating Repeated Patterns with Wild Cards, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.2 n.1, p.40-50, January 2005
	Kjell Lemström , Jorma Tarhio, Transposition invariant pattern matching for multi-track strings, Nordic Journal of Computing, v.10 n.3, p.185-205, September 2003
	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
	Gene Myers, A fast bit-vector algorithm for approximate string matching based on dynamic programming, Journal of the ACM (JACM), v.46 n.3, p.395-415, May 1999
	Sun Kim, A new string-pattern matching algorithm using partitioning and hashing efficiently, Journal of Experimental Algorithmics (JEA), 4, p.2-es, 1999
	Tun-Wen Pai , Margaret Dah-Tsyr Chang , Jia-Han Chu , Wei-Yuan Chang , Hsiu Ling Tai, Ladderlike stepping and interval jumping searching algorithms for DNA sequences, Proceedings of the second conference on Asia-Pacific bioinformatics, p.93-98, January 01, 2004, Dunedin, New Zealand
	Ying Xu , Lusheng Wang , Xiaotie Deng, Exact pattern matching for RNA secondary structures, Proceedings of the second conference on Asia-Pacific bioinformatics, p.257-263, January 01, 2004, Dunedin, New Zealand
	H. Shang , T. h. Merrettal, Tries for Approximate String Matching, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.540-547, August 1996
	Gonzalo Navarro , Mathieu Raffinot, Fast and flexible string matching by combining bit-parallelism and suffix automata, Journal of Experimental Algorithmics (JEA), 5, p.4-es, 2000
	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
	Nivio Ziviani , Edleno Silva de Moura , Gonzalo Navarro , Ricardo Baeza-Yates, Compression: A Key for Next-Generation Text Retrieval Systems, Computer, v.33 n.11, p.37-44, November 2000
	Raghu Sastry , N. Ranganathan , Klinton Remedios, CASM: A VLSI Chip for Approximate String Matching, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.8, p.824-830, August 1995
	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
	E. Sutinen , J. Tarhio, Approximate string matching with ordered q-grams, Nordic Journal of Computing, v.11 n.4, p.321-343, December 2004
	Ying Xu , Lusheng Wang , Hao Zhao , Jianping Li, Exact matching of RNA secondary structure patterns, Theoretical Computer Science, v.335 n.1, p.53-66, 20 May 2005
	J.-P. Comet, Application of max-plus algebra to biological sequence comparisons, Theoretical Computer Science, v.293 n.1, p.189-217, 3 February 2003
	Patrick Cégielski , Irène Guessarian , Yuri Matiyasevich, Multiple serial episodes matching, Information Processing Letters, v.98 n.6, p.211-218, 30 June 2006
	Ela Hunt , Malcolm P. Atkinson , Robert W. Irving, Database indexing for large DNA and protein sequence collections, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.3, p.256-271, November 2002
	Longtao He , Binxing Fang , Jie Sui, The wide window string matching algorithm, Theoretical Computer Science, v.332 n.1-3, p.391-404, 28 February 2005
	Kimmo Fredriksson , Maxim Mozgovoy, Efficient parameterized string matching, Information Processing Letters, v.100 n.3, p.91-96, 15 November 2006
	Kimmo Fredriksson , Szymon Grabowski, A general compression algorithm that supports fast searching, Information Processing Letters, v.100 n.6, p.226-232, 31 December 2006
	Heikki Hyyrö , Kimmo Fredriksson , Gonzalo Navarro, Increased bit-parallelism for approximate and multiple string matching, Journal of Experimental Algorithmics (JEA), 10, 2005
	Leena Salmela , Jorma Tarhio , Jari Kytöjoki, Multipattern string matching with q-grams, Journal of Experimental Algorithmics (JEA), 11, 2006
	Panagiotis D. Michailidis , Konstantinos G. Margaritis, A programmable array processor architecture for flexible approximate string matching algorithms, Journal of Parallel and Distributed Computing, v.67 n.2, p.131-141, February, 2007
	Roger D. Chamberlain , Ron K. Cytron , Mark A. Franklin , Ronald S. Indeck, The Mercury system: exploiting truly fast hardware for data search, Proceedings of the international workshop on Storage network architecture and parallel I/Os, p.65-72, September 28-28, 2003, New Orleans, Louisiana
	Luís M. S. Russo , Arlindo L. Oliveira, Efficient generation of super condensed neighborhoods, Journal of Discrete Algorithms, v.5 n.3, p.501-513, September, 2007
	Ke Wang, Discovering Patterns from Large and Dynamic Sequential Data, Journal of Intelligent Information Systems, v.9 n.1, p.33-56, July/Aug. 1997
	Kimmo Fredriksson , Jorma Tarhio, Efficient String Matching in Huffman Compressed Texts, Fundamenta Informaticae, v.63 n.1, p.1-16, January 2004
	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
	Shyong Jian Shyu , Chun-Yuan Tsai, Finding the longest common subsequence for multiple biological sequences by ant colony optimization, Computers and Operations Research, v.36 n.1, p.73-91, January, 2009
	Chaim Linhart , Ron Shamir, Faster pattern matching with character classes using prime number encoding, Journal of Computer and System Sciences, v.75 n.3, p.155-162, May, 2009
	Leena Salmela , Jorma Tarhio, Fast parameterized matching with q-grams, Journal of Discrete Algorithms, v.6 n.3, p.408-419, September, 2008
	Janardhan Singaraju , John A. Chandy, FPGA based string matching for network processing applications, Microprocessors & Microsystems, v.32 n.4, p.210-222, June, 2008
	Frantisek Franek , Christopher G. Jennings , W. F. Smyth, A simple fast hybrid pattern-matching algorithm, Journal of Discrete Algorithms, v.5 n.4, p.682-695, December, 2007
	Panagiotis D. Michailidis , Konstantinos G. Margaritis, Processor array architectures for flexible approximate string matching, Journal of Systems Architecture: the EUROMICRO Journal, v.54 n.1-2, p.35-54, January, 2008
	Szymon Grabowski , Kimmo Fredriksson, Bit-parallel string matching under Hamming distance in O(n⌈m/w⌉) worst case time, Information Processing Letters, v.105 n.5, p.182-187, February, 2008
	Chia-Tien Dan Lo , Yi-Gang Tai , Kleanthis Psarris, Hardware implementation for network intrusion detection rules with regular expression support, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil
	Zheng Liu , James Borneman , Tao Jiang, A software system for gene sequence database construction based on fast approximate string matching, International Journal of Bioinformatics Research and Applications, v.1 n.3, p.273-291, September 2005
	Jan Holub , W. F. Smyth , Shu Wang, Fast pattern-matching on indeterminate strings, Journal of Discrete Algorithms, v.6 n.1, p.37-50, March, 2008
	Panagiotis D. Michailidis , Konstantinos G. Margaritis, Parallel text searching applications on a heterogeneous cluster architecture, International Journal of Computational Science and Engineering, v.1 n.1, p.45-59, February 2005
	Kimmo Fredriksson , Szymon Grabowski, Efficient algorithms for pattern matching with general gaps, character classes, and transposition invariance, Information Retrieval, v.11 n.4, p.335-357, August 2008
	Ahmed K. Elmagarmid , Panagiotis G. Ipeirotis , Vassilios S. Verykios, Duplicate Record Detection: A Survey, IEEE Transactions on Knowledge and Data Engineering, v.19 n.1, p.1-16, January 2007
	Philip Bille , Martin Farach-Colton, Fast and compact regular expression matching, Theoretical Computer Science, v.409 n.3, p.486-496, December, 2008
	Kimmo Fredriksson, Succinct backward-DAWG-matching, Journal of Experimental Algorithmics (JEA), 13, February 2009
	Rajesh Prasad , Suneeta Agarwal, Multi-patterns parameterized shift-and string matching algorithm with super alphabets, Proceedings of the International Conference on Advances in Computing, Communication and Control, January 23-24, 2009, Mumbai, India
	Wen-Jyi Hwang , Huang-Chun Roan , Ying-Nan Shih , Chia-Tien Dan Lo , Chien-Min Ou, FPGA-based ROM-free network intrusion detection using shift-OR circuit, Journal of Embedded Computing, v.3 n.2, p.99-107, April 2009
	Kimmo Fredriksson , Fedor Nikitin, Simple Random Access Compression, Fundamenta Informaticae, v.92 n.1-2, p.63-81, January 2009
	Sergio Deusdado , Paulo Carvalho, GRASPm: an efficient algorithm for exact pattern-matching in genomic sequences, International Journal of Bioinformatics Research and Applications, v.5 n.4, p.385-401, July 2009