String Matching (14)

John Reif

November 12th, 1998

1 STRING MATCHING

1.1 Matching Strings

see the seven seas seashells by the seashore. Find all occurrences of seas. Common problem to lots of applications:

• UNIX grep

• Word processors

• Web searching

• DNA

1.2 Alphabets

The alphabet is the set of symbols Σ.

• English Σ = {a, b, c, d, ..., x, y, z}

• ASCII 256 symbols, UNICODE 65536 symbols

• DNA Σ = {A, C, G, T }

Set of all strings: Σ^{∗} Size of alphabet: |Σ|

1.3 Notation

Let P be a string in Σ^{∗}. P [i..j]: Array range notation character i to j inclusive indexed from 1 to length of string. |P | denotes the length of string P. AB is the concatenation of strings A and B. Q ⊏ R: the string Q is a prefix of R. R = QS for some S.

                               Q = abc
                               R = abcbbca
                               S = bbca

Q ⊐ R: the string Q is a suffix of R. R = SQ for some S.

                               Q = bca
                               R = abcbbca
                               S = abcb

1.4 The String Matching Problem

Given a pattern string P ∈ Σ^{∗}, with length |P | = m and a text string T ∈ Σ^{∗}, with length |T | = n, where m, n > 0 and m ≤ n: If P occurs as a substring of T, find the first occurrence—that is, find s such that T [s + 1..s + m] = P [1, m] (0 ≤ s ≤ n − m).

1.5 Extensions

Other related problems:

• Find all matches

• Find multiple patterns

• Wildcard matching

• Formatting

2 NAIVE PATTERN MATCHER

2.1 Examples

First thing you’d try:

                  P = abc
                  T = abaccbabacbaabcabacabacccaabbca . . .
                   . = abc
                   . = abc
                   . = abc

. =  abc …

Test the pattern at every position of the text.

2.2 Algorithm

Naive-Pattern-Matcher(T, P)

1 n ← length[T]
2 m ← length[P]
3 for s ← 0 to n − m
4  do j ← 1
5  while j ≤ m and P [j] = T [s + j]
6  do j ← j + 1
7  if j > m
8  then print “Pattern occurs at shift′′ s

2.3 Analysis

Remember that |P | = m, |T | = n. Inner loop will take m steps to confirm the pattern matches Outer loop will take n − m + 1 steps Therefore, worst case is Θ((n − m + 1)m)

2.4 More Analysis

When does the worst case occur?

     T = aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa . . .. P = aaaaaa.

When does the best case occur?

     T = aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa . . .. P = bbbbbb.

2.5 Intuition for Improvement

When could the Naive Algorithm do better?

                  T = aaaaaaaabaaaaaaaaaaaaaaaaaaaaaa . . .
                     = aaaaaaaaa
                     = aaaaaaaaa
                     = aaaaaaaaa
                     =  aaaaaaaaa . . .

Use information that is gathered in comparisons to motivate larger shifts than 1 (e.g., here we’d like to shift |P |)

3 BOYER-MOORE

3.1 Naive Algorithm Again

Naive-Pattern-Matcher-2(T, P)

1 n ← length[T]
2 m ← length[P]

3 4

5 s ← 0
6 while s ≤ n − m
7  do j ← m
8  while j > 0 and P [j] = T [s + j]
9  do j ← j − 1
10  if j = 0
11  then print “Pattern occurs at shift” s
12  s ← s + 1
13  else s ← s + 1

Same algorithm as before, but check P right-to-left instead. When would this alone help?

When the last character in the pattern is rare. Fast jumps!

3.2 Boyer-Moore Algorithm

Boyer-Moore-Matcher(T, P, Σ)

1 n ← length[T]
2 m ← length[P]
3 λ ← Compute-Last-Occurrence-Function(P, m, Σ)
4 γ ← Compute-Good-Suffix-Function(P, m)
5 s ← 0
6 while s ≤ n − m
7  do j ← m
8  while j > 0 and P [j] = T [s + j]
9  do j ← j − 1
10  if j = 0
11  then print “Pattern occurs at shift” s
12  s ← s + γ[0]
13  else s ← s + max(γ[j], j − λ[T [s + j]])

Heuristics must have the property that they don’t miss any matches.

3.3 Bad-Character Heuristic

In the case of a mismatch, P [j] ≠ T [s + j]: Look for the occurrence of mismatch character in the pattern, such that P [k] = T [s + j]. Three cases: k = 0: The character occurs nowhere in the pattern

aaac........
aaaaaa
    aaaaaa

k < j: The rightmost occurrence of the bad character is to the left of j

aaacaa........
acaaaa
  acaaaa

k > j: The rightmost occurrence of the bad character is to the right of j

..aaacac........
  aaaaac
aaaaac

3.4 Bad-Character Heuristic Analysis

In every case, we propose a shift of j − k. Negative values occur for case 3, but the other heuristic is always greater than 0, so the max guarantees progress. Define λ[a] to be the index of the right-most index of a in P. If a ∉ P then λ[a] = 0. Then j − λ[T [s + j]] is the bad-character shift we want. (j is current offset from s in T, T [s + j] is the current character.)

3.5 Bad-Character Heuristic Algorithm

Compute the λ mapping. Compute-Last-Occurrence-Function(P, m, Σ)

1 for each a ∈ Σ
2  do λ[a] = 0
3 for j ← 1 to m
4  do λ[P [j]] ← j

Running time is O(|Σ| + m).

3.6 When does it help?

How much can the Bad-Character Heuristic help? How likely is this in English?

3.7 Good-Suffix Heuristic

Use the fact that we know that a suffix of the pattern P matched:

T = abbbaabab
           ||
P =    cabaab
P =       cabaab

Propose to shift the pattern to the right by the least amount that guarantees not to skip any occurrence of the good-suffix already matched. Define γ to be the shift proposed by the good-suffix heuristic.

3.8 Prefix Function

P_{k} refers to the first k characters of P (the k length prefix of P). P_{m} = P

                               P = aababddc

P_{1} = a
P_{2} = aa

                              P_{3} = aab

etc. Given a pattern P [1, m], define the prefix-function π: π[j] = max{k : k < j and P_{k} ⊐ P_{j}} Example.

3.9 Computing the Prefix Function

With amortized analysis, can show that computing the prefix-function is O(m). For more informaiton, see the book, pages 871–874.

3.10 Similarity Relation

Define Q ∼ R (“Q is similar to R”) to mean Q ⊏ R or R ⊏ Q.

R =      bcba
Q = bbbbbbcba

If ∼, can align strings at right and some suffix will match.

3.11 Good-Suffix Heuristic

Propose to shift the pattern to the right by the least amount that guarantees not to skip any occurrence of the good-suffix already matched.

T = abbbaabab
           ||
P =    cabaab
P =       cabaab

γ[j] = m − max{k : 0 ≤ k < m and P [j + 1..m] ∼ P_{k}}. In example above, j = 4, want maximum k such that P [5..6] = ab ∼ P_{k}.

P_{1} = c
P_{2} = ca

                                P_{3} = cab
                                P_{4} = caba
                                P_{5} = cabaa

So, γ[4] = 3.

3.12 Good-Suffix Heuristic Algorithm

The resulting definition of the Good-Suffix Heuristic: γ[j] = min({m − π[m]} ∪ {l − π′ : 1 ≤ l ≤ m and j = m − π′[l]}) Implentation of this defintion: Compute-Good-Suffix-Function(P, m)

1 π ← Compute-Prefix-Function(P)
2 P′ ← reverse(P)
3 π′ ← Compute-Prefix-Function(P′)
4 for j ← 0 to m
5  do γ[j] ← m − π[m]
6 for l ← 1 to m
7  do j ← m − π′[l]
8  if γ[j] > l − π′[l]
9  then γ[j] ← l − π′[l]
10 return

3.13 Analysis of Compute-Good-Suffix-Function

Compute-Prefix-Function takes O(m) and two loops both of which are O(m). Therefore, Compute-Good-Suffix-Function is O(m)

3.14 Analysis of Boyer-Moore

Compute-Last-Occurrence-Function is O(m + |Σ|) Compute-Good-Suffix-Function is O(m) so Boyer-Moore-Matcher is O((n − m + 1)m + |Σ|) So, theoretically no better than Naive (actually a little worse), but in practice it seems to do better.

4 STRING MATCHING WITH FINITE AUTOMATA

4.1 Finite Automata

A finite automaton M has:

• Q is a finite set of states

• q_{0} ∈ Q is the start state

• A ⊆ Q is the set of accepting states

• Σ is the finite input alphabet

• δ is the transition function. Maps a state and an input symbol to another state.

4.2 Example

A finite automaton begins in the start state, reads input symbols, making transitions based on these symbols. When the input sequence terminates, if it is in an accepting state, the automaton is said to accept that input string, otherwise the input is rejected. Define a function ϕ called the final-state function, which ϕ(w) is the state that M is in after processing w.

4.3 The Suffix-Function

Given a pattern P [1..m], define the suffix-function σ such that σ(x) is the length of the longest prefix of P that is also a suffix of x: σ(x) = max {k : P_{k} ⊐ x}

                                   P = abaabc

P_{1} = a
P_{2} = ab

                                  P_{3} = aba
                                  P_{4} = abaa
                            σ(abbaba) = aba

4.4 String-Matching Automata

For a given pattern P, we can define its string-matching automata:

• Q = {0, …, m} (states)

• q_{0} = 0 (start state)

• A = {m} (accepting state)

• δ(q, a) = σ(P_{q}a)

The transition function chooses the next state to maintain the invariant: ϕ(T_{i}) = σ(T_{i}) after scanning in the first i characters, the state number is the longest prefix of P that is also a suffix of T_{i}.

4.5 Finite-Automaton-Matcher

Finite-Automaton-Matcher(T, δ, m)

1 n ← length[T]
2 q ← 0
3 for i ← 1 to n
4  do q ← δ(q, T [i])
5  if q = m
6  then s ← i − m
7  print “Pattern occurs at shift” s

This is clearly O(n) since we take one step for each symbol of T. So, this seems better than the others? Why not use this?

4.6 Computing the transition function

This can be done according to its definition, and takes O(m^{3}|Σ|). More clever versions can achieve O(m|Σ|). This brings the total running time for Finite-Automaton-Matcher to O(n + m|Σ|). Actually, not too bad if pattern is small relative to the size of the text.