String Searching Algorithms

Description

String searching is a subject of both theoretical and practical interest in computer science. This book presents a bibliographic overview of the field and an anthology of detailed descriptions of the principal algorithms available. The aim is twofold: on the one hand, to provide an easy-to-read comparison of the available techniques in each area, and on the other, to furnish the reader with a reference to in-depth descriptions of the major algorithms. Topics covered include methods for finding exact and approximate string matches, calculating 'edit' distances between strings, finding common sequences and finding the longest repetitions within strings. For clarity, all the algorithms are presented in a uniform format and notation. Preface Contents List of Figures Introduction Some Definitions Algorithm Presentation Chapter Preview String Matching 2.1 Overview 2.1.1 Brute Force 2.1.2 Knuth-Morris-Pratt and Beyer-Moore Approaches 2.1.3 Hashing Functions 2.1.4 Comparative Performance Space Optimality 2.1.5 Popularity 2.1 .6 Multiple-String Searches 2.2 Algorithms in Detail 2.2.1 Brute Force 2.2.2 Knuth-Morris-Pratt 2.2.3 Beyer-Moore 2.2.4 Boyer-Moore-Horspool 2.2.5 Sunday - Quick Search, Maximal Shift, and Optimal Mismatch 2.2.6 Hume and Sunday- Tuned Boyer-Moore and Least Cost 2.3 Further Reading String Distance and Common Sequences 3.1 Overview 3.1.1 String Distance Measures 3.1.2 String Distance and Longest Common Subsequence 3.1.3 Comparative Performance 3.1.4 Related Problems 3.2 Algorithms in Detail 3.2.1 Wagner-Fischer 3.2.2 Hirschberg 3.2.3 Hunt-Szymanski 3.2.4 Masek-Paterson 3.2.5 Ukkonen 3.2.6 Heaviest Common Subsequence 3.3 Further Reading Suffix Trees 4.1 Overview 4.1.1 Suffix Tries 4.1.2 From Suffix Trie to Suffix Tree 4.2 Algorithms in Detail 4.2. 1 Brute Force 4.2.2 McCreight 4.2.3 Ukkonen 4.3 Further Reading Approximate String Matching 5.1 Overview 5.1 .1 String Matching with k Mismatches 5.1.2 String Matching with k Differences 5.1.3 String Matching with Don't-Cares 5.1.4 Application Areas 5.1.5 Dedicated Hardware and Parallel Algorithms 5.2 Algorithms in Detail 5.2.1 Landau-Vishkin k-mismatches 5.2.2 Shift-Add 5.2.3 Tarhio-Ukkonen k-mismatches 5.2.4 Baeza-Yates-Perleberg k-mismatches 5.2.5 Dynamic Programming k-differences 5.2.6 Landau-Vishkin k-differences 5.2. 7 Chang-Lawler k-differences 5.2.8 Chang-Lampe k-differences 5.2.9 Wu-Manber k-differences 5.3 Further Reading Repeated Substrings 6.1 Overview 6.1 .1 Repetitions 6.1.2 Longest Repeated Substrings 6.2 Algorithms in Detail 6.2.1 Brute Force 6.2.2 Suffix Trees Appendix Asymptotic Notation String Symbology Glossary Bibliography Index