Knuth–Morris–Pratt algorithm: Difference between revisions

Revision as of 07:36, 4 February 2005

Revision as of 16:10, 4 February 2005

Line 1:

The '''Knuth-Morris-Pratt [[string searching algorithm]]''' locatessearches afor patternoccurrences of charactersa within a"pattern" string. It<math>P</math> useswithin the fact that after finding the first mismatch between patterna andmain string we<math>S</math> alreadyby knowemploying the characterssimple comparedobservation beforethat towhen improvea themismatch efficiencyoccurs, ofwe thehave search.enough Weknowledge thereforesimply willby have to comparepossessing the pattern to itselfdetermine towhere determinethe hownext manymatch positionscould webegin, havethus tobypassing movere-examination toof thepreviously leftmatched characters.

The algorithm was invented by [[Donald Knuth|Knuth]] and [[Vaughan Pratt|Pratt]] and independently by [[J. H. Morris]] in [[1976]].

==An example of the algorithm==

To motivate the technical details, we consider a specific instance. Take:

main stringS: ABC ABCDAB ABCDABCDABDE

patternP: ABCDABD

In this article, we will be using [[Array#Indices into Arrays|zero-based arrays]] for our strings; thus the 'C' in <math>P</math> will be denoted <math>P[2]</math>. Let <math>m</math> be the start of the currently matched substring within <math>S</math>, <math>i</math> the position within <math>P</math>, and <math>j</math> the absolute position within <math>S</math>.

We begin by matching the first three characters one after another. Thus in the fourth step, the main position is 0, the current position is 3, and the pattern position is 3. But the current character is a space ' ' and the pattern character a 'D', so we have a mismatch. Rather than beginning again from main position 1, we note that no 'A' occurs between pattern positions 0 and 3 except at 0; hence, having checked all those characters previously, we know there is no chance of finding the beginning of a match if we check them again. Therefore we move on to the next character and set the main position to 4, and start checking again from pattern position 0.

We begin by matching the first three characters one after another. Thus in the fourth step, the<math>m main position is= 0, thei current position is= 3, andj the pattern position is= 3</math>. But the current character<math>S[3]</math> is a space ' ' and the<math>P[3] pattern character a= 'D'</math>, so we have a mismatch. Rather than beginning again from<math>m main position= 1</math>, we note that no 'A' occurs between pattern positions 0 and 3 in <math>P</math> except at 0; hence, having checked all those characters previously, we know there is no chance of finding the beginning of a match if we check them again. Therefore we move on to the next character, andsetting set<math>m the main position to= 4, andi start= checking0, againj from= pattern position 04</math>.

We quickly obtain a nearly complete match 'ABCDAB' when, at pattern position 6 and main position 10, we again have a discrepancy. However, just prior to the end of the current partial match we passed an 'AB', which could be the beginning of a new match, so we must take this into consideration. However, we already know that these characters match the two characters prior to the current position, so we need not check them again; we simply reset the main position to 8 and continue searching from pattern position 2 at the current position.

We quickly obtain a nearly complete match 'ABCDAB' when, at pattern<math>i position= 6, andj main position= 10,</math> we again have a discrepancy. However, just prior to the end of the current partial match we passed an 'AB', which could be the beginning of a new match, so we must take this into consideration. However,As we already know that these characters match the two characters prior to the current position, so we need not check them again; we simply reset the<math>m main= position8, toi 8= 2</math> and continue searching from pattern position 2 atmatching the current positioncharacter.

This search fails immediately, however, as the pattern still does not contain a ' ', so as in the first trial, we increment the main position to 11, reset the pattern position to 0, and begin searching anew. Once again we immediately hit upon a match 'ABCDAB' but the next character, 'C', does not match the final character 'D' of the pattern. Reasoning as before, we set the main position to start at the two-character string 'AB' leading up to the current position (hence main position 17), set the pattern position to 2, and continue matching from the current position. This time we are able to complete the match, and return the index 17 as its origin.

This search fails immediately, however, as the pattern still does not contain a ' ', so as in the first trial, we increment the<math>m main= position11</math> to 11,and reset the<math>i pattern= position0, toj 0= 11</math>, and begin searching anew. Once again we immediately hit upon a match 'ABCDAB' but the next character, 'C', does not match the final character 'D' of the pattern. Reasoning as before, we set the<math>m main= position17</math>, to start at the two-character string 'AB' leading up to the current position (hence main position 17), set the<math>i pattern position to= 2</math>, and continue matching from the current position. This time we are able to complete the match, and return the indexposition 17 as its origin.

==The searching algorithm==

Line 20 ⟶ 22:

The above example is completely instructive in this regard. Once the table is compiled the search is trivial and can be done without ever repeatedly matching any character of the main string. It proceeds as follows:

# Let <math>i = j = m = 0</math>. ''i'' will be the pattern position, and ''m''let the<math>P</math> mainhave <math>n</math> positioncharacters.

# Compare <math>P[i]</math> versus <math>S[j]</math>. At this point we have already matched <math>i</math> previous characters.

# Assume inductively that we have matched characters <math>0, \dots, i - 1</math> of the pattern against characters <math>m, \dots, m + i - 1</math> of the main string, and are currently considering the next one. If ''i'' is the length of the pattern we have found a match; we return ''m'' as its origin and terminate. Otherwise, we compare pattern character ''i'' with main character ''m + i''.

#* If they are equal, set <math>i = i + 1</math>, <math>j = j + 1</math>. If <math>i = n</math> then we have found a full match; terminate the algorithm and return <math>m</math> as the start of the match.

#* If they are unequal, consultlet <math>e = T[i - 1]</math> be an entry in the "partial match" table described below, at position ''<math>i - 1'', and obtain the index ''e'' stored there</math>. Set <math>m = m + ij - e</math>, <math>i = e</math>.

# Return to step 2.

Line 32 ⟶ 34:

The goal of the table is to allow the algorithm not to check any character of the main string more than once. The key observation about the nature of a linear search that allows this to happen is that in having checked some segment of the main string against an ''initial segment'' of the pattern, we know exactly at which places a new potential match which could continue to the current position could begin prior to the current position. In other words, we "pre-search" the pattern itself and compile a list of all possible fallback positions that bypass a maximum of hopeless characters while not sacrificing any potential matches in doing so.

We want to be able to look up, for each pattern position, the length of the longest possible initial match that ends in the current position other than the full match that probably just failed. Hence position ''n''<math>i</math> of the table is exactly the lengthposition of <math>P[i]</math> within the longest possible initial segment of the pattern<math>P</math> which is also a terminal segment of the substring ending at position ''n'' of the pattern<math>P[i]</math>. For those positions which ''could not'' be part of a subpattern, we set<math>T[i] the= entry to 0-1</math>, reflecting the fact that there are no fallbacks should the match fail there. To cover the possiblity of a mismatch in position 0, we also include an entry for index -1, which is also 0-1.

The table for 'ABCDABD' is as follows:

Line 58 ⟶ 60:

|-

!pos

|0 -1

|0 -1

|0 -1

|0 -1

|0 -1

|1 0

|2 1

|0 -1

|}

The first four entries are 0-1, since the only subpattern they appear in is the entire pattern. The number under the 'A' in position 4 is 10, because 'A' itself is a proper initial substring of the pattern ending at position 4, and has<math>P[4]</math> lengthoccurs 1at position 0 of it. The number under the following 'B' is 21 as 'AB' is a proper initial substring ending at position 5, withand length<math>P[5]</math> 2occurs at position 1 of it. As 'D' is not in any subpattern, it receives a 0-1.

==Compiling the table==

Line 74 ⟶ 76:

Although the algorithm makes the eventual search as efficient as may reasonably be expected (each character of the main string is matched exactly once), it may seem that the work has been hidden in the compilation of the table itself. This is not so, as this is ''also'' efficient.

We consider the example of 'ABCDABD' first. We will see that it follows much the same pattern as the main search, and is efficient for similar reasons. LetWe set <math>T(n)[-1] = -1</math>. denote Since <math>P[0]</math> is at the tableend entryof inonly positionthe ''n''complete initial segment, wherewe set <math>T([0)] = 0-1</math>. as Wewell. therefore begin byTo calculatingfind <math>T([1)]</math>, meaning that we must discover a proper terminal substring of 'AB' which is also an initial substring of the pattern. But the only proper terminal substring of 'AB' is 'B', which is not an initial substring of the pattern, so we set <math>T([1)] = 0-1</math>.

Continuing to 'C', we note that there is a shortcut to checking ''all'' terminal substrings: let us say that we discovered a terminal substring ending at 'C' with length 2; then its first character is an initial substring of an initial substring of the pattern, hence an initial substring itself...and it ends at 'B', which we already determined cannot occur. Therefore we need not even concern ourselves with substrings having length 2, and as in the previous case the sole one with length 1 fails, so <math>T([2)] = 0-1</math>.

Similarly for 'D', giving <math>T([3)] = 0-1</math>, so we pass to the subsequent 'A'. The same logic shows that the longest substring we need consider has length 1, and in this case 'A' ''does'' work; thus <math>T([4)] = 10</math>. Considering now the following 'B', we exercise the following logic: if we were to find a subpattern beginning before the previous 'A' yet continuing to the current 'B', then in particular it would itself have a proper initial segment ending at 'A' yet beginning before 'A', which contradicts the fact that we already found that 'A' itself is the earliest occurrence of a proper subpattern ending at it. Therefore we need not look before that 'A' to find a subpattern for 'B'. In fact, checking it, we find that it continues to 'B' and that 'B' is the second entry of the substring of which 'A' is the first. Therefore the entry for 'B' in 'T' is one more than the entry for 'A', namely <math>T([5)] = 21</math>.

Finally, the pattern does ''not'' continue from 'B' to 'D'. Similar reasoning as above shows that if we were to find a subpattern longer than 1 at 'D' then it must comprise a subpattern ending at 'B'; since the current one does not work, this one would have to be shorter. But the current one is an initial segment of the pattern ending at the second position, so this potential new subpattern would be as well, and we already decided there were none of those. Since 'D' itself is not a subpattern, <math>T([6)] = 0-1</math>.

==The table algorithm==

Line 86 ⟶ 88:

The example above illustrates the general technique for assembling the table with a minimum of fuss. The principle is that of the overall search: most of the work was already done in getting to the current position, so very little needs to be done in leaving it. Here follows the algorithm.

# Set <math>T[-1] = T[0] = -1</math>. This takes care of special conditions; we cannot compute <math>T[-1]</math> by searching for substrings, and our algorithm for <math>T[0]</math> would give the incorrect answer 0 as this is the unique case in which a single character is ''not'' a proper initial substring. Again, let <math>P</math> have <math>n</math> characters.

# Set <math>T(-1)i = 01</math>.

# Assume inductively that we have calculated <math>T(-1), \dots, T(n - 1)</math> and are currently calculating <math>T(n)</math>. Furthermore, we have chosen each of the previous values such that the longest proper initial segment of the pattern which is also a substring terminating in character ''k'' of the pattern has length <math>T(k)</math> (and the empty string has length 0).

# If <math>i = n</math> then we are done; terminate the algorithm. Otherwise, set <math>j = T[i - 1]</math> and compare <math>P[i]</math> with <math>P[j + 1]</math>.

# Set <math>i = n - 1</math>.

#* If they are equal, set <math>T[i] = j + 1</math>, <math>i = i + 1</math>.

# Set <math>i = T(i)</math>. At this point, we know that the longest initial segment of the pattern that could possibly terminate at character ''n'' must start no earlier than ''n - i''. In particular, character ''n'' will be character ''i'' in the continued pattern, which would be character ''i'' of the entire pattern.

#* If characternot, ''n''and equalsif character<math>j ''i''= then the subpattern terminating at ''n - 1'' continues to ''n''0</math>, and we set <math>T(n)[i] = i + -1</math>, n<math>i = ni + 1</math>, and return to step 2.

# Return to step 3.

#* If not, then the subpattern does ''not'' continue, and we must find the next candidate. If <math>i > 0</math> then as in the example above at the final 'D', we may begin searching for strings of length ''T(i)'' ending at character ''i - 1''. Return to step 4 if so. If <math>i = 0</math>, then there is nothing left to search, so set <math>T(n) = 0, n = n + 1</math>, and return to step 2.

==Notes on the Algorithm==

Line 105 ⟶ 107:

[[Category:Algorithms on strings]]

[[es:Algoritmo Knuth-Morris-Pratt]]