String Matching

6.854 Advanced Algorithms Lecturer: Erik Demaine, David Karger String Matching 1.1 Problem formulation We consider a basic problem in string matching, and two different approaches to it. The first will be algorithmic, while the second will emphasize data structures. The basic problem we consider is: given a string 7 and a pattern P, determine if P appears as a substring in 7, ie.: Input: A text T and a pattern P. Output: Is Pa substring of T? If so, where? 1.1.1 Motivation and Background The string searching problem arises in many fields. An example is searching for common gené sequences in a long DNA sequence. A more familiar example are the type-alhead-find features of modern Internet browsers and text editors. 1.1.2 Obvious Algorithm The obvious algorithun to solve this problem compare each P with T at each position, shifting over Pat each iteration. The running time of this algorithm is O(TP). The algorithm needs to compare all [P] characters of P at each iteration, and there are at worst [7] iterations (actually, T-P). 1.1.3 Rabin-Karp String Matching The Rabin-Karp string matching algorithm is a randomized algorithm that can solve the string matching problem in O([T]+[P). The main technique used here is fingerprinting, which we will discuss in detail a bit later. The motivation is as follows: if we can find a way of compare the pattern P with a P segment of T in O(1) time, we can search the text in O(T) time. The idea of fingerprinting is as follows: comparing two strings x, y of length |P| takes P) comparisons. Suppose we had a function with the following property: and checking f(x)=f(p) could be done in constant time. This is not possible, so instead we settle for the following Definition 1 fingerprint of a string (f(z)): The fingerprint of a string z is a mapping from the string to a set of integers sach that ifry then f(x)=(y) and if f(z)=(y) then with high probability. Assume (without loss of generality) that the input strings are over (0.1). Treat a string r as the hinary representation of a number. Dedine f(z) = (number represented by z) mod p, where p is a random prime. To do the comparisons, we need to compute (P) and (T:+P-1]), for every 1≤ i ≤ 7-P. Can we compute this in O([T]+[P]) time? Yes. The trick is to compute f(Ti+1:i+[P]) from (T+P-1]) in constant time as follows: compute Ti+1:+P-1] from Ti:+P-1] by "dropping" 7[i]: subtract from the current fingerprint 27. Then compute Thi+1:i+P] from Ti+11+P-1] by "adding the last letter and shifting": multiply the current fingerprint by 2 and add Ti + P Analysis A false match when f(x) = f(y) buty. For our fingerprint, this occurs when f(x)=f(y) (mod p) which is exactly when f(x)f(y) is a multiple of p. (Slight notational difficulty here: P with a capital letter is the input text pattern we want to find in the text and is a string. p with a lower case is the random prime number that we pick.) What is the probability that a false match occurs? This is exactly the following probability: Pr (n is a multiple of p) where=f(z)f(y). We upper bound this probability as follows: how many prime factors does n have? Clearly, this is at most logn. As long as the prime we choose is not one of these, we will be fine. Suppose we choose p as a random prime from [2.Q). By the Prime Number Theorem, there Although Rabin-Karp is "fast," we may want to preserve the work we have done if we have multiple queries. We want to design a data structure that can answer multiple queries efficiently. Let n be the length of the text and m be the length of the pattern. We want to preprocess the text in O(n) time and produce a data structure that takes O(n) space and can answer queries in O(m) time. Trees and Tries Here we give a description of various data structures that we might try to use: 1. Tree Dictionary Keep a set of k strings in a binary tree dictionary. Check if the pattern is one of the strings in tree. This would take O(m log k) time to do a search. The problem here is that we would have to store all n(n+1)/2 substrings in the dictionary. This is clearly too large a value for k. [Diagram: A binary tree with four nodes labeled a, b, c, and d. Edges connect the nodes.] Figure 1.2: An example of a trie on {a,b,c,d}. 2. Trie A trie is another type of search tree. The difference between a trie and a regular search tree is that the outgoing edges of a node are the ones that correspond to characters. A walk down the path of a trie corresponds to iterating through the characters of a string. See Figure 1.2 for an example. The nodes store the index information for a search. At each node, the edges are implemented by an array of size Σ, where Σ is the alphabet and is thus directly indexable. Therefore, tries can search for a pattern in O(m) time! The problem with a trie is that it also requires the storage of all possible substrings the text and would take O(n²) time to build the trie. 3. Suffix Tree Since we realize that storing all possible substrings is highly redundant, instead build a trie of only then suffixes of the text. Any substring of the text is a prefix to some suffix in the text; therefore, it reaches some internal node of the trie. We label each leaf node