STRINGS AND PATTERN MATCHING - Purdue University

1 1 STRINGS and PATTERN MatchingSTRINGS ANDPATTERNMATCHING brute force , Rabin-Karp, Knuth-Morris-PrattWhat s up?I m looking for some s quite a trick consideringthat you have no yeah? Have you seen your writing?It looks like an EKG!2 STRINGS and PATTERN MatchingString Searching The previous slide is not a great example of what ismeant by String Searching. Nor is it meant toridicule people without The object ofstring searching is to find the locationof a specific text PATTERN within a larger body of text( , a sentence, a paragraph, a book, etc.). As with most algorithms, the main considerationsfor string searching are speed and efficiency. There are a number of string searching algorithms inexistence today, but the two we shall review areBrute force and PATTERN MatchingBrute force TheBrute force algorithm compares the PATTERN tothe text, one character at a time, until unmatchingcharacters are found:- Compared characters are Correct matches are in boldface type.

2 The algorithm can be designed to stop on either thefirst occurrence of the PATTERN , or upon reaching theend of the ROADS DIVERGED IN A YELLOW WOODROADSTWO ROADS DIVERGED IN A YELLOW WOODROADSTWO ROADS DIVERGED IN A YELLOW WOODROADSTWO ROADS DIVERGED IN A YELLOW WOODROADSTWOROADS DIVERGED IN A YELLOW WOODROADS4 STRINGS and PATTERN MatchingBrute force Pseudo-Code Here s the pseudo-codedoif (text letter == PATTERN letter)compare next letter of PATTERN to nextletter of textelsemove PATTERN down text by one letterwhile (entire PATTERN found or end of text)tetththeheehthtehtheththehehthtthet etththeheehthtehtheththehehthtthetetthth eheehthtehtheththehehthtthetetththeheeht htehtheththehehthtthetetththeheehthtehth eththehehthtthetetththeheehthtehtheththe hehthtthe5 STRINGS and PATTERN MatchingBrute force -Complexity Given a PATTERN M characters in length, and a text Ncharacters in Worst case: compares PATTERN to each substring oftext of length M.

3 For example, M= )AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH5 comparisons made2)AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH5 comparisons made3)AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH5 comparisons made4)AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH5 comparisons made5)AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH5 comparisons ) AAAAAAAAAAAAAAAAAAAAAAAAAAAH5 comparisons madeAAAAH Total number of comparisons: M (N-M+1) Worst case time complexity: (MN)6 STRINGS and PATTERN MatchingBrute force -Complexity(cont.) Given a PATTERN M characters in length, and a text Ncharacters in Best case if PATTERN found: Finds PATTERN in first Mpositions of text. For example, M= )AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAA5 comparisons made Total number of comparisons: M Best case time complexity: (M)7 STRINGS and PATTERN MatchingBrute force -Complexity(cont.) Given a PATTERN M characters in length, and a text Ncharacters in Best case if PATTERN not found: Always mismatchon first character.

4 For example, M= )AAAAAAAAAAAAAAAAAAAAAAAAAAAHOOOOH1 comparison made2) AAAAAAAAAAAAAAAAAAAAAAAAAAAHOOOOH1 comparison made3) AAAAAAAAAAAAAAAAAAAAAAAAAAAHOOOOH1 comparison made4) AAAAAAAAAAAAAAAAAAAAAAAAAAAHOOOOH1 comparison made5) AAAAAAAAAAAAAAAAAAAAAAAAAAAHOOOOH1 comparison ) AAAAAAAAAAAAAAAAAAAAAAAAAAAH1 comparison madeOOOOH Total number of comparisons: N Best case time complexity: (N)8 STRINGS and PATTERN MatchingRabin-Karp The Rabin-Karp string searching algorithm uses ahash function to speed up the & Karp sFresh from SyriaHeavenlyHomemade Hashish9 STRINGS and PATTERN MatchingRabin-Karp The Rabin-Karp string searching algorithmcalculates ahash valuefor the PATTERN , and for eachM-character subsequence of text to be compared. If the hash values are unequal, the algorithm willcalculate the hash value for next M-charactersequence. If the hash values are equal, the algorithm will do aBrute force comparisonbetween the PATTERN and theM-character sequence.

5 In this way, there is only one comparison per textsubsequence, and brute force is only needed whenhash values match. Perhaps a figure will clarify some and PATTERN MatchingRabin-Karp ExampleHash value of AAAAA is 37 Hash value of AAAAH is 1001)AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH37 1001 comparison made2) AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH37 1001 comparison made3) AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH37 1001 comparison made4) AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH37 1001 comparison ) AAAAAAAAAAAAAAAAAAAAAAAAAAAHAAAAH6 comparisons made 100=10011 STRINGS and PATTERN MatchingRabin-Karp Pseudo-Codepattern is M characters longhash_p=hash value of patternhash_t=hash value of first M letters inbody of textdoif (hash_p ==hash_t) brute force comparison of patternand selected section of texthash_t = hash value of next section of text, one character overwhile (end of textor brute force comparison == true)12 STRINGS and PATTERN MatchingRabin-Karp Common Rabin-Karp questions.

6 What is the hash function used to calculatevalues for character sequences? Isn t it time consuming to hashevery one of the M-charactersequences in the text body? Is this going to be on the final? To answer some of these questions, we ll have to and PATTERN MatchingRabin-Karp Math Consider an M-character sequence as an M-digitnumber inbaseb, wherebis the number of letters inthe alphabet. The text subsequence t[i .. i+M-1] ismapped to the numberx(i) =t[i] bM-1 +t[i+1] bM-2 +..+t[i+M-1] Furthermore, given x(i) we can compute x(i+1) forthe next subsequence t[i+1 .. i+M] in constant time,as follows:x(i+1) =t[i+1] bM-1 +t[i+2] bM-2 +..+t[i+M]x(i+1) =x(i) bShift left one digit-t[i] bM Subtract leftmost digit+t[i+M] Add new rightmost digit In this way, we never explicitly compute a newvalue. We simply adjust the existing value as wemove over one and PATTERN MatchingRabin-Karp Mods If M is large, then the resulting value (~bM) will beenormous.

7 For this reason, we hash the value bytaking itmod a prime numberq. Themod function (% in Java) is particularly usefulin this case due to several of its inherent properties:- [(x mod q) + (y mod q)] mod q = (x+y) mod q- (x mod q) mod q = x mod q For these reasons:h(i) = ((t[i] bM-1 modq) +(t[i+1] bM-2 modq) + .. +(t[i+M-1] modq)) modqh(i+1) =(h(i) b modqShift left one digit-t[i] bM modqSubtract leftmost digit+t[i+M] modq )Add new rightmost digitmodq15 STRINGS and PATTERN MatchingRabin-Karp Pseudo-Codepattern is M characters longhash_p=hash value of patternhash_t=hash value of first M letters in body of textdoif (hash_p==hash_t) brute force comparison of patternand selected section of texthash_t = hash value of next section of text, one character overwhile (end of textor brute force comparison ==true)16 STRINGS and PATTERN MatchingRabin-Karp Complexity If a sufficiently large prime number is used for thehash function, the hashed values of two differentpatterns will usually be distinct.

8 If this is the case, searching takes O(N) time, whereN is the number of characters in the larger body oftext. It is always possible to construct a scenario with aworst case complexity ofO(MN). This, however, islikely to happen only if the prime number used forhashing is and PATTERN MatchingThe Knuth-Morris-PrattAlgorithm TheKnuth-Morris-Pratt (KMP) string searchingalgorithm differs from the brute - force algorithm bykeeping track of information gained from previouscomparisons. Afailure function(f) is computed that indicates howmuch of the last comparison can be reused if it fais. Specifically, f is defined to be the longest prefix ofthe PATTERN P[0,..,j] that is also a suffix of P[1,..,j]- Note:nota suffix of P[0,..,j] Example:- value of the KMP failure function: This shows how much of the beginning of the stringmatches up to the portion immediately preceding afailed if the comparison fails at (4), we know the a,b inpositions 2,3 is identical to positions 0,1j012345P[j]ababacf(j)00123018 STRINGS and PATTERN MatchingThe KMP Algorithm (contd.)

9 Time Complexity Analysis definek =i -j In every iteration through the while loop, one ofthree things 1) ifT[i] =P[j], theni increases by 1, as doesjk remains the 2) ifT[i] !=P[j] andj > 0, theni does not changeandkincreases by at least 1, sincekchangesfromi -j toi -f(j-1)-3)ifT[i]!=P[j] andj= 0, theniincreases by 1 andk increases by 1 sincej remains the same. Thus, each time through the loop, eitheri orkincreases by at least 1, so the greatest possiblenumber of loops is 2n This of course assumes thatf has already beencomputed. However,fis computed in much the same manner asKMPM atch so the time complexity argument isanalogous. KMPF ailureFunction isO(m) Total Time Complexity:O(n +m)19 STRINGS and PATTERN MatchingThe KMP Algorithm (contd.) the KMP string MATCHING algorithm: Pseudo-CodeAlgorithmKMPM atch(T,P)Input:StringsT (text) withn characters andP( PATTERN ) withm :Starting index of the first substring ofTmatchingP, or an indication thatP is not asubstring KMPF ailureFunction(P){build failure function}i 0j 0whilei <ndoifP[j] =T[i] thenifj =m - 1thenreturni -m - 1{a match}i i + 1j j + 1else ifj > 0then{no match, but we have advanced}j f(j-1){j indexes just after MATCHING prefix in P}elsei i + 1return There is no substring ofT matchingP 20 STRINGS and PATTERN MatchingThe KMP Algorithm (contd.

10 The KMP failure function: Pseudo-CodeAlgorithmKMPF ailureFunction(P);Input:StringP ( PATTERN ) withm charactersOuput:The faliure functionf forP, which mapsj tothe length of the longest prefix ofP that is a suffixofP[1,..,j]i 1j 0whilei m-1doifP[j] = T[j] then{we have matchedj + 1 characters}f(i) j + 1i i + 1j j + 1else ifj > 0then{j indexes just after a prefix ofP that matches}j f(j-1)else{there is no match}f(i) 0i i + 121 STRINGS and PATTERN MatchingThe KMP Algorithm (contd.) A graphical representation of the KMP stringsearching algorithmbaaabcaaaaaaaabbbbccccaa1234567 89 10 11 121314 15 16 17 18baaabcbaaabcbaaabcbaaabc19no comparisonneeded here22 STRINGS and PATTERN MatchingRegular Expressions notation for describing a set of STRINGS , possibly ofinfinite size denotes the empty string ab + c denotes the set {ab, c} a* denotes the set { ,a, aa, aaa, ..} Examples-(a+b)*all the STRINGS from the alphabet {a,b}-b*(ab*a)*b* STRINGS with an even number of a s-(a+b)*sun(a+b)* STRINGS containing the PATTERN sun -(a+b)(a+b)(a+b)a4-letter STRINGS ending in a23 STRINGS and PATTERN MatchingFinite State Automaton machine for processing strings01bbaa321aba064bbaa2351 a,b24 STRINGS and PATTERN MatchingComposition of FSA s a 25 STRINGS and PATTERN MatchingTries Atrie is a tree-based date structure for storingstrings in order to make PATTERN MATCHING faster.