Pattern Matching Algorithms

 Pattern Matching Algorithms:

 There are various algorithms used to implement the pattern matching problem.

Some of them are:

1. Brute Force.
2. Boyer-Moore.
3. Knuth-Morris-Pratt (KMP).

 Brute Force:

 The elements of the array come from a set _ called the alphabet; the elements themselves are called characters. Common examples are ASCII text, where each character is an seven-bit integer1, strands of DNA, where the alphabet is the set of nucleotides {A,C, G, T}, or proteins, where the alphabet is the set of 22 amino acids.

The problem we want to solve is the following. Given two strings, a text T[1 .. n] and a pattern P[1 ..m], find the first substring of the text that is the same as the pattern. (It would be easy to extend our algorithms to find all matching substrings, but we will resist.) A substring is just a contiguous subarray. For any shift s, let Ts denote the substring T[s .. s +m− 1]. So more formally, we want to find the smallest shift s such that Ts = P, or report that there is no match.

For example,if the text is the string ‘AMANAPLANACATACANALPANAMA’2 and the pattern is ‘CAN’, then the output should be 15. If the pattern is ‘SPAM’, then the answer should be ‘none’. In most cases the pattern is much smaller than the text; to make this concrete, I’ll assume that m < n/2. Here’s the ‘obvious’ brute force algorithm, but with one immediate improvement. The inner while loop compares the substring Ts with P. If the two strings are not equal, this loop stops at the first character mismatch.

 ALGORITHM: Brute_Force(T[1 .. n], P[1 ..m]):

For    s

equal 

i 

while equal and i <= m

if T[s + i − 1] != P[i]

equal

else

i

if equal

return s

return ‘none’

Boyer-Moore algorithm:

The Boyer-Moore algorithm (Boyer & Moore 1977) is considered one of the most efficient algorithms for general pattern matching applications. It is able to recognize and skip certain areas in the text where no match would be possible.

The pattern is shifted from left to right across the text, as in brute-force pattern matching, but comparison is performed from right to left on the pattern. As soon as a mismatch is detected, the pattern is shifted to the right according to one of two key heuristics: the extended bad character rule and the good suffix rule.

To illustrate the operation of these heuristics, suppose that the pattern, P, is aligned at position k of T, and that a mismatch has been detected between the character at position i of the pattern that is, P[i] 6= T[k + i − 1]. Then let c = T[k + i − 1], the mismatched character of the text, and t = P[i + 1: : :m], the suffix of the pattern which matches the corresponding portion of the text.

The extended bad character rule proposes that if there is an occurrence of c in P to the left of i,  hat the pattern be shifted so that the two occurrences of c are aligned. If no such shift is possible, the pattern is shifted completely past the c in the text.

The good suffix rule attempts to align the matched suffix, t, with a previous occurrence of t in the pattern (for example, in the pattern reduced, the suffixed occurs twice). If there are no other occurrences of t in the pattern, then the pattern is e shifted so that the a prefix of the pattern matches a suffix of t in the text, or, if this is not possible, shifted completely past t.

The Boyer-Moore algorithm checks both of these heuristics at each stage of the matching process; if both shifts are possible, then the maximum is chosen. In this way, Boyer-Moore achieves so-called `sub-linear' performance for most texts.

To apply the Boyer-Moore algorithm to the permuted output of the Burrows-Wheeler transform, we de_ne an array Hr to relate the characters in T with their position in F, such that 8i : 1 _ i _ n; T[i] = F[Hr[i]]

The Hr array can be computed e_ciently with the following procedure:

Compute-Hr-Array(W; id)

1. i   id

2. for j   1 to n do

3. i   W[i]

4. Hr[j]   i

5. end for

where id is the index of the _rst character in L, obtained from the BWT output.

The Hr array introduces the possibility of accessing random characters in the permuted string. Using this technique, we have implemented a Boyer-Moore algorithm for BWT by adapting a standard Boyer-Moore routine to access character i at F[Hr[i]] instead of at T[i]. The asymptotic complexity is the same for this approach as for Boyer-Moore on uncompressed text, although in practice it is a little slower, due to the time taken to construct Hr, and an extra dereference each time a character is needed.

 KMP String Matching Algorithm: Plan 

• We maintain two indices, ` and r, into the text string.
• We iteratively update these indices and detect matches such that the following loop invariant is maintained – KMP Invariant: ` · r, t[`..r] = p[0..r − `], and all occurrences of the pattern p starting prior to ` in the text t have been detected
• We ensure that the invariant holds initially by setting ` and r to zero.
• Remark: We will see later that the algorithm also requires a preprocessing phase involving only the pattern string p Achieving Linear Time Complexity: The Plan
• The algorithm performs only a constant amount of computation in each iteration
• The algorithm never decreases ` or r
• In each iteration, either ` or r is increased
• Note that the indices ` and r are at most t
• By the KMP invariant, all matches have been detected once ` reaches t, so we can terminate at that point
• The preprocessing phase, which involves only p, runs in O(p) time

KMP Iteration:

• Let’s see how to define an iteration of the KMP loop
• Assume the KMP invariant holds at the beginning of the iteration
• Since the loop has not terminated, ` < t
• We’d like to increase ` or r, while maintaining the invariant
• There are two cases to consider
• Case 1: 0 · r − ` < p, i.e., we do not yet know whether there is a match starting at index `
• Case 2: r − ` = p, i.e., we have found a match starting at index `

Case 1: 0 · r − ` < p

• Case 1.1: t[r] = p[r − `]

– We’ve matched another symbol; increment r

• Case 1.2: r = ` and t[r] 6= p[r − `]

– Our current match is the empty string and the next symbol does not

match p[0]; increment ` and r

• Case 1.3: r > ` and t[r] 6= p[r − `]

– Our current match is a nonempty proper prefix of p and the next

symbol does not extend this match

• – How should we update ` and r in this remaining subcase?

Case 2: r − ` = p

• We output that a match exists starting at index `
• How do we update ` and r?
• Note that this case is very similar to Case 1.3 treated earlier
• We increase ` by p − c(p)