UrbanPro
true

Find the best tutors and institutes for BTech Tuition

Find Best BTech Tuition

Please select a Category.

Please select a Locality.

No matching category found.

No matching Locality found.

Outside India?

Search for topics

Pattern Matching Algorithms

D Subba Rao
23/08/2017 0 0

 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 

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)
0 Dislike
Follow 2

Please Enter a comment

Submit

Other Lessons for You

Lets Talk About Software Design-patterns
What are Design Patterns? Design Pattern is a used and tested solution for a known problem. In simple words, you can say a general reusable solution to a commonly occurring problem within a given context...

Spring - Dependency Injection (DI)
Spring - Dependency Injection (DI) DI is a framework which provides loose coupling in code. Here loose coupling means no hard coding of the object. Instead of hard coding, we will be injecting these object...

Gaurav Kothari | 18/11/2020

1 0
0

Circular Queue
#include <stdio.h> #include <stdlib.h> #define MAX 5 char a; int front = 0, rear = -1, count = 0; void insert() { char item; if(count==MAX) { printf("\n\t\tCircular Queue...

Balaji K | 16/11/2020

0 0
0

Binary Search Tree in C
#include <stdio.h> #include <stdlib.h> struct node { int element; struct node *left; struct node *right; }; struct node *root = NULL; struct node *insert(struct node...

Balaji K | 16/11/2020

0 0
0

Facts about C language
C programming language was developed in 1972 by Dennis Ritchie at AT&T Bell Labs. It was developed to overcome the problems of languages such as B, BPCL. It was developed to write the Unix operating...

Manoj Singh | 03/08/2020

0 0
0
X

Looking for BTech Tuition Classes?

Find best tutors for BTech Tuition Classes by posting a requirement.

  • Post a learning requirement
  • Get customized responses
  • Compare and select the best

Looking for BTech Tuition Classes?

Find best BTech Tuition Classes in your locality on UrbanPro

Post your learning requirement

UrbanPro.com is India's largest network of most trusted tutors and institutes. Over 55 lakh students rely on UrbanPro.com, to fulfill their learning requirements across 1,000+ categories. Using UrbanPro.com, parents, and students can compare multiple Tutors and Institutes and choose the one that best suits their requirements. More than 7.5 lakh verified Tutors and Institutes are helping millions of students every day and growing their tutoring business on UrbanPro.com. Whether you are looking for a tutor to learn mathematics, a German language trainer to brush up your German language skills or an institute to upgrade your IT skills, we have got the best selection of Tutors and Training Institutes for you. Read more