ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Fast text searching: allowing errors
Full text PdfPdf (5.33 MB)
Source
Communications of the ACM archive
Volume 35 ,  Issue 10  (October 1992) table of contents
Pages: 83 - 91  
Year of Publication: 1992
ISSN:0001-0782
Authors
Sun Wu  Bell Labs, Murray Hill, NJ
Udi Manber  Univ. of Arizona, Tucson
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 21,   Downloads (12 Months): 248,   Citation Count: 107
Additional Information:

references   cited by   index terms   review   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/135239.135244
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
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
3
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]
 
4
Chang, W.I. and Lawler, E.L. Approximate string matching in sublinear expected time., FOCS 90, pp. 116-124.
 
5
Z. Galil , R. Giancarlo, Data structures and algorithms for approximate string matching, Journal of Complexity, v.4 n.1, p.33-72, March 1988  [doi>10.1016/0885-064X(88)90008-8]
 
6
Zvi Galil , Kunsoo Park, An improved algorithm for approximate string matching, SIAM Journal on Computing, v.19 n.6, p.989-999, Dec. 1990  [doi>10.1137/0219067]
 
7
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
8
Patrick A. V. Hall , Geoff R. Dowling, Approximate String Matching, ACM Computing Surveys (CSUR), v.12 n.4, p.381-402, Dec. 1980  [doi>10.1145/356827.356830]
 
9
John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
 
10
Knuth, D.E., Morris. J.H. and Pratt V.R,.Fast pattern matching in strings. SIAM J. Comput. 6 (June 1977), 323-350.
 
11
Gad M. Landau , Uzi Vishkin, Fast string matching with k-differences, Journal of Computer and System Sciences, v.37 n.1, p.63-78, August 1988  [doi>10.1016/0022-0000(88)90045-1]
 
12
G. M. Landau , U. Vishkin, Fast parallel and serial approximate string matching, Journal of Algorithms, v.10 n.2, p.157-169, June 1989  [doi>10.1016/0196-6774(89)90010-2]
 
13
Levenshtein, V.I. Binary codes capable of correcting deletions, insertions, and reversals, Sov. Physs., DokL (Feb. 1966), 707-710L
 
14
Manber, U. and Wu, S. Approximate string matching with arbitrary costs for text abd hypertext. IAPR Workshop on Structural and Syntatic Pattern. Recognition, (Bern, Switzerland. Aug. 1992).
 
15
Manber, U. and Wu, S.. Approximate pattern matching. BYTE. To be published Nov, I992,
 
16
Myers, E.W, An O(ND) difference algorithm and its variations. Algorithmica 1 (1986), 251-266,.
 
17
Myers, E.W. and Miller, W. Approximate matching of regular expressions. Bull Math. Bio, 51, (1989), 5-37.
 
18
Pinter, R. Efficient string matching with don't-care patterns. In combinatorial Algoritms on Words, A. Apostolico and Z. Galil, Eds., Springer-Verlag, Berlin, 1985.
 
19
Tarhio, J. and Ukkonen, E. Approximate Boyer-Moore string matching. Tech. Rep..#A-.1990-3,. Dept. of Computer Science, University of Helsinki (Mar. 1990).,
 
20
Ukkonen, E. Finding approximate patterns in sirings. J, Algor. 6 (1985), 132-137.
 
21
Esko Ukkonen, Algorithms for approximate string matching, Information and Control, v.64 n.1-3, p.100-118, Jan./Feb./March 1985  [doi>10.1016/S0019-9958(85)80046-2]
 
22
Wagner, R.A. and Seiferas, J.I., Correcting counter-automation-recognizable languages, SIAM J. Comput. (1978), 3357-375.
 
23
Sun Wu, Approximate pattern matching and its applications, University of Arizona, Tucson, AZ, 1992
 
24
Wu, S.. and Manber. U. Agrep-A fast approximate pattern-matching tool. Usenix Winter 1992 Technical Conference (San Francisco Jan. 1992), pp. 153-162,
 
25
Wu, S., Manber, U. and Myers,. E,.W',. A Sub-Quadratic Algorithm for Approximate Regular Expression M:atching, submitted for publication (May 1992).

CITED BY  107
Frank Vahid, Procedure exlining: a transformation for improved system and behavioral synthesis, Proceedings of the 8th international symposium on System synthesis, p.84-89, September 13-15, 1995, Cannes, France
Frank Vahid, Partitioning sequential programs for CAD using a three-step approach, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.7 n.3, p.413-429, July 2002
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
Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
Hal Berghel , David Roach, An extension of Ukkonen's enhanced dynamic programming ASM algorithm, ACM Transactions on Information Systems (TOIS), v.14 n.1, p.94-106, Jan. 1996
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
Justin Zobel , Philip Dart, Phonetic string matching: lessons from information retrieval, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.166-172, August 18-22, 1996, Zurich, Switzerland
Gonzalo Navarro, A guided tour to approximate string matching, ACM Computing Surveys (CSUR), v.33 n.1, p.31-88, March 2001
Frank Vahid, Procedure exlining: a new system-level specification transformation, Proceedings of the conference on European design automation, p.508-513, September 18-22, 1995, Brighton, England
Gonzalo Navarro, Approximate regular expression searching with arbitrary integer weights, Nordic Journal of Computing, v.11 n.4, p.356-373, December 2004
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
Luciano R. S. de Lima , Alberto H. F. Laender , Berthier A. Ribeiro-Neto, A hierarchical approach to the automatic categorization of medical documents, Proceedings of the seventh international conference on Information and knowledge management, p.132-139, November 02-07, 1998, Bethesda, Maryland, United States
Kevyn Collins-Thompson , Charles Schweizer , Susan Dumais, Improved string matching under noisy channel conditions, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA
C. E. R. Alves , E. N. Cáceres , F. Dehne, Parallel dynamic programming for solving the string editing problem on a CGM/BSP, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada
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
Jason Tsong-Li Wang , Gung-Wei Chirn , Thomas G. Marr , Bruce Shapiro , Dennis Shasha , Kaizhong Zhang, Combinatorial pattern discovery for scientific data: some preliminary results, ACM SIGMOD Record, v.23 n.2, p.115-125, June 1994
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
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
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
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
S. Muthukrishnan , Krishna Palem, Non-standard stringology: algorithms and complexity, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.770-779, May 23-25, 1994, Montreal, Quebec, Canada
Claudia Pearce , Charles Nicholas, Generating a dynamic hypertext environment with n-gram analysis, Proceedings of the second international conference on Information and knowledge management, p.148-153, November 01-05, 1993, Washington, D.C., United States
Yuen-Hsien Tseng, Content-based retrieval for music collections, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.176-182, August 15-19, 1999, Berkeley, California, United States
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
A. Prasad Sistla , Tao Hu , Vikas Chowdhry, Similarity based retrieval from sequence databases using automata as queries, Proceedings of the eleventh international conference on Information and knowledge management, November 04-09, 2002, McLean, Virginia, USA
Heikki Hyyrö, A bit-vector algorithm for computing Levenshtein and Damerau edit distances, Nordic Journal of Computing, v.10 n.1, p.29-39, 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
Richard L. Kline , Ephraim P. Glinert, Approximate matching algorithms for music information retrieval using vocal input, Proceedings of the eleventh ACM international conference on Multimedia, November 02-08, 2003, Berkeley, CA, USA
Ning-Han Liu , Yi-Hung Wu , Arbee L. P. Chen, Efficient K-NN search in polyphonic music databases using a lower bounding mechanism, Proceedings of the 5th ACM SIGMM international workshop on Multimedia information retrieval, November 07-07, 2003, Berkeley, California
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
Gonzalo Navarro, Regular expression searching on compressed text, Journal of Discrete Algorithms, v.1 n.5-6, p.423-443, October 2003
Maxime Crochemore , Borivoj Melichar , Zdenek Tronícek, Directed acyclic subsequence graph: overview, Journal of Discrete Algorithms, v.1 n.3-4, p.255-280, June 2003
Juha Kärkkäinen , Gonzalo Navarro , Esko Ukkonen, Approximate string matching on Ziv-Lempel compressed text, Journal of Discrete Algorithms, v.1 n.3-4, p.313-338, June 2003
Haifeng Li , Tao Jiang, A class of edit kernels for SVMs to predict translation initiation sites in eukaryotic mRNAs, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.262-271, March 27-31, 2004, San Diego, California, USA
Stefan Burkhardt , Andreas Crauser , Paolo Ferragina , Hans-Peter Lenhof , Eric Rivals , Martin Vingron, q-gram based database searching using a suffix array (QUASAR), Proceedings of the third annual international conference on Computational molecular biology, p.77-83, April 11-14, 1999, Lyon, France
Rodger J. McNab , Lloyd A. Smith , Ian H. Witten , Clare L. Henderson , Sally Jo Cunningham, Towards the digital music library: tune retrieval from acoustic input, Proceedings of the first ACM international conference on Digital libraries, p.11-18, March 20-23, 1996, Bethesda, Maryland, United States
Victoria J. Hodge , Jim Austin, A Comparison of Standard Spell Checking Algorithms and a Novel Binary Neural Approach, IEEE Transactions on Knowledge and Data Engineering, v.15 n.5, p.1073-1081, September 2003
Naoko Kosugi , Yuichi Nishihara , Tetsuo Sakata , Masashi Yamamuro , Kazuhiko Kushima, A practical query-by-humming system for a large music database, Proceedings of the eighth ACM international conference on Multimedia, p.333-342, October 2000, Marina del Rey, California, United States
Dana Shapira , Ajay Daptardar, Adapting the Knuth-Morris-Pratt algorithm for pattern matching in Huffman encoded texts, Information Processing and Management: an International Journal, v.42 n.2, p.429-439, March 2006
J.-M. Champarnaud , F. Coulon, NFA reduction algorithms by means of regular inequalities, Theoretical Computer Science, v.327 n.3, p.241-253, 2 November 2004
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
Korinna Grabski , Tobias Scheffer, Sentence completion, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom
J. T. L. Wang , Q. Ma , D. Shasha , C. H. Wu, New techniques for extracting features from protein sequences, IBM Systems Journal, v.40 n.2, p.426-441, February 2001
Patrick Lambrix , Nahid Shahmehri, Querying Documents using Content, Structure and Properties, Journal of Intelligent Information Systems, v.15 n.3, p.287-307, Nov.-Dec. 2000
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
Yves Lepage , Ando Shin-ichi, Saussurian analogy: a theoretical account and its application, Proceedings of the 16th conference on Computational linguistics, August 05-09, 1996, Copenhagen, Denmark
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
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
David Bainbridge , Michael Dewsnip , Ian H. Witten, Searching digital music libraries, Information Processing and Management: an International Journal, v.41 n.1, p.41-56, January 2005
David Bainbridge, Music information retrieval research and its context at the University of Waikato, Journal of the American Society for Information Science and Technology, v.55 n.12, p.1092-1099, October 2004
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
Hongkun Zhao , Weiyi Meng , Zonghuan Wu , Vijay Raghavan , Clement Yu, Fully automatic wrapper generation for search engines, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan
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
Laali Elkhalifa , Raman Adaikkalavan , Sharma Chakravarthy, InfoFilter: a system for expressive pattern specification and detection over text streams, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Philippe Flajolet , Wojciech Szpankowski , Brigitte Vallée, Hidden word statistics, Journal of the ACM (JACM), v.53 n.1, p.147-183, January 2006
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
Owen de Kretser , Alistair Moffat, SEFT: a search engine for text, Software—Practice & Experience, v.34 n.10, p.1011-1023, August 2004
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
Lin Xu , Curtis Dyreson, Approximate retrieval of XML data with ApproXPath, Proceedings of the nineteenth conference on Australasian database, December 03-04, 2007, Gold Coast, Australia
Westley Weimer, Patches as better bug reports, Proceedings of the 5th international conference on Generative programming and component engineering, October 22-26, 2006, Portland, Oregon, USA
Robert Gwadera , Mikhail J. Atallah , Wojciech Szpankowski, Reliable detection of episodes in event sequences, Knowledge and Information Systems, v.7 n.4, p.415-437, May 2005
Stoyan Mihov , Klaus U. Schulz, Fast Approximate Search in Large Dictionaries, Computational Linguistics, v.30 n.4, p.451-477, December 2004
Hongkun Zhao , Weiyi Meng , Clement Yu, Automatic extraction of dynamic record sections from search engine result pages, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
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
Farooq Ahmad , Grzegorz Kondrak, Learning a spelling error model from search query logs, Proceedings of the conference on Human Language Technology and Empirical Methods in Natural Language Processing, p.955-962, October 06-08, 2005, Vancouver, British Columbia, Canada
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
Cédric du Mouza , Philippe Rigaux , Michel Scholl, Parameterized pattern queries, Data & Knowledge Engineering, v.63 n.2, p.433-456, November, 2007
Ying-Dar Lin , Kuo-Kun Tseng , Tsern-Huei Lee , Yi-Neng Lin , Chen-Chou Hung , Yuan-Cheng Lai, A platform-based SoC design and implementation of scalable automaton matching for deep packet inspection, Journal of Systems Architecture: the EUROMICRO Journal, v.53 n.12, p.937-950, December, 2007
Udi Manber, Finding similar files in a large file system, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.2-2, January 17-21, 1994, San Francisco, California
Udi Manber , Sun Wu, GLIMPSE: a tool to search through entire file systems, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.4-4, January 17-21, 1994, San Francisco, California
Udi Manber , Mike Smith , Burra Gopal, WebGlimpse: combining browsing and searching, Proceedings of the Annual Technical Conference on Proceedings of the USENIX 1997 Annual Technical Conference, p.15-15, January 06-10, 1997, Anaheim, California
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
Hai He , Weiyi Meng , Clement Yu , Zonghuan Wu, Wise-integrator: an automatic integrator of web search interfaces for E-commerce, Proceedings of the 29th international conference on Very large data bases, p.357-368, September 09-12, 2003, Berlin, Germany
Chee-Yong Chan , Minos Garofalakis , Rajeev Rastogi, RE-Tree: an efficient index structure for regular expressions, Proceedings of the 28th international conference on Very Large Data Bases, p.251-262, August 20-23, 2002, Hong Kong, China
Bozena Kostek , Jaroslaw Wojcik, Machine learning system for estimating the rhythmic salience of sounds, International Journal of Knowledge-based and Intelligent Engineering Systems, v.9 n.4, p.275-284, December 2005
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
Tamer Kahveci , Ambuj K. Singh, Efficient Index Structures for String Databases, Proceedings of the 27th International Conference on Very Large Data Bases, p.351-360, September 11-14, 2001
Rakesh Agrawal , King-Ip Lin , Harpreet S. Sawhney , Kyuseok Shim, Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases, Proceedings of the 21th International Conference on Very Large Data Bases, p.490-501, September 11-15, 1995
Rakesh Agrawal , Giuseppe Psaila , Edward L. Wimmers , Mohamed Zaït, Querying Shapes of Histories, Proceedings of the 21th International Conference on Very Large Data Bases, p.502-514, September 11-15, 1995
Chee-Yong Chan , Minos Garofalakis , Rajeev Rastogi, RE-tree: an efficient index structure for regular expressions, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.102-119, August 2003
Rodger J. McNab , Lloyd A. Smith , Ian H. Witten , Clare L. Henderson, Tune Retrieval in the Multimedia Library, Multimedia Tools and Applications, v.10 n.2-3, p.113-132, April 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
András Kornai, Extended finite state models of language, Natural Language Engineering, v.2 n.4, p.287-290, December 1996
H. Blume , H.-M. Blüthgen , C. Henning , P. Osterloh , T. G. Noll, Embedding of Dedicated High-Performance ASICs into Reconfigurable Systems Providing Additional Multimedia Functionality, Journal of VLSI Signal Processing Systems, v.31 n.2, p.117-126, June 2002
Christopher L. Hayes , Yan Luo, DPICO: a high speed deep packet inspection engine using compact finite automata, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, December 03-04, 2007, Orlando, Florida, USA
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
Kuo-Kun Tseng , Ying-Dar Lin , Tsern-Huei Lee , Yuan-Cheng Lai, Deterministic high-speed root-hashing automaton matching coprocessor for embedded network processor, ACM SIGARCH Computer Architecture News, v.35 n.3, p.36-43, June 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
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
Heikki Hyyrö, Improving the bit-parallel NFA of Baeza-Yates and Navarro for approximate string matching, Information Processing Letters, v.108 n.5, p.313-319, November, 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
Christophe Cerisara, Automatic discovery of topics and acoustic morphemes from speech, Computer Speech and Language, v.23 n.2, p.220-239, April, 2009
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
Geoffrey Peters , Caroline Anthony , Michael Schwartz, Song search and retrieval by tapping, Proceedings of the 20th national conference on Artificial intelligence, p.1696-1697, July 09-13, 2005, Pittsburgh, Pennsylvania
Kuo-Kun Tseng , Yuan-Cheng Lai , Ying-Dar Lin , Tsern-Huei Lee, A fast scalable automaton-matching accelerator for embedded content processors, ACM Transactions on Embedded Computing Systems (TECS), v.8 n.3, p.1-30, April 2009
N. R. Brisaboa , A. Fariña , G. Navarro , J. R. Parama, New adaptive compressors for natural language text, Software—Practice & Experience, v.38 n.13, p.1429-1450, November 2008

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Text processing


General Terms:
Algorithms


Keywords:
approximate string matching, information retrieval, pattern matching, software tools, string searching


REVIEW

"Wilfred J. Hansen : Reviewer"

The simple string matching problem is to find an exact match for a pattern string in some text corpus. Fast, special-purpose algorithms solve this problem in time On/m more...

Collaborative Colleagues:
Sun Wu: colleagues
Udi Manber: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player