Lecture
We often encounter a specific kind of search, so-called string search (search within a string). Let there be some text T and a word (or pattern) W. It is necessary to find the first occurrence of this word in the given text. This action is typical for any text-processing systems. (The elements of the arrays T and W are characters of some finite alphabet – for example, {0, 1}, or {a, …, z}, or {a, …, z} in Cyrillic.)
The most typical application of such a problem is document retrieval: given a collection of documents consisting of a sequence of bibliographic references, each reference accompanied by a "descriptor" indicating the topic of the corresponding reference. One needs to find certain keywords occurring among the descriptors. There could, for example, be a query for "Programming" and "Java." Such a query can be interpreted as follows: are there articles possessing the descriptors "Programming" and "Java."
String search is formally defined as follows. Let an array T of N elements and an array W of M elements be given, where 0<M≤N. String search finds the first occurrence of W in T, and the result is taken to be the index i indicating the first match with the pattern (word) counted from the start of the string (from the start of the array T).
Example. It is required to find all occurrences of the pattern W = abaa in the text T=abcabaabcabca.
The pattern occurs in the text only once, with shift S=3, index i=4.
Idea of the algorithm:
1. I=1,
2. compare the I-th character of array T with the first character of array W,
3. match → compare the second characters and so on,
4. mismatch → I:=I+1 and go to step 2,
Termination condition of the algorithm:
1. M comparisons in a row are successful,
2. I+M>N, meaning the word was not found.
Complexity of the algorithm:
Worst case. Let the array T→{AAA….AAAB}, of length │T│=N, and the pattern W→{A….AB}, of length │W│=M. Obviously, to detect the match at the end of the string will require on the order of N*M comparisons, i.e. O(N*M).
Drawbacks of the algorithm:
1. high complexity — O(N*M), in the worst case – Θ((N-M+1)*M);
2. after a mismatch, scanning always starts again from the first character of the pattern and can therefore include characters of T that have already been examined before (if the string is read from secondary memory, such backtracking takes a lot of time);
3. information about the text T obtained while checking a given shift S is not used in any way when checking subsequent shifts.
The KMP search algorithm actually requires only on the order of N comparisons even in the worst case.
Example.
(Characters that were compared are underlined.)
After a partial match of the initial part of the pattern W with the corresponding characters of the string T, we effectively know the part of the string traversed and can "compute" some information (based on the pattern W itself), with the help of which we can then quickly advance through the text.
The idea of KMP search – on every mismatch of two characters of the text and the pattern, the pattern is shifted by the entire distance traversed, since smaller shifts cannot lead to a full match.
Features of KMP search:
1. requires on the order of (N+M) character comparisons to obtain the result;
2. the KMP search scheme yields a genuine gain only when the failure was preceded by a certain number of matches. Only in this case is the pattern shifted by more than one position. Unfortunately, matches occur much less often than mismatches. Therefore, the gain from KMP search is quite insignificant for most kinds of text.
In practice, the BM search algorithm is most effective when the pattern W is long and the alphabet's cardinality is fairly large.
The idea of BM search – comparison of characters begins from the end of the pattern, not from the beginning, that is, individual characters are compared from right to left. Then, using some heuristic procedure, the size of the rightward shift s is computed. And comparison of characters begins again from the end of the pattern.
This method not only improves handling of the worst case, but also gives a gain in intermediate situations.
Almost always, except for specially constructed examples, BM search requires significantly fewer than N comparisons. In the most favorable circumstances, when the last character of the pattern always lands on a mismatching character of the text, the number of comparisons equals (N / M); in the worst case – O((N-M+1)*M+ p), where p – is the cardinality of the alphabet.
Let the alphabet D={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, that is, each character in the alphabet is a base-d digit, where d=│D│.
Example. Let the pattern have the form W = 3 1 4 1 5
We compute the values of the numbers from a window of length |W|=5 modulo q, where q — is a prime number.
23590(mod 13)=8, 35902(mod 13)=9, 59023(mod 13)=9, …
k1=314157(mod 13) – an occurrence of the pattern,
k2=673997(mod 13) – a spurious hit.
From the equality ki= kj (mod q) it does not follow that ki= kj (for example, 31415=67399(mod 13), but this does not mean that 31415=67399). If ki= kj (mod q), one still has to check whether the strings W[1…m] and T[s+1…s+m] actually match.
If the prime number q is sufficiently large, the additional cost of analyzing spurious hits will be small.
In the worst case the running time of the RK algorithm is Θ((N-M+1)*M), while on average it runs fairly quickly – in time O(N+M).
Example: How many spurious hits k will the RK algorithm make if
q= 11, 13, 17. Let W={2 6}
26 mod 11=4 → k =3 spurious hits,
26 mod 13=0 → k =1 spurious hit,
26 mod 17=9 → k =0 spurious hits.
Clearly, the number of spurious hits k is a function of the size of the prime number q (if the pattern-processing function is mod q) and, in general, of the form of the function used to process the pattern W and the text T.
[[b9486]]
Comments