Permuted Pattern Matching Algorithms on Multi-Track Strings

Abstract

A multi-track string is a tuple of strings of the same length. Given the pattern and text of two multi-track strings, the permuted pattern matching problem is to find the occurrence positions of all permutations of the pattern in the text. In this paper, we propose several algorithms for permuted pattern matching. Our first algorithm, which is based on the Knuth–Morris–Pratt (KMP) algorithm, has a fast theoretical computing time with $O\left(mk\right)$ as the preprocessing time and $O(nklog\sigma )$ as the matching time, where n, m, k, $\sigma$, and $\mathit{occ}$ denote the length of the text, the length of the pattern, the number of strings in the multi-track, the alphabet size, and the number of occurrences of the pattern, respectively. We then improve the KMP-based algorithm by using an automaton, which has a better experimental running time. The next proposed algorithms are based on the Boyer–Moore algorithm and the Horspool algorithm that try to perform pattern matching. These algorithms are the fastest experimental algorithms. Furthermore, we propose an extension of the AC-automaton algorithm that can solve dictionary matching on multi-tracks, which is a task to find multiple multi-track patterns in a multi-track text. Finally, we propose filtering algorithms that can perform permuted pattern matching quickly in practice.

1. Introduction

The pattern matching problem on strings is to find all occurrence positions of a pattern string in a text string. Pattern matching algorithms such as the Knuth–Morris–Pratt (KMP) algorithm [1], the Boyer–Moore algorithm [2], and the Horspool algorithm [3] perform pattern matching quickly by preprocessing the pattern. On the other hand, pattern matching can be accelerated by preprocessing the text into some indexing structure such as suffix trees [4], suffix arrays [5], or position heaps [6].

The permuted pattern matching problem, proposed by Katsura et al. [7,8], is a generalization of the pattern matching problem, where we compare tuples of strings. We call a tuple of strings of the same length a multi-track string. The permuted pattern matching problem is as follows: given two multi-track strings $\mathbb{T}=(T_1,T_2,\dots ,T_k)$ and $\mathbb{P}=(P_1,P_2,\dots ,P_k)$ where $|T_1|=\cdots =|T_k|=n\ge |P_1|=\cdots =|P_k|=m$, to find all positions i such that $(T_1[i:i+m-1],\cdots ,T_k[i:i+m-1])$ is a permutation of $\mathbb{P}$. The problem can be solved by constructing indexing structures from the text such as multi-track suffix trees [7], multi-track position heaps [8], and filtering multi-set trees [9], or by preprocessing the pattern such as the AC-automaton-based algorithm [7].

Multi-track strings can model various types of real data when sequences in the data have the same meaning. For example, data from a three-dimensional accelerometer in a smartphone can be considered a multi-track string. Consider two smartphones with the same position, and rotate one of them several times where each rotation is 90 degrees on the x, y, or z axis. If we perform the same motion on both smartphones, the generated data from three-dimensional accelerometer of one phone is a permutation of the other one. By using permuted pattern matching, we can find occurrences of a pattern on both smartphones without permuting the pattern.

In this paper, we propose several algorithms that solve permuted pattern matching quickly. These algorithms can be classified into three groups. The first group consists of algorithms that are based on the KMP algorithm [1]. This group includes the multi-track KMP, multi-track AC-automaton, and multi-track permuted matching automaton algorithms. The second group consists of algorithms that are based on the Boyer–Moore algorithm [2] and the Horspool algorithm [3]. This group includes the multi-track Boyer–Moore and multi-track Horspool algorithms. The third group consists of filtering algorithms. Moreover, we conduct experiments and show that our algorithms perform permuted pattern matching faster than existing algorithms. The worst case running times of the proposed algorithms and existing algorithms are summarized in

Table 1. Comparison of the algorithms for permuted pattern matching. Multi-track AC-automaton can find occurrences of multiple patterns.

Algorithm	Preprocessing Time	Matching Time
AC-automaton-based [7]	$O(mklog\sigma )$	$O(nklog\sigma )$
Multi-track KMP	$O\left(mk\right)$	$O\left(nk\right)$
MTAC-automaton	$O(dklog\sigma )$	$O(nklog\sigma )$
MT permuted matching automaton	$O(mklog\sigma )$	$O(nklog\sigma )$
MT Boyer–Moore	$O\left(m\right(klog\sigma +\sigma \left)\right)$	$O\left(nk\right(m+log\sigma )+n(k+\sigma \left)\right)$
MT Horspool	$O\left(m\right(klog\sigma +\sigma \left)\right)$	$O\left(nk\right(m+log\sigma )+n(k+\sigma \left)\right)$

, where d is the total length of the patterns and $\sigma$ is the size of the alphabet.

Preliminary versions of this work appeared in [10,11].

2. Notation and Definition on Multi-Track Strings

Let $\Sigma$ be a totally-ordered alphabet and $\sigma =|\Sigma |$ be the size of the alphabet. An element of ${\Sigma }^{*}$ is called a string. For a string $W\in {\Sigma }^{*}$, the length of W is denoted by $\left|W\right|$. The empty string, denoted by $\epsilon$, is a string of length zero. For a string $W\in {\Sigma }^{*}$ of length n, $W\left[i\right]$ denotes the $i^{\mathrm{th}}$ symbol of W, and $W[i:j]=W\left[i\right]W[i+1]\cdots W\left[j\right]$ denotes a substring of W that begins at i and ends at j for $1\le i\le j\le n$. For convenience, we abbreviate $W[1:i]$ to $W[:i]$ and $W[i:n]$ to $W[i:]$; these terms are known as the prefix and the suffix of W, respectively. Moreover, let $W[i:j]=\epsilon$ if $i>j$. The reverse string of W is denoted by $W^R=W\left[n\right]W[n-1]\cdots W\left[2\right]W\left[1\right]$. For two strings, X and Y, $X\prec Y$ denotes that X is lexicographically smaller than Y, and $X⪯Y$ denotes that either $X=Y$ or $X\prec Y$.

A multi-track symbol $\mathbb{C}=(c_1,c_2,\dots ,c_k)$ is a k-tuple of symbols $c_i\in \Sigma$. A multi-track string (or multi-track for short) $\mathbb{W}=(W_1,W_2,\dots ,W_k)$ is a k-tuple of strings $W_i\in {\Sigma }^{*}$ where $|W_1|=|W_2|=\cdots =|W_k|$, and each $W_i$ is called the $i^{\mathrm{th}}$ track of $\mathbb{W}$. The length n of strings in $\mathbb{W}$ is called the length of $\mathbb{W}$ and denoted by ${\left|\mathbb{W}\right|}_{\mathit{len}}$, and the number k of tracks in $\mathbb{W}$ is called the track count of $\mathbb{W}$ and is denoted by ${\left|\mathbb{W}\right|}_{\mathit{num}}$. For a multi-track symbol $\mathbb{C}=(c_1,c_2,\dots ,c_k)$, we define $\mathbb{C}\left[i\right]=c_i$. For a multi-track $\mathbb{W}$ of track count $k={\left|\mathbb{W}\right|}_{\mathit{num}}$, $\mathbb{W}\left[i\right]=(W_1\left[i\right],W_2\left[i\right],\dots ,W_k\left[i\right])$ denotes the $i^{\mathrm{th}}$ multi-track symbol, and $\mathbb{W}\left[i\right]\left[j\right]$ denotes $W_j\left[i\right]$ for $1\le i\le {\left|\mathbb{W}\right|}_{\mathit{len}}$ and $1\le j\le {\left|\mathbb{W}\right|}_{\mathit{num}}$. Moreover, $\mathbb{W}[i:j]=(W_1[i:j],W_2[i:j],\dots ,W_k[i:j])$ denotes a substring of $\mathbb{W}$ that begins at i and ends at j for $1\le i\le j\le {\left|\mathbb{W}\right|}_{\mathit{len}}$. Similarly to the notation for strings, $\mathbb{W}[:i]$ and $\mathbb{W}[i:]$ mean $\mathbb{W}[1:i]$ and $\mathbb{W}[i:|\mathbb{W}{|}_{\mathit{len}}]$, which are called the prefix and the suffix of $\mathbb{W}$, respectively.

Let $\mathbf{r}=(r_1,r_2,\dots ,r_k)$ be a permutation of $(1,2,\dots ,k)$. For a multi-track $\mathbb{W}=(W_1,W_2,\dots ,W_k)$, $\mathbb{W}\langle \mathbf{r}\rangle =\mathbb{W}\langle r_1,r_2,\dots ,r_k\rangle =(W_{r_1},\dots ,W_{r_k})$ is called a permuted multi-track of $\mathbb{W}$. The sorted index $\mathsf{SI}\left(\mathbb{W}\right)$ of a multi-track $\mathbb{W}$ is a permutation $(r_1,\cdots ,r_k)$ such that $W_{r_i}⪯W_{r_{i+1}}$ for any $1\le i<k$, where we assume $r_i<r_{i+1}$ in the case $W_{r_i}=W_{r_{i+1}}$. The sorted multi-track $\mathsf{sort}\left(\mathbb{W}\right)$ is defined as $\mathbb{W}\langle \mathsf{SI}\left(\mathbb{W}\right)\rangle$. The reverse of a multi-track is $\mathbb{W}=(W_1,\cdots ,W_k)$ is ${\mathbb{W}}^R=(W_1^R,\cdots ,W_k^R)$. The sorted index of the reverse multi-track, denoted by $\mathsf{RI}\left(\mathbb{W}\right)$, is a permutation $(r_1,\cdots ,r_k)$ such that $w_{r_i}^R⪯w_{r_{i+1}}^R$ for any $1\le i<k$.

Lemma 1

([7]). Let ${\mathit{SI}}_{\mathbb{W}}$ be a two-dimensional array such that ${\mathit{SI}}_{\mathbb{W}}\left[i\right]=\mathsf{SI}\left(\mathbb{W}[i:]\right)$ for $1\le i\le n$. ${\mathit{SI}}_{\mathbb{W}}$ can be computed in $O\left(nk\right)$ time ffline, where $n={\left|\mathbb{P}\right|}_{\mathit{len}}$ and $k={\left|\mathbb{P}\right|}_{\mathit{num}}$.

Lemma 2.

Let ${\mathit{RI}}_{\mathbb{W}}$ be a two-dimensional array such that ${\mathit{RI}}_{\mathbb{W}}\left[i\right]=\mathsf{RI}\left(\mathbb{W}[i:]\right)$ for $1\le i\le n$. ${\mathit{RI}}_{\mathbb{W}}$ can be computed in $O\left(n\right(k+\sigma \left)\right)$ time nline, where $n={\left|\mathbb{P}\right|}_{\mathit{len}}$ and $k={\left|\mathbb{P}\right|}_{\mathit{num}}$.

Proof. 

Clearly, ${\mathit{RI}}_{\mathbb{W}}$ can be computed in $O\left(n\right(k+\sigma \left)\right)$ by using a radix sort algorithm. □

For two multi-tracks $\mathbb{X}=(X_1,X_2,\dots ,X_k)$ and $\mathbb{Y}=(Y_1,Y_2,\dots ,Y_k)$ of the same length, we say that $\mathbb{X}$permuted-matches$\mathbb{Y}$ if $\mathbb{X}=\mathbb{Y}\langle \mathbf{r}\rangle$ for some permutation $\mathbf{r}$, and it is denoted by $\mathbb{X}\bowtie \mathbb{Y}$. □

Lemma 3

([7]). For two multi-tracks $\mathbb{X}$ and $\mathbb{Y}$, $\mathbb{X}\bowtie \mathbb{Y}$ if and only if $\mathsf{sort}\left(\mathbb{X}\right)=\mathsf{sort}\left(\mathbb{Y}\right)$.

Throughout this paper, we assume that $\mathbb{P}$ is a pattern with ${\left|\mathbb{P}\right|}_{\mathit{num}}=k$ and ${\left|\mathbb{P}\right|}_{\mathit{len}}=m$, and $\mathbb{T}$ is text with ${\left|\mathbb{T}\right|}_{\mathit{num}}=k$ and ${\left|\mathbb{T}\right|}_{\mathit{len}}=n\ge m$. The pattern matching problem on multi-tracks is defined as follows.

Definition 1

(Permuted pattern matching ([7]). Given a multi-track text $\mathbb{T}$ and a multi-track pattern $\mathbb{P}$, compute all positions i that satisfy $\mathbb{P}\bowtie \mathbb{T}[i:i+m-1]$. We call such positions ccurrence position of $\mathbb{P}$ in $\mathbb{T}$.

For example, given a text $\mathbb{T}=\left(\begin{array}{cc}\mathtt{aabaaaaa}& ,\hfill \\ \mathtt{abaabbaa}& ,\hfill \\ \mathtt{baaababa}& \hfill \end{array}\right)$ and a pattern $\mathbb{P}=\left(\begin{array}{cc}\mathtt{aba}& ,\hfill \\ \mathtt{baa}& ,\hfill \\ \mathtt{aaa}& \hfill \end{array}\right)$, we can see that the pattern $\mathbb{P}$ matches $\mathbb{T}$ at two because $\mathbb{T}[2:4]=\mathbb{P}$. Moreover, the pattern $\mathbb{P}$ permuted-matches $\mathbb{T}$ at six, since $\mathbb{P}\langle 3,2,1\rangle =\left(\begin{array}{cc}\mathtt{aaa}& ,\hfill \\ \mathtt{baa}& ,\hfill \\ \mathtt{aba}& \hfill \end{array}\right)=\mathbb{T}[6:8]$. Therefore, we should output two and six in this case.

We remark that Katsura et al. [7] defined a more general problem called the sub-permuted pattern matching, where we have ${\left|\mathbb{T}\right|}_{\mathit{num}}\ge {\left|\mathbb{P}\right|}_{\mathit{num}}$, and our task is to find a partial permutation $(r_1,\cdots ,r_{{\left|\mathbb{P}\right|}_{\mathit{num}}})$ of $(1,\cdots ,|\mathbb{T}{|}_{\mathit{num}})$ and a position i for which $\mathbb{P}\bowtie \mathbb{T}\langle r_1,\cdots ,r_{{\left|\mathbb{P}\right|}_{\mathit{num}}}\rangle [i:i+m-1]$ holds. However, in this paper, we only consider the case ${\left|\mathbb{T}\right|}_{\mathit{num}}={\left|\mathbb{P}\right|}_{\mathit{num}}$, which was called full-permuted pattern matching in [7].

3. KMP-Based Permuted Pattern Matching Algorithms

In this section, we propose three algorithms for permuted pattern matching based on the KMP algorithm. In Section 3.1, we introduce our first algorithm, the multi-track KMP algorithm (MTKMP algorithm) which uses the border array of a multi-track pattern. We remark that this algorithm is a variant of the generalized KMP algorithm proposed by Matsuoka et al. [12]. They showed that the KMP algorithm can be applied to string classes that satisfy some equality and border properties. In this paper, we show some properties of multi-track strings so that the KMP algorithm can be applied to multi-track strings and give the exact computation time of the algorithm.

In Section 3.2, we extend it to the multi-track AC-automaton algorithm, which can perform dictionary matching on multi-tracks. Last, in Section 3.3, we introduce another extension of the MTKMP algorithm, the permuted matching automaton algorithm, which can perform permuted pattern matching faster than the MTKMP algorithm.

3.1. Multi-Track KMP Algorithm

Similar to the original KMP algorithms, the multi-track KMP algorithm uses multi-track border arrays to compute the shift amount when the algorithm finds a mismatch. First, we define borders for multi track strings.

Definition 2

(Borders of multi-tracks). A orde of a multi-track $\mathbb{P}$ is any multi-track that permuted-matches with a prefix and a suffix of $\mathbb{P}$. Moreover, a border $\mathbb{B}$ of $\mathbb{P}$ is called rope if $\mathbb{B}$ $\mathbb{P}$.

We can easily confirm the following lemma.

Lemma 4.

For any two borders ${\mathbb{B}}_1$ and ${\mathbb{B}}_2$ of $\mathbb{P}$, if $|{\mathbb{B}}_1{|}_{\mathit{len}}<{\left|{\mathbb{B}}_2\right|}_{\mathit{len}}$, then ${\mathbb{B}}_1$ is a border of ${\mathbb{B}}_2$.

Let $\mathbb{T}[i:i+j]\bowtie \mathbb{P}[1:j+1]$ for some i and j. If $\mathbb{T}[i+x:i+x+m-1]\bowtie \mathbb{P}[1:m]$ for some $x\le j$, then $\mathbb{T}[i:i+(j-x\left)\right]\bowtie \mathbb{P}[1:(j-x)+1]$ and $\mathbb{T}[i+x:i+j]\bowtie \mathbb{P}[1:(j-x)+1]$ hold, i.e., $\mathbb{P}[1:(j-x)+1]$ is a proper border of $\mathbb{P}[1:j+1]$. Therefore, if $\mathbb{T}[i:i+j]\bowtie \mathbb{P}[1:j+1]$ and $\mathbb{T}[i:i+j]$ $\mathbb{P}[1:j+1]$, we can safely shift $\mathbb{P}$ by x, where $(j-x+1)$ is the length of the longest proper border of $\mathbb{P}[1:j+1]$. We store the length of the longest proper border of $\mathbb{P}[1:j+1]$ for $1\le j\le m$ as the border array of $\mathbb{P}$.

Definition 3

(Multi-track border array). Given a multi-track $\mathbb{P}$ of ${\left|\mathbb{P}\right|}_{\mathit{len}}=m$, he border arra ${\mathit{Border}}_{\mathbb{P}}$ of $\mathbb{P}$ is an array of length $m+1$, where the $i^{\mathrm{th}}$ element of ${\mathit{Border}}_{\mathbb{P}}$ is the length of the longest proper border of $\mathbb{P}[1:i]$. Formally,

$${\mathit{Border}}_{\mathbb{P}}\left[i\right]=max\{j\mid \mathbb{P}[1:j]\bowtie \mathbb{P}[i-j+1:i],0\le j<i\}.$$

(1)

For algorithmic purpose, we define ${\mathit{Border}}_{\mathbb{P}}\left[0\right]=-1$. Algorithm 1 constructs the multi-track border array of an input $\mathbb{P}$.

Lemma 5.

Given a multi-track $\mathbb{P}$ of ${\left|\mathbb{P}\right|}_{\mathit{len}}=m$ and ${\left|\mathbb{P}\right|}_{\mathit{num}}=k$, Algorithm 1 constructs the border array of $\mathbb{P}$ in $O\left(mk\right)$ time.

Proof. 

First, we show the correctness of the algorithm by induction. Assume we have computed the longest proper border of $\mathbb{P}[:j]$ and stored it in $\mathit{Border}\left[j\right]$ for $1\le j\le i$. Let $\mathbb{P}[:b]$ be the longest proper border of $\mathbb{P}[:i+1]$. Clearly, $\mathbb{P}[:b-1]$ is a border of $\mathbb{P}[:i]$. Using Lemma 4, we can find $b-1$ by finding $max\{j\mid \mathbb{P}[:j\left]\mathrm{is}\mathrm{a}\mathrm{proper}\mathrm{border}\mathrm{of}\mathbb{P}\right[:i\left]\mathrm{and}\mathbb{P}\right[:j+1]\bowtie \mathbb{P}[i-j+1:i+1\left]\right\}$. Since $\mathit{Border}\left[j\right]$ is the longest proper border of $\mathbb{P}[:j]$, the algorithm can find $b-1$ by updating $j\leftarrow \mathit{Border}\left[j\right]$ from $j=i$ until $\mathbb{P}[:\mathit{Border}[j]+1]\bowtie \mathbb{P}[i-\mathit{Border}[j]+1:i+1]$ holds. Therefore, Algorithm 1 computes the border array of $\mathbb{P}$ correctly.

Next, we show the computation time of the algorithm. Using Lemma 1, $\mathit{SI}$ can be computed in $O\left(mk\right)$. Both while loops are called $O\left(m\right)$ times at most, since $i-j\le i\le m+1$, and the value of i always increases each time the outer loop is called, while the value of $i-j$ always increases each time the inner loop is called. Each comparison of $\mathbb{P}\left[j\right]\langle \mathsf{SI}\left(\mathbb{P}\right[1:\left]\right)\rangle$ and $\mathbb{P}\left[i\right]\langle \mathsf{SI}\left(\mathbb{P}\right[i-j:\left]\right)\rangle$ consumes $O\left(k\right)$ time; hence, Algorithm 1 runs in $O\left(mk\right)$ time. □

Algorithm 2 shows the pseudocode of the MTKMPalgorithm. The MTKMP algorithm performs permuted pattern matching from left to right of the pattern and the text. The sorted pattern ${\mathbb{P}}_{\mathit{sort}}$ and the array $\mathit{SI}$ save the sorted indices of suffixes of text used to perform permuted-matching between the pattern and a substring of the text. If symbols on the text and the pattern are mismatched, we shift the matching position of the pattern using $\mathit{Border}$. If the pattern matches a substring of the text, then the MTKMP algorithm outputs the occurrence position at the text and shifts the pattern according to $\mathit{Border}$.

Algorithm 1: Multi-track border array construction algorithm.

Algorithm 2: The multi-track KMP algorithm.

Theorem 1.

Given a text $\mathbb{T}$ and a pattern $\mathbb{P}$, the MTKMP algorithm computes all occurrence positions of $\mathbb{P}$ in $\mathbb{T}$ in $O(nk+mk)$ time.

Proof. 

According to the above arguments, we can shift $\mathbb{P}$ by x, where $(j-x+1)$ is the length of the longest proper border of $\mathbb{P}[1:j+1]$ if $\mathbb{T}[i:i+j]\bowtie \mathbb{P}[1:j+1]$ and $\mathbb{T}[i:i+j]$ $\mathbb{P}[1:j+1]$. Since $\mathit{Border}\left[i\right]$ is the longest proper border of $\mathbb{P}[:i]$, the algorithm finds the occurrence position of $\mathbb{P}$ in $\mathbb{T}$ correctly.

Using Lemma 1, $\mathit{SI}$ can be computed in $O\left(nk\right)$. From Lemma 5, constructMTBorderArray $\mathbb{P}$ runs in $O\left(mk\right)$. Both while loops are called $O\left(n\right)$ times at most, since $i-j\le i\le n+1$, and the value of i always increases each time the outer loop is called, while the value of $i-j$ always increases each time the inner loop is called. Each comparison of $\mathbb{P}\left[j\right]\langle \mathsf{SI}\left(\mathbb{P}\right[1:\left]\right)\rangle$ and $\mathbb{T}\left[i\right]\langle \mathsf{SI}\left(\mathbb{T}\right[i-j:\left]\right)\rangle$ consumes $O\left(k\right)$ time. Hence, Algorithm 2 runs in $O(nk+mk)$ time. □

3.2. Multi-Track AC-Automaton

In this subsection, we introduce a data structure called a multi-track AC-automaton that can perform dictionary matching on multi-tracks, namely permuted dictionary matching. Let $D=\{{\mathbb{P}}_1,{\mathbb{P}}_2,\dots ,{\mathbb{P}}_r\}$ be a set of patterns of the same track count k, called a dictionary, and let $d={\sum }_{i=1}^r{m}_i$ be the total length of the patterns in D, where $m_i={\left|{\mathbb{P}}_i\right|}_{\mathit{len}}$. The multi-track AC-automaton of D, denoted by $\mathsf{MTAC}\left(D\right)$, consists of a set of states and three functions: goto, failure, and output functions. Figure 1 shows an example of $\mathsf{MTAC}\left(D\right)$.

For a dictionary D, the states of $\mathsf{MTAC}\left(D\right)$ are $\mathcal{S}=\{\mathsf{sort}\left({\mathbb{P}}_i\right)[:j]\mid {\mathbb{P}}_i\in D,0\le j\le m_i\}$. Each state corresponds to a prefix of $\mathsf{sort}\left({\mathbb{P}}_i\right)$ for some ${\mathbb{P}}_i\in D$. Unlike the original AC-automaton, the multi-track AC-automaton uses a multi-track symbol, instead of a single symbol, to define the goto function. The goto, failure, and output functions of $\mathsf{MTAC}\left(D\right)$ are defined as follows.

Definition 4

(Goto function). We define the goto function δ of $\mathsf{MTAC}\left(D\right)$ by $\delta \left(\mathsf{sort}\left({\mathbb{P}}_i\right)[:j]\right),\mathbb{C})=\mathsf{sort}\left({\mathbb{P}}_i\right)[:j+1]$ iff $\mathbb{C}=\mathsf{sort}\left({\mathbb{P}}_i\right)[j+1]$ for a state $\mathsf{sort}\left({\mathbb{P}}_i\right)[:j]$ and a multi-track symbol $\mathbb{C}$.

Definition 5

(Failure function). The failure link of a state $\mathsf{sort}\left({\mathbb{P}}_i\right)[:j]$ is defined as $\mathsf{flink}\left(\mathsf{sort}\left({\mathbb{P}}_i\right)[:j]\right)=\mathsf{sort}\left({\mathbb{P}}_i[l:j]\right)$, where ${\mathbb{P}}_i[l:j]$ is the longest proper suffix of ${\mathbb{P}}_i[:j]$ such that ${\mathbb{P}}_i[l:j]$ permuted-matches a prefix of some pattern in D.

Definition 6

(Output function).The output $\mathsf{output}\left({\mathbb{P}}_i[:j]\right)$ of a state $\mathsf{sort}\left({\mathbb{P}}_i\right)[:j]$ is the set of patterns that permuted-matches ${\mathbb{P}}_i[l:j]$ for some $1\le l\le j$.

Next, we explain how to construct $\mathsf{MTAC}\left(D\right)$. We use multi-track symbol tries to implement the goto function.

Definition 7

(Multi-track symbol trie). Let $\mathcal{C}=\{{\mathbb{C}}_1,...,{\mathbb{C}}_z\}$ be a set of multi-track symbols. The multi-track symbol trie of $\mathcal{C}$ is the trie for the set of strings $\{{\mathbb{C}}_1\left[1\right]{\mathbb{C}}_1\left[2\right]\cdots {\mathbb{C}}_1\left[\right|{\mathbb{C}}_1{|}_{\mathit{num}}],\cdots ,{\mathbb{C}}_z\left[1\right]{\mathbb{C}}_z\left[2\right]\cdots {\mathbb{C}}_z\left[\right|{\mathbb{C}}_z{|}_{\mathit{num}}\left]\right\}$.

For a state $s\in \mathcal{S}$, we use the multi-track symbol trie of a set $\{\mathbb{C}\mid \delta (s,\mathbb{C})\ne \mathsf{NULL}\}$ and each leaf of multi-track symbol tries labeled by $\delta (s,\mathbb{C})$. Since a child of a node in multi-track symbol tries can be searched in $O(log\sigma )$ time, $\delta (s,\mathbb{C})$ can be computed in $O(klog\sigma )$ time. The goto function $\delta$ can be constructed by using Algorithm 3.

Algorithm 3: Multi-track AC-automaton goto function construction algorithm.

Lemma 6.

Algorithm 3 constructs the goto function of the multi-track AC-automaton of a dictionary $D=\{{\mathbb{P}}_1,{\mathbb{P}}_2,\dots ,{\mathbb{P}}_r\}$ in $O(dklog\sigma )$ time.

Proof. 

The goto function $\delta (s,\mathbb{C})$ is executed $O\left(d\right)$ times, and $\delta (s,\mathbb{C})$ can be computed in $O(klog\sigma )$ time. □

After constructing the goto function, we can construct the failure function of $\mathsf{MTAC}\left(D\right)$. Algorithm 4 shows a construction algorithm for the failure function of a multi-track AC-automaton. In order to simplify the construction algorithm, we use a special state that reads any multi-track symbol to get to the root state.

Algorithm 4: Multi-track AC-automaton failure function construction algorithm.

Lemma 7.

Algorithm 4 constructs the failure function of the multi-track AC-automaton of a dictionary $D=\{{\mathbb{P}}_1,{\mathbb{P}}_2,\dots ,{\mathbb{P}}_r\}$ in $O(dklog\sigma )$ time.

Proof. 

We can bound the running time of Algorithm 4 by counting the number of executions of $\delta (s,\mathbb{C})$. For each pattern ${\mathbb{P}}_i$, let $s_{i,j}$ be a state such that $s_{i,j}=\delta (\mathit{root},{\mathbb{P}}_i[:j])$ for $1\le j\le m_i$. Let $f_{i,j}$ be the number of executions of $\mathsf{flink}$ when finding $\mathsf{flink}\left(s_{i,j}\right)$. The maximum value of $f_{i,j}$ is bounded by $\mathsf{depth}\left(\mathsf{flink}\left(s_{i,j-1}\right)\right)+1$. Because the depth of $\mathsf{flink}\left(s_{i,j}\right)$ is, at most, $\mathsf{depth}\left(\mathsf{flink}\left(s_{i,j-1}\right)\right)-f_{i,j}+1$, we get $f_{i,j}\le \mathsf{depth}\left(\mathsf{flink}\left(s_{i,j-2}\right)\right)-f_{i,j-1}+2$ recursively. By solving this formula, we get ${\sum }_{j=1}^{m_i}{f}_{i,j}\le 2m_i$ and ${\sum }_{i=1}^r{\sum }_{j=1}^{m_i}{f}_{i,j}\le {\sum }_{i=1}^{r}2m_i=2d$. Moreover, each $\delta (s,\mathbb{C})$ is executed in $O(klog\sigma )$ time. □

Last, by using the goto and failure functions, Algorithm 4 constructs the output function of a multi-track AC-automaton.

Lemma 8.

Algorithm 5 constructs the output function of the multi-track AC-automaton of a dictionary $D=\{{\mathbb{P}}_1,{\mathbb{P}}_2,\dots ,{\mathbb{P}}_r\}$ in $O(dklog\sigma )$ time.

Proof. 

Updating the output function can be performed in $O\left(1\right)$ time by using lists to save the output function and updating it by concatenating the list (see [13]). The proof is similar to the proofs of Lemmas 3 and 4. □

From Lemmas 6–8, we get the following theorem.

Theorem 2.

The multi-track AC-automaton of a dictionary $D=\{{\mathbb{P}}_1,{\mathbb{P}}_2,\dots ,{\mathbb{P}}_r\}$ can be constructed in $O(dklog\sigma )$ time.

Algorithm 5: Multi-track AC-automaton output function construction algorithm.

By using the multi-track AC-automaton of D, we can perform permuted dictionary matching on a text $\mathbb{T}$, as shown in Algorithm 6. Let $\mathit{v}$ be the current state of the multi-track AC-automaton. For each position i on $\mathbb{T}$, Algorithm 6 uses the sorted index of $\mathbb{T}[i-\mathsf{depth}(\mathit{v}):]$ to determine the permutation of $\mathbb{T}\left[i\right]$ that is used in the goto function.

Algorithm 6: Permuted dictionary matching algorithm by using multi-track AC-automaton.

Theorem 3.

Permuted dictionary matching on a multi-track text $\mathbb{T}$ can be performed in $O(nklog\sigma )$ time by using the multi-track AC-automaton of D.

Proof. 

The running time of Algorithm 6 can be evaluated by counting the number of executions of $\delta (s,\mathbb{C})$. First, for each i, $\delta (s,\mathbb{C})$ is executed at least once on the $\mathit{v}$ transition. Next, $\delta (s,\mathbb{C})$ is executed to check whether the transition is $\mathsf{NULL}$ or not. In this case, the number of executions of $\delta (s,\mathbb{C})$ is the same as that of $\mathsf{flink}$. The latter is, at most, n, because whenever $\delta (s,\mathbb{C})$ is executed, the depth of $\mathit{v}$ is increased by one, and whenever $\mathsf{flink}$ is executed, the depth of $\mathit{v}$ is decreased by at least one. Therefore, the number of executions of $\delta (s,\mathbb{C})$ is $O\left(n\right)$. □

3.3. Multi-Track Permuted Matching Automaton

In this subsection, we describe a data structure called a multi-track permuted matching automaton that can perform permuted pattern matching on a multi-track text $\mathbb{T}$ online, by preprocessing a multi-track pattern $\mathbb{P}$. For a multi-track pattern $\mathbb{P}=(P_1,P_2,...,P_k)$, the multi-track permuted matching automaton of $\mathbb{P}$, denoted by $\mathsf{MTPMA}\left(\mathbb{P}\right)$, consists of a set of states and two functions, goto and failure functions. In addition, each state of the multi-track permuted matching automaton has a weight in order to determine whether $\mathsf{flink}$ should be executed or not. Figure 2 shows an example of a multi-track permuted matching automaton.

Let $\mathcal{S}$ be the set of states of $\mathsf{MTPMA}\left(\mathbb{P}\right)$. Each state of $\mathsf{MTPMA}\left(\mathbb{P}\right)$ corresponds to a prefix of $P_i$, i.e., $\mathcal{S}=\{P_i[:j]\mid 1\le i\le k,0\le j\le m\}$. Each state s has a weight, which is the number of tracks containing s as a prefix. Moreover, a state s is called an accept state if $s=P_i$ for some i. The goto and failure functions of $\mathsf{MTPMA}\left(\mathbb{P}\right)$ are defined as follows.

Definition 8

(Goto function).We define the goto function δ as $\delta (P_i[:j],c)=P_i[:j+1]$ iff $c=P_i[j+1]$ for each state $P_i[:j]$ and symbol c.

Definition 9

(Failure function). Let $S_j=\{P_i[:j]\mid 1\le i\le k\}$ be the set of states whose depth is j. The failure link of the state is $\mathsf{flink}\left(P_i[:j]\right)=P_x[:y]\in S_y$ such that $P_x[:y]$ is a proper suffix of $P_i[:j]$ and $\mathbb{P}[:y]$ is the longest prefix of $\mathbb{P}$ that permuted-matches with a proper suffix of $\mathbb{P}[:j]$. The latter condition is similar to that of the multi-track KMP algorithm.

Next, we explain how to construct $\mathsf{MTPMA}\left(\mathbb{P}\right)$. Algorithm 7 constructs the goto function of a multi-track permuted matching automaton. We add a weight on each state each time we visit the state when reading each track.

Lemma 9.

Algorithm 7 constructs the goto function of $\mathsf{MTPMA}\left(\mathbb{P}\right)$ in $O(mklog\sigma )$ time.

Proof. 

For each track, the number of executions of $\delta (s,c)$ is m, and there are k tracks in a pattern $\mathbb{P}$. Moreover, $\delta (s,c)$ can be executed in $O(log\sigma )$ time. □

After constructing the goto function, Algorithm 8 constructs the failure function of $\mathsf{MTPMA}\left(\mathbb{P}\right)$. For each state s, we use a multi-track border array to determine the depth of $\mathsf{flink}\left(s\right)$.

Lemma 10.

Algorithm 8 constructs the failure function of $\mathbb{P}$ in $O(mklog\sigma )$ time.

Proof. 

Similarly to the proof of Theorem 7, the failure and goto functions are executed $O\left(mk\right)$ times. Moreover, the execution time of the failure function is $O\left(1\right)$, and that of the goto function is $O(log\sigma )$. □

From Lemmas 9 and 10 we get the following theorem.

Theorem 4.

The multi-track permuted matching automaton of a pattern $\mathbb{P}$ can be constructed in $O(mklog\sigma )$ time.

Finally, by using $\mathsf{MTPMA}\left(\mathbb{P}\right)$, Algorithm 9 can perform permuted pattern matching on a multi-track text $\mathbb{T}$. Algorithm 9 uses k pointers $\mathit{activeStates}$ to point to the current states. Note that all $\mathit{activeStates}$ always have the same depth. Algorithm 9 uses two conditions to determine whether it should execute the failure function or not. The first condition is when it cannot find the goto transition, and the second condition is when the number of state pointers in the state is more than the weight of the state. If any of the $\mathit{activeStates}$ fail, then all of the $\mathit{activeStates}$ execute the failure function, otherwise $\mathit{activeStates}$ executes the goto function.

Theorem 5.

By using $\mathsf{MTPMA}\left(\mathbb{P}\right)$, Algorithm 9 performs permuted pattern matching on a multi-track string $\mathbb{T}$ in $O(nklog\sigma )$ time.

Proof. 

Similarly to the proof of Theorem 3, the number of executions of the failure and goto function is $O\left(nk\right)$. Since the execution time of the failure function is $O\left(1\right)$ and the goto function is $O(log\sigma )$, Algorithm 9 runs in $O(nklog\sigma )$ time. □

Algorithm 7: Multi-track permuted matching automaton goto function construction algorithm.

Algorithm 8: Multi-track permuted matching automaton failure function construction algorithm.

Algorithm 9: Multi-track permuted matching automaton matching algorithm.

4. Multi-Track Boyer–Moore and Horspool Algorithms

In this section, we propose two permuted pattern matching algorithms that are based on the Boyer–Moore algorithm and the Horspool algorithm, which we call MT-BM and MT-H , respectively. The original Boyer–Moore algorithm uses two functions $\mathsf{GoodSuf}$ (good suffixes) and $\mathsf{BadSym}$ (bad symbols), and the Horspool algorithm only uses $\mathsf{BadSym}$ to determine how much the position of a substring to compare should be shifted when a mismatch is found between the input patten and the substring of the text. For multi-track strings, we use a permuted match to define $\mathsf{GoodSuf}$ instead of a complete match, and we use sorted multi-track symbols for $\mathsf{BadSym}$ instead of symbols. Formally, those functions are defined as follows on multi-tracks.

Definition 10

(Good suffixes function). For a multi-track $\mathbb{P}$ of length ${\left|\mathbb{P}\right|}_{\mathit{len}}=m$, let $A\left[i\right]=\{0<s<i\mid \mathbb{P}[i-s+1:m-s]\bowtie \mathbb{P}[i+1:m],\mathbb{P}[i-s:m-s]$ $\mathbb{P}[i:m]\}$ and $B\left[i\right]=\{i\le s<m\mid \mathbb{P}[1:m-s]\bowtie \mathbb{P}[s+1:m\left]\right\}$. The good suffixes function is defined as ${\mathsf{GoodSuf}}_{\mathbb{P}}\left[m\right]=1$ and ${\mathsf{GoodSuf}}_{\mathbb{P}}\left[i\right]=minA\left[i\right]\cup B\left[i\right]\cup \left\{m\right\}$ for $0\le i<m$.

Definition 11

(Bad symbols function). For a multi-track $\mathbb{P}$ of length ${\left|\mathbb{P}\right|}_{\mathit{len}}=m$ and a multi-track symbol $\mathbb{C}$, ${\mathsf{BadSym}}_{\mathbb{P}}\left(\mathbb{C}\right)$ is the first occurrence position of $\mathsf{sort}\left(\mathbb{C}\right)$ in ${\mathbb{P}}^R[2:]$. The function ${\mathsf{BadSym}}_{\mathbb{P}}\left(\mathbb{C}\right)$ returns m if there is no occurrence of $\mathsf{sort}\left(\mathbb{C}\right)$ in ${\mathbb{P}}^R[2:]$.

In the implementation, $\mathsf{GoodSuf}$ is computed by using an array, while $\mathsf{BadSym}$ can be computed by using a trie of the multi-track symbols. We perform permuted-match instead of exact matching when computing $\mathsf{GoodSuf}$. We also use another array $\mathsf{suf}$ to compute $\mathsf{GoodSuf}$.

Definition 12

(Suffixes). For a multi-track $\mathbb{P}$ of length ${\left|\mathbb{P}\right|}_{\mathit{len}}=m$, ${\mathsf{suf}}_{\mathbb{P}}\left[i\right]$ is the maximum value of l such that $\mathbb{P}[i-l+1:i]\bowtie \mathbb{P}[m-l+1:m]$ for $1\le i\le m$.

Algorithm 10 shows how to construct $\mathsf{GoodSuf}$ and $\mathsf{BadSym}$. The array $\mathsf{GoodSuf}$ is computed by $\mathsf{ComputeGoodSuf}$, which uses array $\mathsf{suf}$ computed by $\mathsf{ComputeSuf}$. Note that we compute $\mathsf{RI}\left(\mathbb{P}\right[:i\left]\right)$ at the beginning (Lines 2 and 26) of the algorithm and will not recompute them when we use the values later.

Algorithm 10: MT-BM and MT-H preprocessing functions.

Lemma 11.

The function $\mathsf{ComputeSuf}$ computes the array $\mathsf{suf}$ in $O\left(m\right(k+\sigma \left)\right)$ time.

Proof. 

First, $\mathit{RI}$ can be computed in $O\left(m\right(k+\sigma \left)\right)$ time by using radix sort. The for loop is executed $m-1$ times, and the while loop in Line 11 is executed m times at most through the whole run, because k is always reduced in each loop. A comparison of two multi-track symbols of the pattern that was executed in each loop can be computed in $O\left(k\right)$ time. □

Lemma 12.

The function $\mathsf{ComputeGoodSuf}$ computes $\mathsf{GoodSuf}$ in $O\left(m\right)$ time.

Proof. 

All the for loops are executed m times at most. The while loop is executed m times at most through the whole execution of the algorithm, since j is always increased and does not exceed m. □

Lemma 13.

The function $\mathsf{ComputeBadSym}$ computes $\mathsf{BadSym}$ in $O\left(m\right(klog\sigma +\sigma \left)\right)$ time.

Proof. 

$\mathit{RI}$ can be computed in $O\left(m\right(k+\sigma \left)\right)$ time by using radix sort. Each edge in the trie of $\mathsf{BadSym}$ can be accessed in $O(log\sigma )$ time by using a binary search. Since the depth of the trie is, at most, k, each $\mathsf{BadSym}\left(\mathbb{P}\right[i\left]\right)$ for $1\le i\le m$ can be added and accessed in $O(klog\sigma )$ time. □

By using both ${\mathsf{GoodSuf}}_{\mathbb{P}}$ and ${\mathsf{BadSym}}_{\mathbb{P}}$, MT-BM outputs the positions of the text that are permuted-matched with the pattern. The matching algorithm of MT-BM is shown in Algorithm 11.

Algorithm 11: Multi-track Boyer–Moore algorithm.

Theorem 6.

Given a multi-track text $\mathbb{T}$ and a pattern $\mathbb{P}$, MT-BM outputs all occurrence positions of $\mathbb{P}$ in $\mathbb{T}$ in $O\left(nk\right(m+log\sigma )+n(k+\sigma \left)\right)$ time with $O\left(m\right(klog\sigma +\sigma \left)\right)$ preprocessing time.

Proof. 

From Lemmas 11–13, Algorithm 11 needs $O\left(m\right(klog\sigma +\sigma \left)\right)$ time for preprocessing. Next, $\mathit{RI}$ can be computed in $O\left(n\right(k+\sigma \left)\right)$ time by using radix sort. In the outer while loop starting at Line 7, the value of j is increased by at least one, so the loop is executed $n-m+2$ times at most. In each execution of the outer loop, the inner while loop is executed m times at most, where multi-track symbols of the pattern and the text can be compared in $O\left(k\right)$ time. $\mathsf{BadSym}$ can be accessed in $O(klog\sigma )$ time, and $\mathsf{GoodSuf}$ can be executed in $O\left(1\right)$ time. □

Similarly to the original Horspool algorithm, the multi-track Horspool algorithm (MT-H) uses $\mathsf{BadSym}$ to shift the pattern.

Theorem 7.

Given a multi-track text $\mathbb{T}$ and a pattern $\mathbb{P}$, MT-H outputs all occurrence positions of $\mathbb{P}$ in $\mathbb{T}$ in $O\left(nk\right(m+log\sigma )+n(k+\sigma \left)\right)$ time with $O\left(m\right(klog\sigma +\sigma \left)\right)$ preprocessing time.

Proof. 

Similar to the proof of Theorem 6. □

Boyer–Moore and Horspool Matching Algorithms with Track Trie

The two algorithms presented in the previous subsections determine if two multi-tracks permuted-match by sorting them. In this subsection, we present another idea for this task using a data structure called a track trie. The track trie $\mathsf{TrackTrie}\left(\mathbb{P}\right)$ of a multi-track $\mathbb{P}$ stores all the reversed strings of the tracks of $\mathbb{P}$, that is $\{P_1^R,P_2^R,\dots ,P_k^R\}$. Figure 3a shows the track trie of a multi-track pattern $\mathbb{P}=(\mathtt{bbaba},\mathtt{abbba},\mathtt{aaabb})$.

Algorithm 12 is the construction algorithm of $\mathsf{TrackTrie}\left(\mathbb{P}\right)$. For a node s of $\mathsf{TrackTrie}\left(\mathbb{P}\right)$ and a symbol $c\in \Sigma$, the goto function $\delta (s,c)$ returns the child of s that has an edge labeled c. We naturally extend it to the domain ${\Sigma }^{*}$ by $\delta (s,\epsilon )=s$ and $\delta (s,aw)=\delta \left(\delta \right(s,a),w)$ for any $a\in \Sigma$ and $w\in {\Sigma }^{*}$. We also associate a weight with each node to find mismatch on a text, as we explain later.

Algorithm 12: Track trie construction algorithm.

Theorem 8.

Algorithm 12 constructs $\mathsf{TrackTrie}\left(\mathbb{P}\right)$ in $O(mklog\sigma )$ time.

Proof. 

The function $\mathit{goto}$ can be calculated in $O(log\sigma )$ time by binary search. On each execution of the inner for loop (Line 6), Algorithm 12 executes $\mathit{goto}$ to check the child nodes of $\mathit{activeNode}$. If there is no node with an edge labeled $\mathbb{P}\left[j\right]\left[i\right]$, then a new node is constructed, which can be done in $O\left(1\right)$ time. On the other hand, if there is a node with an edge labeled $\mathbb{P}\left[j\right]\left[i\right]$, Algorithm 12 accesses the child node and then increases its weight by one. The total number of iterations of the inner loop is $mk$. □

For a given multi-track text $\mathbb{T}$ and a position i, Algorithm 13 finds a mismatch position in two cases: (1) when a track cannot find its $\mathit{goto}$ destination, and (2) when the number of tracks that have the same string w is more than the weight of the node that represents the string $\delta (root,w)$. Those mismatch conditions are illustrated in Figure 3b,c, respectively. Figure 3b shows that the track trie cannot find a transition for the second symbol $\mathtt{b}$ of the third track. On the other hand, Figure 3c shows that ${\mathbb{T}}_2[3:]$ has two “$\mathtt{bba}$” on its track; however, the $\mathbb{P}[3:]$ has only one “$\mathtt{bba}$” on its track, i.e., the node that represents “$\mathtt{bba}$” has one on its weight.

Algorithm 13: Track trie matching algorithm.

Theorem 9.

Given a multi-track text $\mathbb{T}$ and a position j, Algorithm 13 finds a mismatch position in the pattern in $O(mklog\sigma )$ time.

Proof. 

For each position $i+j$ on the text, Algorithm 13 executes $\mathit{goto}$ to check whether $\mathit{activeNodes}\left[l\right]$ has a child node with an edge labeled $\mathbb{T}[i+j]\left[l\right]$ for $1\le l\le k$. If there is no child node with an edge labeled $\mathbb{T}[i+j]\left[l\right]$, then Algorithm 13 considers it a mismatch and returns the mismatch position. On the other hand, if there is such a child node, Algorithm 13 updates $\mathit{activeNodes}\left[l\right]$ to the child node and then checks whether the number of tracks of $\mathbb{T}[i+j:]$ that contain $\mathbb{T}[i+j:i+m]\left[l\right]$ as a prefix is more than the weight of the child node. If the number of tracks exceeds the weight, then Algorithm 13 treats it as mismatch and returns the mismatch position. The total number of iterations of the inner loop is, at most, $mk$. □

Although the worst case time complexity remains the same, by using track trie, both MT-BM and MT-H can match the pattern to the text faster, because we do not need to compute the reverse-sorted index of the text. First, we construct the track trie of the pattern by using $\mathsf{constructTrackTrie}\left(\mathbb{P}\right)$. Then, we replace Line 10 of Algorithm 11 by $\mathsf{matchTrackTrie}(\mathbb{T},j)$ to find a mismatch position.

5. Filtering Algorithm on a Multi-Track String

In this section, we propose filtering algorithms for permuted pattern matching. The filtering algorithm uses a function to transform a multi-track string into another sequence. Then, the algorithm implements a pattern matching algorithm on the transformed pattern and text to get candidate positions where the pattern may permuted-match. Finally, every candidate position is checked for whether the pattern is permuted-matched in each position or not.

The filtering algorithm uses a function $\varphi$ that inputs a multi-track $\mathbb{W}$ and outputs a sequence of length ${\left|\mathbb{W}\right|}_{\mathit{len}}$. The function $\varphi$ must have a false-positive property, that is, for two multi-tracks $\mathbb{X}$ and $\mathbb{Y}$, if $\mathbb{X}\bowtie \mathbb{Y}$, then $\varphi \left(\mathbb{X}\right)=\varphi \left(\mathbb{Y}\right)$. We can use any hash function such as the Karp–Rabin fingerprint [14] and locality-sensitive hashing [15]. We describe the filtering algorithm by using a simple function $\beta$ that is defined as follows.

Definition 13

(Bucket function β). For $\mathbb{W}=(W_1,W_2,\dots ,W_k)$, $\beta \left(\mathbb{W}\right)=(B_1,B_2,\dots ,B_{\sigma })$ such that $B_j\left[i\right]$ is the number of the $j^{\mathrm{th}}$ symbol in $\mathbb{Z}\left[i\right]$.

For example, for a multi-track $\mathbb{W}=(\mathtt{abab},\mathtt{bbac},\mathtt{aabb},\mathtt{cabb},\mathtt{abba})$, $\beta \left(\mathbb{W}\right)$ is as follows,

$$\left(\begin{array}{cccc}\mathtt{a}& \mathtt{b}& \mathtt{a}& \mathtt{b}\\ \mathtt{b}& \mathtt{b}& \mathtt{a}& \mathtt{c}\\ \mathtt{a}& \mathtt{a}& \mathtt{b}& \mathtt{b}\\ \mathtt{c}& \mathtt{a}& \mathtt{b}& \mathtt{b}\\ \mathtt{a}& \mathtt{b}& \mathtt{b}& \mathtt{a}\end{array}\right),\beta \left(\mathbb{Z}\right)=\left(\begin{array}{cccc}3& 2& 2& 1\\ 1& 3& 3& 3\\ 1& 0& 0& 1\end{array}\right).$$

(2)

$\beta \left(\mathbb{W}\right)$ can be computed in $O\left(n\right(k+\sigma \left)\right)$ time by counting all symbols in $\mathbb{W}$.

Algorithm 14 shows an example of filtering algorithm for permuted pattern matching. This algorithm uses $\beta$ as a hash function, and the KMP algorithm as a patten matching algorithm. First, the algorithm computes ${\mathbb{P}}^{\prime }=\beta \left(\mathbb{P}\right)$ and ${\mathbb{T}}^{\prime }=\beta \left(\mathbb{T}\right)$ and then constructs the border array ${\mathit{Border}}_{{\mathbb{P}}^{\prime }}$ using the same procedure as the KMP algorithm. Next, the algorithm performs pattern matching on ${\mathbb{P}}^{\prime }$ and ${\mathbb{T}}^{\prime }$. When a mismatch occurs, the pattern is shifted by using ${\mathit{Border}}_{{\mathbb{P}}^{\prime }}$. If ${\mathbb{P}}^{\prime }$ matches ${\mathbb{T}}^{\prime }[i:j]$, then the algorithm checks whether the pattern $\mathbb{P}$ permuted-matches $\mathbb{T}[i:j]$ or not, and it outputs the position if true.

Algorithm 14: Filtering algorithm for permuted pattern matching.

Theorem 10.

Given a multi-track text $\mathbb{T}$ and a pattern $\mathbb{P}$, Algorithm 14 computes all occurrence positions of $\mathbb{P}$ in $\mathbb{T}$ in $O\left(\right(m+n\left)\right(\sigma +k)+cmk)$ time, where c is the number of candidates.

Proof. 

As described above, ${\mathbb{P}}^{\prime }=\beta \left(\mathbb{P}\right)$ and ${\mathbb{T}}^{\prime }=\beta \left(\mathbb{T}\right)$ can be computed in $O\left(m\right(\sigma +k\left)\right)$ and $O\left(n\right(\sigma +k\left)\right)$, respectively. The border array ${\mathit{Border}}_{{\mathbb{P}}^{\prime }}$ can be constructed in $O\left(m\sigma \right)$ time, and pattern matching can be performed in $O\left(n\sigma \right)$ time, since the comparison ${\mathbb{P}}^{\prime }\left[i\right]={\mathbb{P}}^{\prime }\left[i\right]$ needs $O\left(\sigma \right)$ time. In addition, the algorithm takes $O\left(cmk\right)$ time to check the candidates. □

6. Experiments

We performed some sets of experiments to evaluate the practical performance of the proposed algorithms. We measured the running time of our algorithms and the AC-automaton-based algorithm [7]. All experiments were performed on a computer with an Intel Xeon CPU E5-2609 8 core, 2.40 GHz, 256 GB memory, and a Debian Wheezy operating system. We set the parameter values as $n=$ 100,000, $m=10$, $k=$ 1000, and $\sigma =2$, and we changed one of the parameters in each experiment to see the relation between the parameters and the running time of the algorithms. We used randomly-generated texts and patterns. The source code of our algorithm is available at https://github.com/ushitora/permutedpatternmatching.

The first set of experiments compared the running times of KMP-based algorithms, namely the multi-track KMP algorithm, the multi-track AC-automaton algorithm, and the multi-track permuted matching automaton algorithm. The purpose of this experiment was to see the changes in the running time of the multi-track KMP algorithm when extended to the multi-track AC-automaton algorithm and the multi-track permuted matching automaton algorithm. The results of the experiment are shown in Figure 4. From the results, we can see that the multi-track AC-automaton algorithm was slower than the multi-track KMP algorithm. The reason for this is that the multi-track AC-automaton algorithm uses state transitions instead of comparing multi-track symbols directly. This time difference is not significant considering that the multi-track AC-automaton algorithm focuses on dictionary matching instead of single pattern matching. Next, we can see that the multi-track permuted matching automaton algorithm is faster than the multi-track KMP algorithm. The multi-track permuted matching automaton algorithm can perform matching faster because the multi-track permuted matching automaton algorithm does not need to sort the text.

The next experiment compared the running time of the multi-track Boyer–Moore algorithm and the multi-track Horspool algorithm. We also checked the effectiveness of track tries in reducing the matching times of both algorithms. Figure 5 shows the result of the experiment. While the multi-track Horspool was slightly faster than the multi-track Boyer–Moore algorithm, there was no significant difference between these algorithms. We can also see that track tries significantly reduced the matching times of both algorithms, since we do not need to sort the text when using track tries.

The third experiment set compared the running times of the filtering algorithms. We used three algorithms, the KMP algorithm, the Boyer–Moore algorithm, and the Horspool algorithm, as filtering algorithms. Figure 6 shows the running times of the filtering algorithms. There was no significant difference in running time between the filtering algorithms. We can see that the filtering algorithms were fast apart from when the pattern length was $m=1$. The algorithms became very slow, because there were many occurrence position candidates when $m=1$. The occurrence position candidates will be fewer if the pattern length is longer.

Lastly, we compared the proposed algorithms with the AC-automaton-based algorithm [7]. Figure 7 shows the running time of the AC-automaton-based algorithm [7] and the proposed algorithms. We chose the fastest algorithms among the groups. We can see that the proposed algorithms were faster than the AC-automaton-based algorithm overall. The multi-track Boyer–Moore algorithm with track trie was the fastest among the algorithms.

7. Conclusions

We proposed some algorithms for permuted pattern matching on multi-track strings. We primarily focused on the algorithms that preprocess the pattern before performing permuted pattern matching, instead of constructing indexing structures from the text. We showed that our proposed algorithms are faster than the AC-automaton-based algorithm. Moreover, we proposed an algorithm for dictionary matching on multi-track strings, which, to the best of our knowledge, is the first algorithm for this problem. Because of its considerable difficulty owing to a larger number of permutations, only a few algorithms for sub-permuted pattern matching have been proposed. Therefore, developing an algorithm for the sub-permuted pattern matching problem must be addressed in future work.