PKnuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm
Kranthi Kumar Mandumula

December 18, 2011

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

outline

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

Definition History Components of KMP Algorithm Example Run-Time Analysis Advantages and Disadvantages References

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Definition:

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

Best known for linear time for exact matching. Compares from left to right. Shifts more than one position. Preprocessing approach of Pattern to avoid trivial comparisions. Avoids recomputing matches.

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

History:

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

This algorithm was conceived by Donald Knuth and Vaughan Pratt and independently by James H.Morris in 1977.

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

History:

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

Knuth, Morris and Pratt discovered first linear time string-matching algorithm by analysis of the naive algorithm. It keeps the information that naive approach wasted gathered during the scan of the text. By avoiding this waste of information, it achieves a running time of O(m + n). The implementation of Knuth-Morris-Pratt algorithm is efficient because it minimizes the total number of comparisons of the pattern against the input string.

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Components of KMP:

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

The prefix-function : It preprocesses the pattern to find matches of prefixes of the pattern with the pattern itself. It is defined as the size of the largest prefix of P[0..j − 1] that is also a suffix of P[1..j]. It also indicates how much of the last comparison can be reused if it fails. It enables avoiding backtracking on the string ‘S’.

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

m ← length[p] a[1] ← 0 k ←0 for q ← 2 to m do while k > 0 and p[k + 1] k ← a[k ] end while if p[k + 1] = p[q] then k ←k +1 end if a[q] ← k end for return Here a =

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

p[q] do

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Computation of Prefix-function with example: Knuth-Morris-Pratt
Algorithm Kranthi Kumar Mandumula

Let us consider an example of how to compute for the pattern ‘p’. Pattern a b a b a c a

I n i t i a l l y : m = length [ p]= 7 [1]= 0 k=0 where m, [1], and k are the length of the pattern, prefix function and initial potential value respectively.

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm

Step 1 : q = 2 , k = 0 [2]= 0 q p 1 a 0 2 b 0 3 a 4 b 5 a 6 c 7 a

Kranthi Kumar Mandumula

Step 2 : q = 3 , k = 0 [3]= 1 q p 1 a 0 2 b 0 3 a 1 4 b 5 a 6 c 7 a

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm

Step 3 : q = 4 , k = 1 [4]= 2 q p 1 a 0 2 b 0 3 a 1 4 b 2 5 a 6 c 7 a

Kranthi Kumar Mandumula

Step 4 : q = 5 , k = 2 [5]= 3 q p 1 a 0 2 b 0 3 a 1 4 b 2 5 a 3 6 c 7 a

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm

Step 5 : q = 6 , k = 3 [6]= 1 q p 1 a 0 2 b 0 3 a 1 4 b 2 5 a 3 6 c 1 7 a

Kranthi Kumar Mandumula

Step 6 : q = 7 , k = 1 [7]= 1 q p 1 a 0 2 b 0 3 a 1 4 b 2 5 a 3 6 c 1 7 a 1

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

A f t e r i t e r a t i n g 6 times , t h e p r e f i x f u n c t i o n computations i s complete : q p 1 a 0 2 b 0 3 A 1 4 b 2 5 a 3 6 c 1 7 a 1

The running time of the prefix function is O(m).

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Algorithm

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

Step 1 : I n i t i a l i z e t h e i n p u t v a r i a b l e s : n = Length o f t h e Text . m = Length o f t h e P a t t e r n . = Prefix −f u n c t i o n of pattern ( p ) . q = Number o f c h a r a c t e r s matched . Step 2 : D e f i n e t h e v a r i a b l e : q=0 , t h e b e g i n n i n g o f t h e match . Step 3 : Compare t h e f i r s t c h a r a c t e r o f t h e p a t t e r n w i t h f i r s t c h a r a c t e r o f text . I f match i s n o t found , s u b s t i t u t e t h e v a l u e o f [ q ] to q . I f match i s found , then i n c r e m e n t t h e v a l u e o f q by 1 . Step 4 : Check whether a l l t h e p a t t e r n elements are matched w i t h t h e t e x t elements . I f not , r e p e a t t h e search process . I f yes , p r i n t t h e number o f s h i f t s taken by t h e p a t t e r n . Step 5 : l o o k f o r t h e n e x t match .

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

n ← length[S] m ← length[p] a ← Compute Prefix function q←0 for i ← 1 to n do while q > 0 and p[q + 1] S[i] do q ← a[q] if p[q + 1] = S[i] then q ←q+1 end if if q == m then q ← a[q] end if end while end for Here a =
Kranthi Kumar Mandumula Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

Example of KMP algorithm:

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

Now let us consider an example so that the algorithm can be clearly understood. String b a c b a b a b a b a c a a b

Pattern a b a b a c a Let us execute the KMP algorithm to find whether ‘p’ occurs in ‘S’.

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

I n i t i a l l y : n = size of S = 15; m = s i z e o f p=7 Step 1 : i = 1 , q = 0 comparing p [ 1 ] w i t h S [ 1 ]

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

String b a c b a b a b a b a c a a b

Pattern a b a b a c a
P[1] does not match with S[1]. ‘p’ will be shifted one position to the right. Step 2 : i = 2 , q = 0 comparing p [ 1 ] w i t h S [ 2 ]

String b a c b a b a b a b a c a a b

Pattern a b a b a c a

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm Step 3 : i = 3 , q = 1 comparing p [ 2 ] w i t h S [ 3 ] p [ 2 ] does n o t match w i t h S [ 3 ] Kranthi Kumar Mandumula

String b a c b a b a b a b a c a a b

Pattern a b a b a c a
B a c k t r a c k i n g on p , comparing p [ 1 ] and S [ 3 ] Step 4 : i = 4 , q = 0 comparing p [ 1 ] w i t h S [ 4 ] p [ 1 ] does n o t match w i t h S [ 4 ]

String b a c b a b a b a b a c a a b

Pattern a b a b a c a

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm Step 5 : i = 5 , q = 0 comparing p [ 1 ] w i t h S [ 5 ] Kranthi Kumar Mandumula

String b a c b a b a b a b a c a a b

Pattern a b a b a c a
Step 6 : i = 6 , q = 1 comparing p [ 2 ] w i t h S [ 6 ]

p [ 2 ] matches w i t h S [ 6 ]

String b a c b a b a b a b a c a a b

Pattern a b a b a c a

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm Step 7 : i = 7 , q = 2 comparing p [ 3 ] w i t h S [ 7 ] p [ 3 ] matches w i t h S [ 7 ] Kranthi Kumar Mandumula

String b a c b a b a b a b a c a a b

Pattern a b a b a c a
Step 8 : i = 8 , q = 3 comparing p [ 4 ] w i t h S [ 8 ]

p [ 4 ] matches w i t h S [ 8 ]

String b a c b a b a b a b a c a a b

Pattern a b a b a c a

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Step 9 : i = 9 , q = 4 comparing p [ 5 ] w i t h S [ 9 ]

Knuth-Morris-Pratt Algorithm p [ 5 ] matches w i t h S [ 9 ] Kranthi Kumar Mandumula

String b a c b a b a b a b a c a a b

Pattern a b a b a c a
Step 1 0 : i = 10 , q = 5 comparing p [ 6 ] w i t h S [ 1 0 ]

p [ 6 ] doesn ’ t matches w i t h S [ 1 0 ]

String b a c b a b a b a b a c a a b

Pattern a b a b a c a
B a c k t r a c k i n g on p , comparing p [ 4 ] w i t h S [ 1 0 ] because a f t e r mismatch q = [5] = 3

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm Step 1 1 : i = 11 , q = 4 comparing p [ 5 ] w i t h S [ 1 1 ] Kranthi Kumar Mandumula

String b a c b a b a b a b a c a a b

Pattern a b a b a c a
Step 1 2 : i = 12 , q = 5 comparing p [ 6 ] w i t h S [ 1 2 ]

p [ 6 ] matches w i t h S [ 1 2 ]

String b a c b a b a b a b a c a a b

Pattern a b a b a c a

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula Step 1 3 : i = 13 , q = 6 comparing p [ 7 ] w i t h S [ 1 3 ]

p [ 7 ] matches w i t h S [ 1 3 ]

String b a c b a b a b a b a c a a b

Pattern a b a b a c a

pattern ‘p’ has been found to completely occur in string ‘S’. The total number of shifts that took place for the match to be found are: i − m = 13-7 = 6 shifts.

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Run-Time analysis:

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

O(m) - It is to compute the prefix function values. O(n) - It is to compare the pattern to the text. Total of O(n + m) run time.

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Advantages and Disadvantages:

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

Advantages: The running time of the KMP algorithm is optimal (O(m + n)), which is very fast. The algorithm never needs to move backwards in the input text T. It makes the algorithm good for processing very large files.

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Advantages and Disadvantages:

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

Disadvantages: Doesn’t work so well as the size of the alphabets increases. By which more chances of mismatch occurs.

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm

Knuth-Morris-Pratt Algorithm Kranthi Kumar Mandumula

Graham A.Stephen, “String Searching Algorithms”, year = 1994. Donald Knuth, James H. Morris, Jr, Vaughan Pratt, “Fast pattern matching in strings”, year = 1977. Thomas H.Cormen; Charles E.Leiserson., Introduction to algorithms second edition , “The Knuth-Morris-Pratt Algorithm”, year = 2001.

Kranthi Kumar Mandumula

Knuth-Morris-Pratt Algorithm