Parametrized Matching Algorithms
Discover the world of parametrized matching algorithms including Less Than Matching, Not Exact Matching, and Order-Preserving Matching. Explore the concepts and applications explained in detail.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Less Than Matching Orgad Keller Modified by Ariel Rosenfeld
Not Exact-Matching Parametrized matching int i=1; int j=2; Int x= i * j; int firstVar=1; int secondVar=2; Int result= firstVar= * secondVar; Algorithms 2 2
Not Exact-Matching Order-Preserving matching Algorithms 2 3
Less Than Matching Match Mis-match .. . .. .. . .. .. . . . . .. .. . .. . .. .. . .. .. . . . . .. .. . .. . .. .. . .. .. . . . . .. .. . . . . . .. . . .. . .. . . . . . .. . . . . . . . . . . . .. . . .. . .. . . . . . .. . . . . . . . . . . . . . . . .. . . .. . . . . . .. . . . . . .. . . .. . . . . . .. . . . . . .. . . . . . . .. . . . . . . . . . .. .. . . . . ... . . . . . .. . . . .. . . . . .. .. . . . . ... . . . . . .. . . . . . .. .. . . . . .. .. . . . . . . .. . .. . . . . . . .. . . . .. . .. .. . .. . . . . . . .. . . . . . . .. .. . . . . . . . . . . .. .. . . . . . . . . .. . . . . . . . . . . . . . . . .. . . .. . . . . .. . . . . .. . . . . . .. . . . . .. . . . . . . .. . . . . . . . . .. . . . . . . . . . . . . . . .. . .. . .. . . . . . . . . . .. . . . . . . . . . ... .. . . . . .. . . . . . . . . . . . . . . . ... . . . . . . .. .. . . . . . . . . . . . . . ... . . . . . .. . .. . . . . . . . . . .. . ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . .. . . . . . . . . . . .. . . . .. ... . . .. . .. .. . . . . .. . . . . . .. . . . . . .. . . . . . . . . . .. . . ... . .. . . . . .. . . . . . . .. . . . . . . .. . . . .. . . . . .. . . . . . . .. . . . . . . .. . . .. . . . . . . . .. . . . . .. .. . . . . .. . . . . ... .. ... . . .. . . . . . . .. . . . . . .. . . . . .. . . . . . . . . .. . . . .. .. . . . .. . . . .. .. . . . . . . . . .. . . . . . . . .. . . .. . .. . .. . . .. .. . .. . . . . .. . .. . .. . . . . .. . . . . . . . . .. . . .. . .. . . . .. . . . . . . . . . . .. .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . ... . . . .. . . .. . . . .. . . . . . . . .. . . . .. . . . . . . . .. . . . .. . . . .. . . .. . . . .. . . . . . . . .. . . . .. . . .. . . . .. . . . .. . . .. . . . .. . . . .. . . .. . . . .. . . . .. . . .. . . . .. . . . .. . . .. . . . .. . . . .. . . .. . . . .. . . .. . . . . . . . . .. . . . . . . . .. . . . .. . . . . .. . . . .. . . . .. . . . . .. . . . .. . . . .. . . . . .. . . . .. . . . . .. . . . .. . . . .. . . . . .. . . . .. . . . .. . . . . .. . . . .. . . . .. . . . . .. . . . .. . . . .. . . . . .. . . . .. . . . . .. . . . .. . . . .. . . . . .. . . . . . . . . .. . .. . . . .. . . . . . . .. . . . . . . . .. . . . . . . .. . . . . . ... . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . . .. . . . . . ... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . .. . . . . . . . . .. . . . . . . . . . . . . . . . . . . . .. . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .. . . .. . . . . . . . .. . . . . . .. . . .. . . .. . . .. . .. . . .. .... . . .. . . .. . . .. ... . . ... . . . . .. . . . . .. . . . . .. . . . .. . .. . .. . .. . .. . .. . . . . .. . . . . .. . . . . .. . . . .. . .. . .. . .. . .. . .. . . .......................... .. . .. .. . .. .. . . . . .. .. . .. . .. .. . .. .. . . . . .. .. . .. . .. .. . .. .. . . . . .. .. . . . . . . . . . . . . . . .. .. . .. . .. . . . . .. . .. . .. . . . . .. . .. . . . . . . . . .. . . . . . .. . . . . . .. . . . . . .. . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. ... . . . . .. .. . . . .. . . . . . .. . . .. . .. . . . . . .. . . . . .. . .. . . .. . . .. . .. . . . . . .. . . . . . . . .. . . . ..................... . .. . . . . .. . . . . . . . . . . . .. .. . . . . . . . . . . . . . . . . . .. .. . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . ... . . . . . . .. . . . . .. . . . . .. . .. . .. . .. . .. . . . . . . .. . . . . . . . . . . . .. . . . . . .. . . . . .. . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . .. . . . . . . . .. . . . . . . .. . . .. . . . . ... . . . . . . .. . . . . . . .. . . .. . . . . . .. . . . . . ... . . . . . . .. . . . ................... ............. ........... ........... Figure 2: Example of Less-than Match and Mis-match In other words, when aligning P in position i of T, thereareat most k positionswherethere is a 1 both in P and T. All these indices of P are output. Example: T = 1001111011; P = 1101 When aligning P in position 1 of T, two 1 s are aligned with 1 s: their locations are 1 and 4. When aligning P in position 4 of T, three 1 s arealigned at locations 1,2 and 4. Algorithms 2 4 We use efficient root finding techniques in a symmetric polynomial to solve the k-aligned ones with locations problem in time O(k3nlogmlogk). We use this algorithm to find error locationsin thesmaller matching convolution, but thealgorithm can beapplied to find error locations in all convolutions (e.g. k-mismatches problem of [Abr87]). In section 2 weshow thebasic outlineof the algorithm for the2-dimensional matching with k-differences problem. In section 3 we present the smaller matching problem definition and solution. In section 4 we givealgorithms for handling a forest partial order. In section 5 we present thek-mismatch with error location problem and itssolution. In section 6wecomplete thealgorithm for 2-dimensional matching of a non-rectangular figurewith k differences. We conclude with open problems and future research. 2 Outline of the 2-dimensional M atching Problem The idea of the algorithm is to split the pattern along the verticle line into two parts, PL and PR. Next, find all locations where each of the halves PL and PR match with no more than k differences. Subsequently choose only the locations in the intersection that total at most k differences. 5
Less Than Matching = = ...n T t t Input: A text , a pattern over alphabet with order relation . Output: All locations where 0 j m i T P ... P p p 0 1 0 1 m i 1, p i j t+ j i j t+ jp Can we use the regular methods? Algorithms 2 5
Transitivity Less Than Matching is in fact transitive, but that is not enough for us: does not imply anything about the relation between and . , a c b c a b Algorithms 2 6
Approach A good approach for solving Pattern Matching problems is sometimes solving: The problem for a binary alphabet . The problem for a bounded alphabet . The problem for an ubounded alphabet . In that order. 0,1 Algorithms 2 7
Binary Alphabet The only case that prevents a match at location is the case where: i = = 0 1, 1 0 j m p i j t+ j This is equivalent to: = = = 0 1, 1 1 j m p i j t+ j So how can we solve this case? Algorithms 2 8
Binary Alphabet 1 m 0 p t So if , there is no match at . 0 j = i i j + j = ...n P T t t We can calculate Then we ll calculate We ll return all locations where ( T P 0 1 R (P reverse) using FFT. T i i m + = R )[ 1] 0 Algorithms 2 9
Example ?=0101 ?=0101001110 ??= 1010 ? = 1010110001 Algorithms 2 10
Example Consider ??and ? as polynomial coefficients. ??= 1010 = ?3+ ? ? = 1010110001 = ?9+ ?7+ ?5+ ?4+ ?0 Using OR: ? ??= ?12+ ?10+ ?8+ ?7+ ?6+ ?5+ ?3+ ? Algorithms 2 11
What just happened? T! = PR= Algorithms 2 14
Complexity Time: ( log ) O n m Algorithms 2 15
Bounded Alphabet We need reductions to binary alphabet. For each we ll define: 1 0 1 0 t p p i i = = t p i i t i i = = ... ... T t t P p p 0 1 0 1 n m We notice are binary. T , P Algorithms 2 16
Bounded Alphabet (less than) matches at T Theorem: location if and only if , (less than) matches at location . Proof: does not match at iff P , j i j j p t + = = 1 p = P i P T P i i i T . that is true iff that does not (less than) match at location . , meaning = 0 i j t + j T Algorithms 2 17
Bounded Alphabet So for each , we ll run the binary alphabet algorithm on . We ll return only the locations that matched in all iterations. Time: (min , O m n , T P log ) m Algorithms 2 18
Problem (min , log ) O m n m Can be worse than the na ve algorithm. What about unbounded alphabet? We present an improvement on the next slides. Algorithms 2 19
n m The Trick n m We ll split the text into overlapping segments of size like this: 2m 2m 2m 2m 2m 2m 2m 2m 2m 2m 2m 2m 2m 2m So every match in the text must appear in whole in one of the segments. 20
Abrahamson-Kosaraju Method First, use the segment splitting trick. Therefore we can assume . For each location in text, we ll produce a triplet: , where . For each location in pattern, we ll produce a triplet: , where . We now have triplets all together. 3m 2 T m i = it a ( ,' ', ) a T i i b P i = ip b ( ,' ', ) Algorithms 2 21
Abrahamson-Kosaraju Method We ll hold all triplets together. Sort all triplets according to symbol. We ll define a symbol that has more than triplets as a frequent symbol . There are frequent symbols. Put all frequent symbols triplets aside. m ( ) O m Algorithms 2 22
Abrahamson-Kosaraju Method For each such group, choose the symbol of the first triplet in group as the group s representative. For instance, on previous example, group 1 s representative is and group 2 s representative is . There are representatives all together. a d ( ) O m Algorithms 2 27
Abrahamson-Kosaraju Method To sum up: ( O frequent symbols. representatives of non-frequent symbols. We ll swap each non-frequent symbol in pattern and text with its representative. Now our text and pattern are over sized alphabet. ) m ( ) O m ( ) O m Algorithms 2 28
Abrahamson-Kosaraju Method We can now run our algorithm over the new text and pattern in . But we still haven t handled comparisons between two non-frequent symbols that are in the same group. ( log ) O mm m Algorithms 2 35
Abrahamson-Kosaraju Method We ll do so naively in each group: For each triplet in the group For each triplet of the form in the group, if , then add an error at location . i k j = T ( ,' ', ) P j ,' ', ) T k ( i + i j kt jp P Time: ( ) O m m p t j k Algorithms 2 36
Running Time For one segment: Sorting the triplets and representatives: . Running the algorithm: Correcting results (Adding in-group errors): . Overall for one segment: . Overall for all segments: . ( log ) O m m . ( log ) O mm m ( ) O m m ( log ) O m m m ( log ) O n m m Algorithms 2 37
Running Time We can improve to . Left as an exercise. ( log ) O n m m Algorithms 2 38
! Algorithms 2 39
