Algorithms on Strings

Description

This text and reference on string processes and pattern matching presents examples related to the automatic processing of natural language, to the analysis of molecular sequences and to the management of textual databases. Algorithms are described in a C-like language, with correctness proofs and complexity analysis, to make them ready to implement. The book will be an important resource for students and researchers in theoretical computer science, computational linguistics, computational biology, and software engineering. Cover Contents Preface 1 - Tools 1.1 - Strings and automata Alphabet and strings Languages Regular expressions and languages Automata 1.2 - Some combinatorics Some specific strings Periodicity and borders Powers, primitivity and conjugacy 1.3 - Algorithms and complexity Writing conventions of algorithms Pattern matching algorithms Expression of complexity Some standard objects 1.4 - Implementation of automata Full implementations Reduced implementations A complete example 1.5 - Basic pattern matching techniques Notion of sliding window The naive algorithm Heuristics Search engine Bit-vector model 1.6 - Borders and prefixes tables Table of borders Table of prefixes Relation between borders and prefixes Notes Exercises 2 - Pattern matching automata 2.1 - Trie of a dictionary 2.2 - Searching for several strings Dictionary automaton Construction of the dictionary automaton Output of the occurrences Implementation by transition matrix 2.3 - Implementation with failure function Definition of the implementation Searching phase Construction of the implementation Optimization of the failure function 2.4 - Implementation with successor by default Size of the implementation Construction of the implementation Searching phase Challenge of implementations 2.5 - Locating one string 2.6 - Locating one string and failure function Properties of the optimized failure function Implementation of the failure functions with tables Searching phase 2.7 - Locating one string and successor by default Construction of the implementation Searching phase Challenge of implementations for searching for one string Notes Exercises 3 - String searching with a sliding window 3.1 - Searching without memory Searching phase Weak version 3.2 - Searching time 3.3 - Computing the good suffix table Algorithm Complexity of the computation 3.4 - Automaton of the best factor 3.5 - Searching with one memory Searching phase Running time of the searching phase 3.6 - Searching with several memories Searching phase Complexity of the searching phase 3.7 - Dictionary searching Notes Exercises 4 - Suffix arrays 4.1 - Searching a list of strings Interval problem Membership problem 4.2 - Searching with the longest common prefixes 4.3 - Preprocessing the list 4.4 - Sorting suffixes 4.5 - Sorting suffixes on bounded integer alphabets 4.6 - Common prefixes of the suffixes Notes Exercises 5 - Structures for indexes 5.1 - Suffix trie Suffix links 5.2 - Suffix tree 5.3 - Contexts of factors Suffix function Evolution of the congruence 5.4 - Suffix automaton Size of the automaton Suffix link and suffix paths Online construction Complexity 5.5 - Compact suffix automaton Notes Exercises 6 - Indexes 6.1 - Implementing an index 6.2 - Basic operations Position Number of factors List of positions 6.3 - Transducer of positions 6.4 - Repetitions 6.5 - Forbidden strings 6.6 - Search machine Lengths of the common factors Optimization of the suffix link 6.7 - Searching for conjugates Notes Exercises 7 - Alignments 7.1 - Comparison of strings Edit distance and edit operation Alignments Edit graph Dotplot 7.2 - Optimal alignment Computation of the edit distance Computation of an optimal alignment Computation of all the optimal alignments Automaton of the optimal alignments 7.3 - Longest common subsequence Computation by dynamic programming Computation of the length in linear space Computation of a longest subsequence in linear space 7.4 - Alignment with gaps 7.5 - Local alignment Similarity Computation of an optimal local alignment 7.6 - Heuristic for local alignment Notes Exercises 8 - Approximate patterns 8.1 - Approximate pattern matching with jokers Jokers only in the string Jokers in the text and in the string 8.2 - Approximate pattern matching with differences Dynamic programming Diagonal monotony Partial computation Diagonal computation Execution time of the diagonal computation 8.3 - Approximate pattern matching with mismatches Search automaton Specific implementation Complexity of the searching phase Merge Correctness proof Preprocessing 8.4 - Approximate matching for short patterns Exact string matching One mismatch One insertion One deletion Short patterns with differences 8.5 - Heuristic for approximate pattern matching with differences Notes Exercises 9 - Local periods 9.1 - Partitioning factors 9.2 - Detection of powers Computation of local powers Number of occurrences of local powers 9.3 - Detection of squares Existence of a square Number of prefix or factor squares 9.4 - Sorting suffixes Incremental computation of the ranks of the suffixes Computation of the common prefixes Notes Exercises Bibliography Books Collections of articles Web sites Applications Algorithmics and combinatorics Articles Index