Introduction

Pattern matching problem on strings is defined as finding all occurences of a pattern string in a text string. Many of pattern matching algorithms can find occurences of the pattern fast by preprocessing the pattern such as AC automaton [1], and KMP algorithm [7], or by constructing data structure from the text such as suffix tree [13], suffix array [9], and position heap [2].

Katsura et al. [5,6] defined a set (or tuple) of strings be a multi-track string, and formulated the pattern matching problem on multi-track strings, called permuted pattern matching. In order to solve this problem, they proposed permuted pattern matching algorithms by constructing data structure from text such as multi-track suffix tree [5], multi-track position heap [6], or by preprocessing the the pattern such as AC automaton based algorithm [5].

In this paper, we propose three new algorithms for multi-track pattern matching problem, based on KMP algorithm [7] 1 . The first one is a full-permuted pattern matching algorithm, that we call it MTKMP for short. Second and third are filtering algorithms for multi-track full-and sub-permuted matching problem, respectively. For short, we call them Filter-MTKMP-Full and Filter-MTKMP, respectively. Different with AC automaton based algorithm [5] that constructs failure functions for each track of the pattern, our algorithms only construct one failure function for a multi-track pattern. Also, our algorithms match the whole tracks of the pattern to the text instead of matching each track of the text independently.

We show that MTKMP runs in O(mM ) time for constructing the failure function, and O(nN ) for matching. Both Filter-MTKMP-Full and Filter-MTKMP run in O(m(M + σ)) time for constructing the failure function, O(n(N + σ)) for filtering, and O(mM ) to verify each candidate. Moreover, the experiment results show that proposed algorithms run faster than AC automaton based multi-track pattern matching algorithm [5] for full-permuted matching, and Filter-MTKMP works faster on sub-permuted-matching when the alphabet size and the track count of the pattern are large.

Preliminaries

Let w ∈ Σ n be a string of length n over an alphabet Σ, and σ = |Σ| be the alphabet size. |w| denotes the length of w and w[i] denotes i-th character of w. The substring of w that begins at position i and ends at position j is denoted by w

[i : j] for 1 ≤ i ≤ j ≤ |w|. In addition, w[: i] = w[1 : i] and w[i :] = w[i : |w|]

denotes a prefix and a suffix of w, respectively. For two strings x and y, x ≺ y denotes that x is lexicographically smaller than y, and x ≼ y denotes that either x equals to y or x ≺ y.

A multi-track string (or multi-track for short) W = (w 1 , w 2 , ..., w N ) is an N -tuple of strings w i ∈ Σ n , and each w i is called the i-th track of W. The length n of a multi-track is denoted by |W| len . The number N of tracks in a multi-track is called track count and denoted by |W| num . For two multi-tracks X = (x 1 , x 2 , .., x N ) and Y = (y 1 , y 2 , .., y N ), we write Let r = (r 1 , r 2 , . . . , r M ) be a partial permutation of (1, 2, . . . , N ) for M ≤ N . For a multi-track W = (w 1 , w 2 , . . . , w N ), a permuted multi-track of W is denoted by either W⟨r 1 , r 2 , . . . , r M ⟩ or W⟨r⟩. Sorted index of a multi track SI(W) = (r 1 , r 2 , . . . , r N ) is defined as a permutation such that w ri ≼ w rj for any 1 ≤ i ≤ j ≤ N . For two multi-tracks X = (x 1 , x 2 , . . . , x M ) and Y = (y 1 , y 2 , . . . , y N ), X permuted-matches Y, denoted by X ◃▹ ⊑ Y, if ∃r.X = Y⟨r⟩, and X full-permutedmatches Y, denoted by X ◃▹ = Y, if M = N and ∃r.X = Y⟨r⟩. Throughout the paper, we assume that P is a pattern with |P| num = M and |P| len = m, and T is a text with |T| num = N and |T| len = n. The pattern matching problem on multi-tracks are defined as follows.

X = Y if x i = y i for 1 ≤ i ≤ N . W[i] denotes (w 1 [i], w 2 [i], ...w N [i]),

Problem 1 (Permuted pattern matching). Given a multi-tracks text T and a multi-track pattern P, output all positions i that satisfy

P ◃▹ ⊑ T[i : i + m − 1].

Moreover, we call it full-permuted pattern matching if M = N , and sub-permuted pattern matching if M < N .

Algorithm 1: MTKMP pattern matching algorithmInput: Multi-track T, Multi-track P Output: match positions compute SI (T[i :]) for 1 ≤ i ≤ n and SI (P[i :]) for 1 ≤ i ≤ m; 1 constructFailureFunction(); 2 i = 1; j = 1; 3 while i ≤ n do 4 while j > 0 and T[i]⟨SI (T[i − j + 1 :])⟩ ̸ = P[j]⟨SI (P[1 :])⟩ do j = F [j]; 5 i = i + 1; j = j + 1; 6 if j > m then 7 output (i − j + 1); 8 j = F [j]; 9 Function constructFailureFunction() 10 i = 1; j = 1; F [1] = 0; 11 while i ≤ m do 12 while j > 0 and P[j]⟨SI (P[1 :])⟩ ̸ = P[i]⟨SI (T[i − j + 1 :])⟩ do j = F [j]; 13 i = i + 1; j = j + 1; 14 F [i] = j; 15

In this section, we propose an algorithm for full-permuted pattern matching that based on KMP algorithm, named multi-track KMP algorithm (shortly MTKMP). In a similar manner to the original KMP algorithm, MTKMP constructs the failure function from the pattern, then uses it to shift the pattern when mismatch occurs. The MTKMP algorithm is described in Algorithm 1.

The failure function F [i] for 1 ≤ i ≤ m+1 in MTKMP is defined as the length of the longest proper suffix of P[1 : i − 1] that permuted-matches with a prefix of P, except F [1] = 0 and F [2] = 1. In order to construct the failure function, first MTKMP finds the value of sorted index SI (P[i : m]) for all 1 ≤ i ≤ m. Then permuted-matching of suffix P[j : i] and prefix P[1 : i − j + 1] is performed by using SI (P[1 :]) and SI (P[j :]).

MTKMP performs permuted pattern matching from left to right of the pattern and the text. Sorted indexes of the text and the pattern are used to perform permuted-matching between the pattern and a substring of the text. If characters on text and pattern are mismatched, then we shift the position of the pattern by using the failure function. If the pattern matches a substring of the text, then MTKMP outputs the position of the text and shifts the pattern according to the failure function.

The MTKMP algorithm runs in O(mM ) time for constructing the failure function and O(nN ) time for matching. Suffix index SI (P[i :]) for 1 ≤ i ≤ m and SI (T[i :]) for 1 ≤ i ≤ n can be computed in O(mM ) and O(nN ) respectively by using suffix tree [3,10,12,13] or suffix array [4,8,9,11]. Next, both the outer while loop and the inner while loop are called O(m) times, since the i − j ≤ i ≤ m + 1 and the value of i always increase each time the outer loop is called, and the value of i − j always increases each time the inner loop is called. Since

5 i = i + 1; j = j + 1; 6 if j > m then 7 if T[i − j + 1 : i − 1] ◃ ▹ ⊑ P then output (i − j + 1); 8 j = F [j]; 9 Function constructFailureFunction() 10 i = 1; j = 1; F [1] = 0; 11 while i ≤ m do 12 while j > 0 and P ′ [i] ̸ = P ′ [j] do j = F [j]; 13 i = i + 1; j = j + 1; 14 if i ≤ m and P ′ [i] = P ′ [j] then F [j] = F [i]; else F [j] = i;

KMP Algorithm for Filtering on Multi-Track String

In this section we propose two filtering algorithms that can outperform MTKMP for permuted pattern matching problems. Instead of the suffix index, we use simple functions to transforms the multi-track string, that can be computed faster than the suffix index. Then, by transforming the pattern and the text, the KMP algorithm can be applied to find candidates of permuted-matching positions. Finally, every candidate position is checked whether or not the pattern is permuted-matched in each position.

The first algorithm is an algorithm for full-permuted pattern matching problem called Filter-MTKMP-Full. We use two functions in this algorithm. Generally, we can implement another function that has a false positive property. The second algorithm, Filter-MTKMP is an algorithm for both full-and subpermuted pattern matching problems. Filter-MTKMP transforms multi-track into alphabet bucket and implements KMP algorithm to it.

Full-Permuted Pattern Matching Algorithm

The Filter-MTKMP-Full algorithm is described in Algorithm 2. First, we transform P by a function func() that has a false-positive property, that is if X ◃▹ = Y then func(X) = func(Y). We propose two functions, sort() and bucket().

Definition 1. ForZ = (z 1 , z 2 , . . . , z N ), sort(Z) = Z ′ = (z ′ 1 , z ′ 2 , . . . , z ′ N ) such that ∃r.Z ′ [i] = Z[i]⟨r⟩ and z ′ j [i] ≼ z ′ j+1 [i] for 1 ≤ i ≤ |Z| len and 1 ≤ j < N . Definition 2. For Z = (z 1 , z 2 , . . . , z N ), bucket(Z) = (b 1 , b 2 , . . . , b σ ) such that b j [i] is the number of the lexicographical j-th character in Z[i].

For example, for a multi-track Z = (abab, bbac, aabb, cabb, abba), the sort(Z) and bucket(Z) are defined as follows,

Z =       a b a b b b a c a a b b c a b b a b b a       , sort(Z) =       a a a a a a a b a b b b b b b b c b b c       , bucket(Z) =   3 2 2 1 1 3 3 3 1 0 0 1   .

For a multi-track Z, sort(Z) can be computed in O(n(N + σ)) by using the bucket sorting algorithm, and bucket(Z) can be computed in O(nN ) time by counting all characters in Z even if naively.

Next, Filter-MTKMP-Full constructs the failure function F of the transformed multi-track P ′ by similar algorithm as the KMP algorithm.

Pattern matching in Filter-MTKMP-Full is performed on P ′ and T ′ . When unmatched is occurred, the pattern is shifted by using the failure function. If P ′ matches to T ′ [i : j], then the algorithm checks whether the pattern P is permuted-matched with T[i : j] or not, and outputs it if the pattern is permutedmatched.

In the same way as described in MTKMP, the failure function can be constructed in O(m(M + σ)) time and the filtering algorithm runs in O(n(N + σ)) time, since sort() and bucket() needs O(M ) and O(σ) time for each comparison, respectively. Also, the Filter-MTKMP-Full algorithm runs in O(m(M + σ)) time for constructing the failure function. In addition, Filter-MTKMP-Full need O(cmM ) time for checking the candidates, where c is the number of candidates.

Permuted Pattern Matching Algorithm

Filter-MTKMP algorithm is an extended version of the Filter-MTKMP-Full algorithm that can be applied to the sub-permuted pattern matching problem. This algorithm uses bucket() to transforms the pattern and the text, and implement the KMP algorithm to the transformed pattern and text. Moreover, this algorithm uses diff (X, Y ) function instead of X ̸ = Y to loosen the condition, thus sub-permuted pattern matching can be performed.

Algorithm 3 shows a pseudocode of the Filter-MTKMP algorithm. First, it transforms P to multi-track bucket P ′ and constructs the failure function F of the multi-track bucket by using a function diff (X,

Y ) = ∑ σ i=1 max(0, Y [i] − X[i]) for two13 i = i + 1; j = j + 1; 14 if i ≤ m and P ′ [i] = P ′ [j] then F [j] = F [i]; else F [j] = i; 15 Function diff (Vector X, Vector Y ) 16 Int sum = 0; 17 for k = 1 to |X| do 18 sum = sum + max(0, Y [k] − X[k]);

Experiments

In order to evaluate the performance of proposed algorithms, we conduct experiments and compare the running time of proposed algorithms with AC automaton based algorithm [5].

In the first experiment, we compare running time of the algorithms for solving full-permuted pattern matching. We change one of the parameters while keeping other parameters constant. We set constant parameter as follows, n = 100000, m = 10, N = M = 1000, and σ = 2. We use random text and pattern with 50 occurrences of the pattern inserted to the text. Figure 1 (a)-(d) show running time of the algorithms when one of the parameters n, N , m, and σ is changed respectively. We can see that the proposed algorithms are faster than AC automaton based algorithm. However, many false positive candidates are found when the length of the pattern is short, and filtering algorithms need lots of time to verify them. track count of the text and track count of the pattern is small, also when the alphabet size is large.

Conclusion

We proposed three algorithms based on the KMP algorithm, that are MTKMP, Filter-MTKMP-Full and Filter-MTKMP. These algorithms can solve the permuted pattern matching problem in linear time. We also conducted computational experiments, and showed that proposed algorithms work faster than AC-automaton based algorithm.