A New Model to Solve Swap Matching Problem and Efficient Algorithms for Short Patterns
- 格式：pdf
- 大小：228.85 KB
- 文档页数：12
A New Model to Solve Swap Matching Problemand Efficient Algorithms for Short PatternsCostas S.Iliopoulos and M.Sohel RahmanAlgorithm Design GroupDepartment of Computer Science,King’s College London,Strand,London WC2R2LS,England{csi,sohel}@/adgAbstract.In this paper,we revisit the much studied problem of Pat-tern matching with Swaps(Swap Matching problem,for short).Wefirstpresent a new graph-theoretic approach to model the problem,whichopens a new and so far unexplored avenue to solve the problem.Then,using the model,we devise an efficient algorithm to solve the swap match-ing problem.The resulting algorithm is an adaptation of the classic shift-or algorithm.For patterns having length similar to the word-size of thetarget machine,the algorithm runs in O((n+m)log m)time,where nand m are the length of the text and the pattern respectively.1IntroductionThe classical pattern matching problem is tofind all the occurrences of a given pattern P of length m in a text T of length n,both being sequences of characters drawn from afinite character setΣ.This problem is interesting as a fundamental computer science problem and is a basic need of many practical applications such as text retrieval,music retrieval,computational biology,data mining,network security,among many others.In this paper,we revisit the Pattern Matching with Swaps problem(the Swap Matching problem,for short),which is a well-studied variant of the classic pattern matching problem.The pattern P is said to match the text T at a given location i,if adjacent pattern characters can be swapped,if necessary,so as to make the pattern identical to the substring of the text ending(or equivalently,starting)at location i.All the swaps are constrained to be disjoint,i.e.,each character is involved in at most one swap. Amir et al.[1]obtained thefirst non-trivial results for this problem.They showed how to solve the problem in time O(nm1/3log m logσ),whereσ=min(|Σ|,m). Amir et al.[3]also studied certain special cases for which O(n log2m)time can be obtained.However,these cases are rather restrictive.Finally,Amir et al.[2] solved the Swap Matching problem in time O(n log m logσ).We remark that all the above solutions to swap matching depend on the fast fourier transform (FFT)technique.It may be noted here that approximate swapped matching[4] and swap matching in weighted sequences[7]have also been studied in the literature.2The contribution of this paper is as follows.Wefirst present a new graph-theoretic approach to model the problem which opens a new and so far unex-plored avenue to solve the problem.Then,using the model,we devise an efficient algorithm to solve the swap matching problem.The resulting algorithm is an adaptation of the classic shift-or algorithm and runs in O((n+m)log m)if the pattern is similar in size to the size of word in the target machine.This seemsto be thefirst attempt to provide an efficient solution to the swap matching problem without using the FFT techniques.The rest of the paper is organized as follows.In Section2,we present some preliminary definitions.Section3presents our new model to solve the swap matching problem.In Section4,we present the algorithm to solve the swap matching problem.Finally,we briefly conclude in Section5.2PreliminariesA string is a sequence of zero or more symbols from an alphabetΣ.A string Xof length n is denoted by X[1..n]=X1X2...X n,where X i∈Σfor1≤i≤n. The length of X is denoted by|X|=n.A string w is called a factor of X ifX=uwv for u,v∈Σ∗;in this case,the string w occurs at position|u|+1inX.The factor w is denoted by X[|u|+1..|u|+|w|].A k-factor is a factor of length k.A prefix(or suffix)of X is a factor X[x..y]such that x=1(y=n),1≤y≤n(1≤x≤n).We define i-th prefix to be the prefix ending at positioni i.e.X[1..i],1≤i≤n.On the other hand,i-th suffix is the suffix starting at position i i.e.X[i..n],1≤i≤n.Definition1.A swap permutation for X is a permutationπ:{1,...,n}→{1,...,n}such that:1.ifπ(i)=j thenπ(j)=i(characters are swapped).2.for all i,π(i)∈{i−1,i,i+1}(only adjacent characters are swapped).3.ifπ(i)=i then Xπ(i)=X i(identical characters are not swapped).For a given string X and a swap permutationπfor X,we useπ(X)to denotethe swapped version of X,whereπ(X)=Xπ(1)Xπ(2)...Xπ(n).Definition2.Given a text T=T1T2...T n and a pattern P=P1P2...P m,Pis said to swap match at location i of T if there exists a swapped version P ofP that matches T at location i,i.e.P j=T i−m+j for j∈[1..m].Problem“SM”(Pattern Matching with Swaps).Given a text T=T1T2...T n and a pattern P=P1P2...P m,we want tofind each location i∈[1..n]such thatP swap matches with T at location i.Definition3.A string X is said to be degenerate,if it is built over the potential2|Σ|−1non-empty sets of letters belonging toΣ.3 Example1.Suppose we are considering DNA alphabet i.e.Σ=ΣDNA={A,C,T,G}. Then we have15non-empty sets of letters belonging toΣDNA.In what follows,the set containing A and T will be denoted by[AT]and the singleton[C]willbe simply denoted by C for ease of reading.Definition4.Given two degenerate strings X and Y each of length n,we sayX[i]matches Y[j],1≤i,j≤n if,and only if,X[i]∩Y[j]=∅.Example2.Suppose we have degenerate strings X=AC[CT G]T G[AC]C andY=T C[AT][AT]T T C.Here X[3]matches Y[3]because X[3]=[CT G]∩Y[3]= [AT]=T=∅.3A Graph-Theoretic Model for Swap MatchingIn this section,we present a new model to solve the swap matching problem.Inour model,we view the text and the pattern as two separate graphs.We startwith the following definitions.Definition5.Given a text T=T1...T n of Problem SM,a T-graph,denotedby T G=(V T,E T),is a directed graph with n vertices and n−1edges suchthat V T={1,2,...n}and E T={(i,i+1)|1≤i<n}.For each i∈V T wedefine label(i)=T i and for each edge e≡(i,j)∈E T we define label(e)≡label((i,j))≡(label(i),label(j))=(T i,T j).Note that the labels in the above definition may not be unique.Also,we normallyuse the labels of the vertices and the edges to refer to them.a→c→a→c→b→a→c→c→b→a→c→a→c→b→aFig.1.The corresponding T-graph of Example5Example3.Suppose,T=acacdaccbacacba.Then the corresponding T-graph is shown in Figure1.Definition6.Given a text P=P1...P m of Problem SM,a P-graph,denotedby P G=(V P,E P),is a directed graph with3m−2vertices and at most5m−9edges.The vertex set V P can be partitioned into three disjoint vertex setsnamely V P(+1),V P0,V P(−1)such that|V P(+1)|=|V P(−1)|=m−1and|V P(0)|=m.The partition is defined in a3×m matrix M[3,m]as follows.For the sake of notational symmetry we use M[−1],M[0]and M[+1]to denote respectively the rows M[1],M[2]and M[3]of the matrix M.1.V P(−1)={M[−1,2],M[−1,3],...M[−1,m]}2.V P(0)={M[0,1],M[0,2],...M[0,m]}43.V P (+1)={M [+1,1],M [+1,2],...M [+1,m −1]}The labels of the vertices are derived from P as follows:1.For each vertex M [−1,i ]∈V P (−1),1<i ≤m :label (M [−1,i ])=P i −1if P i −1=P i ,X if P i −1=P i ,where X /∈Σ(1)2.For each vertex M [0,i ]∈V P (0),1≤i ≤m,label (M [0,i ])=P i3.For each vertex M [+1,i ]∈V P (+1),1≤i <m :label (M [+1,i ])= P i +1if P i =P i +1,X if P i =P i +1,where X /∈Σ(2)The edge set E P is defined as the union of the sets E P (−1),E P (0)and E P (+1)asfollows:1.E P (−1)={(M [−1,i ],M [0,i +1]),(M [−1,i ],M [+1,i +1])|2≤i ≤m −2 label (M [−1,i ])=X } {(M [−1,m −1],M [0,m ])|label (M [−1,m −1])=X }2.E P (0)={(M [0,i ],M [0,i +1])|1≤i ≤m −1} {((M [0,i ],M [+1,i +1])|1≤i ≤m −2 label (M [+1,i +1])=X }3.E P (+1)={(M [+1,i ],M [−1,i +1])|1≤i ≤m −1 label (M [+1,i ])=X }1The labels of the edges are derived from using the labels of the vertices in the obvious way.Example 4.Suppose,P =acbab .Then the corresponding P -graph P G is shown in Figure 2.On the other hand,the corresponding P -graph P G for P =accabis shown in Figure 3.Note that in P we have P 2=P 3=c .The dotted edges in Figure 3are non-existent in P G and are shown only for the sake of understand-ing.Definition 7.Given a P -graph P G ,a path Q =u 1 u =u 1u 2...u is a sequence of consecutive directed edges (u 1,u 2),(u 2,u 3),...(u −1,u ) in P G starting at node u 1and ending at node u .The length of the path Q ,denoted by len (Q ),is the number of edges on the path and hence is −1in this case.It is easy to note that the length of a longest path in P G is m −1.Definition 8.Given a P -graph P G and a T -graph T G ,we say that P G matches T G at position i ∈[1..n ]if and only if there exists a path Q =u 1u 2...u m in P G having u ∈{M [0,1],M [+1,1]}and v ∈{M [−1,m ],M [0,m ]}such that for j ∈[1..m ]we have label (u j )=T i −m +j1Note that,if label (M [+1,i ])=X then label (M [−1,i +1])=X as well.5a −1+112345Fig.2.P-graph of the Pattern P=acbaba −1+112345Fig.3.P-graph of the Pattern P =accabThe above definitions set up our model to solve the swap matching problem. The following Lemma presents the idea for the solution.Lemma1.Given a pattern P of length m and a text T of length n,suppose P G and T G are the P-graph and T-graph of P and T,respectively.Then,P swap matches T at location i∈[1..n]of T if and only if P G matches T G at position i∈[1..n]of T G.Proof.The proof basically follows easily from the definition of the P-graph.At each column of the matrix M,we have all the characters as nodes considering the possible swaps as explained below.Each node in row(−1)and(+1)represents a6swapped situation.Now consider column i of M corresponding to P G .According to definition,we have M [−1,i ]=P i −1and M [+1,i −1]=P i .These two nodes represents the swap of P i and P i −1.Now,if this swap takes place,then in the resulting pattern,P i −1must be followed by P i .To ensure that,in P G ,the only edge starting at M [+1,i −1],goes to M [−1,i ].On the other hand,from M [−1,i ]we can either go to M [0,i +1]or to M [+1,i +1]:the former is when there is no swap for the next pair and the later is when there is another swap for the next pair.Recall that,according to the definition,the swaps are disjoint.Finally,the nodes in row 0represents the normal (non-swapped)situation.As a result,from each M [0,i ]we have an edge to M [0,i +1]and an edge to M [+1,i +1]:the former is when there is no swap for the next pair as well and the later is when there is a swap for the next pair.So it is easy to see that all the paths of length m −1in P G represents all combinations considering all possible swaps in P .Hence the result follows.It is clear that the number of possible paths of length m −1in P G is exponen-tial in m .So spelling all the paths and then perform a pattern matching against,possibly,a index of T is very time consuming unless m is constant.We on the other hand exploit the above model in a different way and apply a modified version of the classic shift-or [5]algorithm to solve the swap matching problem.In the rest of this section,we present a notion of “Forbidden Graph”and in the next section we show how to exploit this notion and modify the shift-or algorithm to solve the swap matching problem.Definition 9.Given a P -graph P G =(V P ,E P ),the forbidden Graph P G=(V P ,E P )is such that V P =V P and E P is defined as follows:E P ={(M [i,j ],M [i,j +1])|i ∈{−1,0,+1},1≤j <m,(label (M [i,j ])=X label (M [i,j +1])=X ) (∀(M [k,j ],M [k,j +1])∈E P ,k ∈{−1,0,+1},label ((M [k,j ],M [k,j +1]))=label ((M [i,j ],M [i,j +1])))}.In other words,the forbidden graph P G contains an edge (u,v )from column j to j +1,where 1≤j <m ,if,and only if,there exists no edge from j to j +1in P -graph having the same label.Example 5.Suppose,P =acbab .Then the forbidden graph P G corresponding to the P -graph P G is shown in Figure 4.The edges of P G are shown in dashed lines and the edges of P G are shown in solid lines.Note that,(M [+1,3],M [+1,4])is nonexistent in P G ,because,label ((M [+1,3],M [+1,4]))=(a,b )and we have(M [+1,3],M [−1,4])∈E P with the same label (a,b ).4Algorithm for Swap MatchingIn this section,we present a new efficient algorithm based on the model pre-sented in Section 3.Our algorithm is a modified version of the classic shift-or algorithm for pattern matching.For the sake of completeness,we first present a7a−10+112345Fig.4.Forbidden graph (solid edges)corresponding to the P -graph (dashed edges)of the Pattern P =acbabbrief account of the shift-or algorithm in the following subsection.In Section 4.2we present the modifications needed to adapt it to solve the swap matching problem.4.1Shift-Or AlgorithmThe shift-or algorithm uses the bitwise techniques and is very efficient if the size of the pattern is no greater than the word size of the target processor.The following description of the shift-or algorithm is taken from [6]after slight adaptation to accommodate our notations.Let R be a bit array of size m.Vector R j is the value of the array R after text character T j has been processed.It contains information about all matches of prefixes of P that end at position j in the text.So,for 1≤i ≤m we have:R j [i ]= 0if P [1..i ]=T [j −i +1..j ],1Otherwise.(3)The vector R j +1can be computed after R j as follows.For each R j [i ]=0:R j +1[i +1]= 0if P i +1=T j +1,1Otherwise.(4)andR j +1[0]= 0if P 0=T j +1,1Otherwise.(5)8If R j+1[m]=0then a complete match can be reported.The transition from R j to R j+1can be computed very fast as follows.For each c∈Σlet D c be a bit array of size m such that for1≤i≤m,D c[i]=0if and only if P i=c.The array D c denotes the positions of the character c in the pattern P.Each D c for all c∈Σcan be preprocessed before the pattern search. And the computation of R j+1reduces to two operations,shift and or:R j+1=SHIF T(R j)OR D Tj+14.2Modifying Shift-Or Algorithm for Swap MatchingIn this section,we modify the shift-or algorithm to solve swap matching problem. To do that we use the graph model,particularly the forbidden graph,presented in Section3.The idea is quite simple and described as follows.First of all,the shift-or algorithm can be extended easily for the degenerate patterns[5].In our swap matching model the pattern can be thought of a having a set of letters at each po-sition as follows:˜P=[M[0,1]M[+1,1]][M[−1,2]M[0,2]M[+1,2]]...[M[−1,m−1]M[0,m−1][+1,m−1]][M[−1,m]M[0,m]].Note that we have used P instead of P above because,in our case,the sets of characters in the consecutive po-sitions in the pattern P don’t have the same relation as in a usual degenerate pattern.In particular,in our case,a match at position of i+1of P will depend on the previous match of position i as the following example shows.Example6.Suppose,P=acbab and T=bcbaaabcba.The P-graph of P is shown in Figure2.So,in line of above discussion,we can say that P=[ac][acb][cba][ba][ab]. Now,as can be easily seen,if we consider degenerate match,then P matches T at position2and6.However,P swap matches T only at position6;not at position2.To elaborate,note that at position2,the match is due to c.So,ac-cording to the graph P G the next match has to be an a and hence at position2 we can’t have a swap match.In what follows,we present a novel technique to adapt the shift-or algorithm to tackle the above situation.We use the forbidden graph as follows.For the sake of convenience,in the discussion that follows,we refer to both P and the pattern P as though they are equivalent;but it will be clear from the context what we really mean.Suppose we have a match up to position i<m of P in T[j−i+1..j].Now we have to check whether there is a‘match’between T j+1and P i+1.For simple degenerate match,we only need to check whether T j+1∈P i+1 or not.However,as the Example6shows,for our case we need to do more than that.What we do is as follows.Suppose that T j=c=M[ ,i].Now,from the forbidden graph we know which of the M[k,i+1],k∈[−1,0,+1]can’t follow M[ ,i].So,for example,even if M[q,i+1]=T[j+1]we can’t continue if there is an edge from M[ ,i]to M[q,i+1]in the forbidden graph(or equivalently if there is no edge from M[ ,i]to M[q,i+1]in the P-graph).In the rest of this section,we show how we use the forbidden graph to modify the shift-or algorithm to solve the swap matching problem.Recall that,wefirst process the pattern to compute the masks D c for every c∈Σ.This can be done9 in O(m/w(m+Σ))time[5]when pattern is not degenerate.However,in our case, we need to assume that our pattern has a set of letters in each position.In this case,we require O(m/w(m +Σ))time where m is the sum of the cardinality of the sets at each position[5].In general degenerate strings,m can be m|Σ|in the worst case.However,in our case,m =|V P|=O(m),where V P is the vertex set of the P-graph.So,computation of the D-mask requires O(m/w(m+Σ))time in the worst case.Then we do a further processing on P as follows.We compute the forbidden graph P G=(V P,E P)from the P-graph P G=(V P,E P).Recall that V P=O(m)and E P=O(m)and therefore,by definition,we have V P=O(m) and E P=O(m).So we can compute the forbidden graph in O(m)time.Two edges(u,v),(x,y)of the forbidden graph(and the P-graph)are said to be‘same’if label(u)=label(x)and label(v)=label(y),i.e.if the two edges have the same labels.Also,given an edge(u,v)≡(M[i1,j1],M[i2,j2])we say that edge(u,v)‘belongs to’column j2,i.e.where the edge ends;and we say col((u,v))≡col((M[i1,j1],M[i2,j2]))=j2.Now we traverse all the edges and construct a set of sets S={S1...S }such that each S i,1≤i≤ contains the edges that are‘same’.The set S i is named by the(same)label of the edges it contains and we may refer to S i using its name.Now,we construct forbiddenmasks F Si ,1≤i≤ such that F Si[k]=1if,and only if,there is an edge(u,v)∈S i having col((u,v))=k.Note that =O(m).The construction of the forbidden mask can be done in O(m/w m log m) time as follows.Wefirst initialize all the entries of the forbidden masks to 0which requires O(m/w m)time.Then we start traversing the edges.Con-sider thefirst edge(u1,v1).We know the label of this edge is label((u1,v1))≡(label(u1),label(v1)).We include the label of this edge in a name database and assign a set S i∈S to this name and keep pointers for constant time referencelater.We also set F Si [j]=1,where col((u1,v1))=j.Now,consider anotheredge(u k,v k).This time wefirst check whether label((u k,v k))already exists in the name database.If yes,then we use the existing name to do the update oth-erwise we include the label in the name database and continue as before.It is clear that this check in the database can be done in O(log )=O(log m).Since we have O(m)edges,the complete construction of the forbidden mask requires O(m/w m log m)time.With the forbidden masks at our hand,for our problem,we simply need to compute R j+1as follows:R j+1=SHIF T(R j)OR D Tj+1OR F(Tj,T j+1)Note that,to locate the appropriate forbidden mask we again need to perform a look up in the name database constructed during the construction of the forbidden mask.So,in total the construction of the R values require O(n log m)time.One detail is that,if F(Tj ,T j+1)doesn’t exist then we assume the mask tohave all0’s.It is easy to see that this works because the forbidden mask allows R j+1to have0at position i if,and only if,the edge(T j,T j+1)is not‘forbidden’. Example7shows a complete execution of our algorithm.10a ca c a−10+112345c X Fig.5.Forbidden graph for P =accab D D a D b D c D X a 1[ac ]01012[acc ]01013[acc ]01014[cab ]00015[ab ]0011a Here X indicates all letters that are not present in PFig.6.The D -masks for Example 7Example 7.Suppose,P =accab and T =acacbaccbacacba .The P -graph and corresponding forbidden graph of P is shown in Figure 3and 5respectively.The D -masks and F -masks are shown in Figure 6and 7respectively.Figure 8shows the detail computation of the R bit array up to the first match found.Figure 8shows the complete computed values of R .The running times of the different phases of the algorithm are listed in Fig-ure 10.Therefore,in total the running time of our algorithm is O (m/w (m log m +|Σ|+n log m )).So,when pattern size is similar to the word size of the target machine,we achieve a very good running time of O (m log m +|Σ|+n log m )=O ((m +n )log m ).Therefore we have the following theorem.Theorem 1.The swap matching problem can be solved in O (m/w (m +n )log m )worst case running time.Corollary 1.The swap matching problem can be solved in O ((m +n )log m )worst case running time if the pattern is similar to the word size of the target machine.11F(a,a)F(a,b)F(b,b)F(c,c)F(c,a)F(X,X)a10000002100100300000041101005101010a Here(X,X)indicates all edges that are not present in the forbidden graphFig.7.The F-masks for Example7−SH D a F(X,X)OR SH D c F(a,c)OR SH D a F(c,a)OR SH D c F(a,c)OR SH D b F(c,b)OR... 1100000000000000000101... 2110010000000000000101... 3110011001000000000101... 4110011001100100000000... 5110011101101111010000...... Fig.8.Detail steps up to thefirst reported match of Example7.Here SH meansShift operation on the previous column and OR means or operation on the previous3columns.123456789101112131415a c a cb ac c b a c a c b a1a0000100010000102c1000110111000113c110011*********4a111001*********5b111100*********Fig.9.The complete computed values of R in Example7.The occurrences of swapmatch are shown using tick marks.Note that the end location of the matches areidentified here.12Phase Running TimeComputation of D-masks O(m/w(m+|Σ|))Computation of F-masks O(m/w m log m)Computation of R-values O(m/w n log m)Fig.10.Running times of the different phases5ConclusionIn this paper,we have revisited the Pattern Matching with Swaps problem,a well-studied variant of the classic pattern matching problem.We have presented a new graph-theoretic approach to model the problem which opens a new and so far unexplored avenue to solve the problem.Then,using the model,we have devised an efficient algorithm to solve the swap matching problem.The resulting algorithm is an adaptation of the classic shift-or algorithm and runs in O((n+ m)log m)if the pattern-length is similar to the word-size in the target machine. Notably,the best known algorithm for swap matching runs in O(n log m logσ) and uses the FFT technique,which has large hidden constants inside its good theoretical bound.This seems to be thefirst attempt to provide an efficient solution to the swap matching problem without using FFT techniques.Moreover the techniques used in our algorithm is quite simple and easy to implement.We believe that the new graph theoretic model could be used to devise more efficient algorithms and a similar approach can be taken to model similar other variants of the classic pattern matching problem.Furthermore,it would be interesting to‘swap’the definitions of T-graph and P-graph and investigate whether efficient pattern matching techniques for Directed acyclic graph can be employed to devise efficient off-line and online algorithms for swap matching. References1. A.Amir,Y.Aumann,ndau,M.Lewenstein,and N.Lewenstein.Patternmatching with swaps.J.Algorithms,37(2):247–266,2000.2. A.Amir,R.Cole,R.Hariharan,M.Lewenstein,and E.Porat.Overlap matching.put.,181(1):57–74,2003.3. A.Amir,ndau,M.Lewenstein,and N.Lewenstein.Efficient special casesof pattern matching with swaps.Inf.Process.Lett.,68(3):125–132,1998.4. A.Amir,M.Lewenstein,and E.Porat.Approximate swapped matching.Inf.Process.Lett.,83(1):33–39,2002.5.R.Baeza-Yates and G.Gonnet.A new approach to text municationsof the ACM,35:74–82,1992.6. C.Charras and T.Lecroq.Handbook of Exact String Matching Algorithms.Textsin Algorithmics.King’s College,London,2004.7.H.Zhang,Q.Guo,and C.S.Iliopoulos.String matching with swaps in a weightedsequence.In J.Zhang,J.-H.He,and Y.Fu,editors,CIS,volume3314of Lecture Notes in Computer Science,pages698–704.Springer,2004.。
