Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences
Recent 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.
What people are saying - Write a review
We haven't found any reviews in the usual places.
Other editions - View all
ABNDM ACGATAT active Agrep Aho-Corasick Aho-Corasick algorithm alphabet annual approach approximate searching arrows ATATA automata backward bit mask bit-parallel algorithms BNDM Boyer-Moore Boyer-Moore algorithm Chapter classes of characters complexity compressed text computational biology computer word construction corresponding Current deterministic diagonal dynamic programming e-transitions edit distance efficient errors exact string matching example extended strings factor oracle factor search function Glushkov automaton Grep hash Horspool algorithm initial self-loop Knuth-Morris-Pratt algorithm L(RE labeled last character Line longest suffix mark an occurrence multipattern search multiple MultiStringRE node O(mn obtained on-line operations pattern matching Preprocessing Pseudo-code Reading G recognizes regular expression represent reverse search algorithm search window Section self-loop sequence set of strings shift the window Shift-And Shift-Or shown in Figure simulation suffix automaton TATAT Td[D technique text character text position transitions tree representation trie verification window by last worst-case
Page 207 - A. Amir, G. Benson, and M. Farach. Let sleeping files lie: Pattern matching in Zcompressed files.
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.