Pattern Matching Algorithms

Name: Pattern Matching Algorithms
Brand: OUP eBook
Price: 162.99 EUR
Availability: OnlineOnly

Alberto Apostolico Zvi Galil(Editor)

OUP eBook (Publisher)

1st Edition

Published on 29. May 1997

394 pages

E-Book

PDF with Adobe-DRM

System requirements

978-0-19-535434-8 (ISBN)

€162.99incl. 7% vat

System requirements

for PDF with Adobe-DRM

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

Intro
Contents
1 Off-line Serial Exact String Searching
1.1 Searching for strings in texts
1.2 Sequential searches
1.2.1 String-Matching Automaton
1.2.2 Forward Prefix scan
1.2.3 Forward Subword scan
1.3 Practically fast searches
1.3.1 Reverse-Suffix scan
1.3.2 Reverse-Prefix scan
1.4 Space-economical methods
1.4.1 Constant-space searching algorithm
1.4.2 Computing a critical factorization
1.4.3 Computing the period of the pattern
1.5 Heuristics for practical implementations
1.6 Exercises
1.7 Bibliographic notes
2 Off-line Parallel Exact String Searching
2.1 Preliminaries
2.2 Application of sequential techniques
2.3 Periodicities and witnesses
2.3.1 Witnesses
2.3.2 Computing and using witnesses in O(log log m) time
2.3.3 A Lower Bound for the CRCW-PRAM
2.4 Deterministic Samples
2.4.1 Faster text search using DS
2.5 The fastest known CRCW-PRAM algorithm
2.5.1 Computing deterministic samples in constant time
2.5.2 Applying DS to obtain the fastest algorithms
2.5.3 A new method to compute witnesses : Pseudo-periods
2.5.4 A constant expected time algorithm
2.6 Fast optimal algorithms on weaker models
2.6.1 Optimal algorithm on the EREW-PRAM
2.7 Two dimensional pattern matching
2.8 Conclusion and open questions
2.9 Exercises
2.10 Bibliographic notes
3 On-line String Searching
3.1 Subword trees
3.2 McCreight's algorithm
3.3 Storing suffix trees
3.4 Building suffix trees in parallel
3.4.1 Preprocessing
3.4.2 Structuring D[sub(x)]
3.4.3 Refining D[sub(x)]
3.4.4 Reversing the edges
3.5 Parallel on-line search
3.6 Exhaustive on-line searches
3.6.1 Lexicographic lists
3.6.2 Building lexicographic lists
3.6.3 Standard representations for constant-time queries
3.7 Exercises
3.8 Bibliographic notes
4 Serial Computations of Levenshtein Distances
4.1 Levenshtein distance and the LCS problem
4.2 Classical algorithm
4.3 Non-parameterized algorithms
4.3.1 Linear space algorithm
4.3.2 Subquadratic algorithm
4.3.3 Lower bounds
4.4 Parameterized algorithms
4.4.1 pn algorithm
4.4.2 Hunt-Szymanski algorithm
4.4.3 nD algorithm
4.4.4 Myers algorithm
4.5 Exercises
4.6 Bibliographic notes
5 Parallel Computations of Levenshtein Distances
5.1 Edit distances and shortest paths
5.2 A monotonicity property and its use
5.3 A sequential algorithm for tube minima
5.4 Optimal EREW-PRAM algorithm for tube minima
5.4.1 EREW-PRAM computation of row minima
5.4.2 The tube minima bound
5.4.3 Implications for string editing
5.5 Optimal CRCW-PRAM algorithm for tube minima
5.5.1 A preliminary algorithm
5.5.2 Decreasing the work done
5.5.3 Further remarks
5.6 Exercises
5.7 Bibliographic notes
6 Approximate String Searching
6.1 The serial algorithm
6.1.1 The dynamic programming algorithm
6.1.2 An alternative dynamic programming computation
6.1.3 The efficient algorithm
6.2 The parallel algorithm
6.3 An algorithm for the LCA problem
6.3.1 Reducing the LCA problem to a restricted-domain range-minima problem
6.3.2 A simple sequential LCA algorithm
6.4 Exercises
6.5 Bibliographic notes
7 Dynamic Programming: Special Cases
7.1 Preliminaries
7.2 Convexity and concavity
7.2.1 Monge conditions
7.2.2 Matrix searching
7.3 The one-dimensional case (1D/1D)
7.3.1 A stack or a queue
7.3.2 The effects of SMAWK
7.4 The two-dimensional case
7.4.1 A coarse divide-and-conquer
7.4.2 A fine divide-and-conquer
7.5 Sparsity
7.5.1 The sparse 2D/0D problem
7.5.2 The sparse 2D/2D problem
7.6 Applications
7.6.1 Sequence alignment
7.6.2 RNA secondary structure
7.7 Exercises
7.8 Bibliographic notes
8 Shortest Common Superstrings
8.1 Early results: NP-hardness and some special cases
8.1.1 NP-hardness
8.1.2 A special case: strings of length 2
8.1.3 A detour: compression measure
8.2 An O(n log n) approximation algorithm
8.3 Linear approximation algorithms
8.3.1 Some definitions and simple facts
8.3.2 A simple variant of Greedy achieves 4n
8.3.3 Improving to 3n
8.3.4 A 4n upper bound for Greedy
8.4 A polynomial-time approximation scheme is unlikely
8.5 Dealing with negative strings
8.5.1 A linear approximation algorithm
8.5.2 A non-trivial bound for a greedy solution
8.6 DNA Sequencing and learning of strings
8.6.1 Modelling DNA sequencing via learning
8.6.2 Learning a string efficiently
8.7 Superstrings with flipping
8.8 Exercises
8.9 Bibliographic notes
9 Two Dimensional Matching
9.1 Exact matching
9.1.1 Linear reductions
9.1.2 Periodicity analysis
9.2 Scaled matching
9.2.1 String scaled matching
9.2.2 Two dimensional scaled matching
9.2.3 Partitioning a column into k-blocks
9.3 Compressed matching
9.3.1 Problem definition and algorithm Overview
9.3.2 The compressed matching algorithm
9.4 Exercises
9.5 Bibliographic notes
10 Suffix Tree Data Structures for Matrices
10.1 Suffix trees for square matrices
10.2 Suffix tree construction for square matrices
10.3 Suffix trees for rectangular matrices
10.4 Linear-space construction
10.4.1 NOD-processing
10.4.2 NOD-queries
10.5 Linear expected-time construction
10.5.1 CT's construction
10.5.2 Sorting M' to obtain R
10.6 Exercises
10.7 Bibliographic notes
11 Tree Pattern Matching
11.1 Preliminary definitions and early history
11.1.1 Trees
11.1.2 A brief review of algorithmic results in exact tree matching
11.1.3 Edit operations and edit distance
11.1.4 Early history of approximate tree matching algorithms
11.2 Tree edit and tree alignment algorithms for ordered trees
11.2.1 Notation
11.2.2 Basic tree edit distance computation
11.2.3 Pattern trees with variable length don't cares
11.2.4 Fast parallel algorithms for small differences
11.2.5 Tree alignment problem
11.2.6 Tree pattern discovery problem
11.3 Algorithms and hardness results for unordered trees
11.3.1 Hardness results
11.3.2 Algorithm for tree alignment and a heuristic algorithm for tree edit
11.4 Conclusion
11.5 Exercises
11.6 Bibliographic notes
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
R
S
T
U
V
W
Y
Z

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Pattern Matching Algorithms

Description

More details

Other editions

Additional editions

Content

System requirements