Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological SequencesRecent years have witnessed a dramatic increase of interest in sophisticated string matching problems, especially in information retrieval and computational biology. This book presents a practical approach to string matching problems, focusing on the algorithms and implementations that perform best in practice. It covers searching for simple, multiple and extended strings, as well as regular expressions, and exact and approximate searching. It includes all the most significant new developments in complex pattern searching. The clear explanations, step-by-step examples, algorithm pseudocode, and implementation efficiency maps will enable researchers, professionals and students in bioinformatics, computer science, and software engineering to choose the most appropriate algorithms for their applications. |
Contents
Extended string matching | 77 |
Regular expression matching | 99 |
5 | 115 |
Approximate matching | 145 |
25 | 169 |
Conclusion | 185 |
| 207 | |
| 208 | |
| 219 | |
Other editions - View all
Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms ... Gonzalo Navarro,Mathieu Raffinot No preview available - 2007 |
Common terms and phrases
ABNDM active AG|AAA Agrep annual approach approximate searching approximate string matching arrows AT|GA ATATA automata bit mask bit-parallel algorithms BNDM Boyer-Moore algorithm Chapter classes of characters complexity compressed text computational biology Computer Science computer word construction corresponding cost Current deterministic diagonal dynamic programming edit distance efficient exact string matching example extended strings ɛ-transitions factor oracle Figure function Glushkov automaton Grep initial self-loop L(RE length Line lmin mark an occurrence matching algorithms multipattern search MultiStringRE node O(mn obtained on-line operations optional characters pattern matching Pref prefix Preprocessing problem pseudo-code Reading A B[A Reading G recognizes regular expression report an occurrence represent search algorithm Section self-loop sequences set of strings shift the window Shift-And Shift-Or simulation space suffix automaton technique text character text position Thompson transitions tree representation trie verification window by last worst-case
Popular passages
Page 207 - A. Amir, G. Benson, and M. Farach. Let sleeping files lie: Pattern matching in Zcompressed files.
Page 212 - In Proceedings of the 14th Annual Symposium on Theoretical Aspects of Computer Science, pages 319-328.
Page 210 - Proceedings of the 5th Annual Symposium on Combinatorial Pattern Matching, number 807 in Lecture Notes in Computer Science, pages 259-273, Asilomar, CA, 1994.
Page 208 - J. Karkkainen and E. Ukkonen. Lempel-Ziv parsing and sublinear-size index structures for string matching. In N. Ziviani, R. Baeza-Yates, and K. Guimaraes, editors, Proceedings of the 3rd South American Workshop on String Processing, pages 141-155, Recife, Brazil, 1996.
Page 209 - Gonnet. Fast text searching for regular expressions or automaton searching on tries. Journal of the ACM, 43(6):915-936, 1996.
Page 210 - C.-H. Chang and R. Paige. From regular expression to DFA's using NFA's. In Proceedings of the 3rd Annual Symposium on Combinatorial Pattern Matching, number 664 in Lecture Notes in Computer Science, pages 90-110.