The function used to determine the next state after the failed match is sometimes called failure function. When k-th pattern character is matched, transition to state k + 1 occurs (green arrows).When k-th pattern character isn’t matched, the prefix function determines the next state (red arrows). State 0 is an initial state, state 6 is an acceptance state (which corresponds to the discovery of the sought string). Knuth-Moriss-Pratt algorithm can be represented as a finite state machine: If q symbols were matched at offset k and (q + 1)-th symbol wasn’t matched, then the next possible valid offset is k + ( q - f(q)), where f is a prefix function. On the other hand, we cannot skip offset s + 2, because first 3 pattern characters match with 3 last checked characters from previous offset. For example, offset s + 1 is certainly invalid, because we already know that character at offset s + 1 matches with second pattern character and it won’t match with the first pattern character. Knowing that q characters were matched, we can skip offsets which are certainly invalid. The following picture illustrates how prefix function is used to accelerate string matching:Īs shown in the picture, q = 5 characters from the pattern were matched at offset s = 4, but the 6-th character wasn’t matched. Prefix function f(q) for the pattern M defines the longest proper prefix of string M which matches its suffix. This information can be used to skip unnecessary comparisons. Prefix function stores the information about how sought pattern matches itself after the shift. To use the information about previous matches, KMP algorithm uses a prefix function.
Knuth-Morris-Pratt algorithm is one of the most popular effective string matching algorithms. Knuth-Morris-Pratt algorithm (KMP Algorithm) All of them perform some kind of pre-processing of the sought string before the search phase. There are several effective string matching algorithms that use the information about previous matches. For example, if we are searching for the substring M = “ aaab” and we have found a match at offset k = 0, there certainly cannot be any match at offsets 1, 2, 3 because S = ‘b’. The major problem with the described algorithm is that it discards the information that was acquired for previous values of k. The running time of simple string matching is O( len(M) * ( len(S) - len(M) - 1)). This algorithm is illustrated in the following picture. S with corresponding characters from the sought string ( M.
The simplest string matching algorithm works as follows:įor each possible offset k within a string S ( k is a number in range from 0 to len(S) - len(M)) compare characters S.
Let’s assume, we have a string S and a sought string (or pattern) M. Choosing String Matching Algorithm Simple String Matchingįirst, let’s consider the simplest possible algorithm for string matching. The next section of this article is dedicated to choosing an appropriate algorithm for our library. There are several algorithms for string matching. Also, information about positions of found terms in input text may be useful.īefore evaluating search query, we must find all occurrences of search terms in input text. The purpose of our library is to determine if given text matches given search query. For example, this approach is used in the web search engines.
0 kommentar(er)
