The string indexing problem is fundamental and important for information retrieval, and to build an index for a given length n text string that allows us to find all occurrences of a given length m pattern string in the text efficiently. The classical indexing structures, suffix trees [16] and suffix arrays [11], require O(n) space and can be built in O(n) time on a constant-size alphabet [6,7,9,12,13,15]. By using suffix trees and suffix arrays, all occurrences of a pattern can be reported in O(m + occ) and O(m log n + occ) time, respectively, where occ is the total number of occurrences of the pattern in the text.
Ehrenfeucht et al. [5] proposed more space efficient indexing structure called position heaps, which requires O(n) space but the number of nodes in the position heaps is at most n + 1 although that of the suffix tree is at most 2n − 1.
Kucherov [?] showed an Ukkonen-like on-line O(n)-time algorithm for constructing position heaps. By using position heaps, the occurrences of the pattern can be found in O(m 2 + occ) time. To improve its time bound to O(m + occ), Ehrenfeucht et al. [5] proposed O(n)-space auxiliary structure, called the maximal-reach pointers (shortly MRPs).
Recently, Katsura et al. [8] proposed a new framework of the string matching problem, called the permuted pattern matching for multi-track strings, that are multi-sets of strings. It can be applied to multiple sequence data such as polyphonic music data, multiple sensor data, and multiple genomes. Formally, two multi-sets of strings T = {t 1 , . . . , t N } and P = {p 1 , . . . , p N } are given, where |t k | = n and |p k | = m for 1 ≤ k ≤ N , and m ≤ n. P is said to permuted-match T at position i if there exists a permutation (j 1 , . . . , j N ) of a subsequence of (1, . . . , N ) such that p 1 = t j1 [i : i + m − 1], . . . , p N = t j N [i : i + m − 1], where t j [b : e] is the substring of t j from b to e. Then, the permuted pattern matching problem is to find all positions i that P permuted-matches T.
To solve this problem efficiently, Katsura et al. proposed an indexing structure for multi-track strings, called multi-track suffix trees (shortly MTST). MTST can be built in O(nN ) time and space, and it provides an O(mN + occ)-time matching algorithm. MTST has most 2n − 1 nodes.
Note that another well-known indexing structure generalized suffix tree (GST) is also applicable to the problem. By a natural extension, the matching can be done in O(mN +occ) time. The space complexity is also O(nN ), but the number of nodes is at most 2nN − 1.
In this paper, we propose two new memory efficient indexing structures for multi-track strings, multi-track position heap (MTPH) and contracted multi-track position heap (CMTPH).
CMTPH is a compact version of MTPH, where some nodes are rearranged and omitted. The number of nodes in MTPH and CMTPH is at most nN + 1 and n + 1, respectively, although the input size of the multi-track text is nN .
The permuted pattern matching using MTPH or CMTPH requires O(m 2 N + occ) or O(m 2 N 2 + occ) time, respectively. Moreover, for MTPH and CMTPH, we define the MRPs to accelarate the matching.
We show O(nN )-time construction algorithms for MTPH and CMTPH with their MRPs. The contributions of this paper is summarized in Table 1.
Let Σ be a finite set of characters, called an alphabet. We assume that Σ is fixed throughout the paper. An element of Σ * is called a string. For two strings x and y, let x • y, or xy briefly, be the concatenation of x and y. For a string w = xyz, strings x, y, z are called prefix, substring, suffix of w, respectively. |w| is the length of w. The empty string is denoted by ε, that is |ε| = 0. w[i] is the i-th character of w, and w[i : j] is the substring of w that begins at position i and ends at j for 1
We denote by x ≺ y if x is lexicographically smaller than y, and denote by x y if either x ≺ y or x = y. For a set S, we denote by |S| the cardinality of S.
An N -tuple1 of strings over Σ of length n is called a multi-track string over Σ or simply multi-track.
For a multi-track T = (t 1 , t 2 , . . . , t N ) over Σ, the i-th element t i of T is called the i-th track, the length of multi-track T is denoted by
and the number of tracks in multi-track T or the track count of T, is denoted by |T| num = N . For two multi-tracks X = (x 1 , x 2 , . . . , x N ) and Y = (y 1 , y 2 , . . . , y N ), we say that X equals Y, denoted by X = Y, if x i = y i for all 1 ≤ i ≤ N .
For a multi-track T = XYZ, multi-track X, Y, and Z are called prefix, substring, and suffix of T, respectively.
The substring of T that begins at position i and ends at position j is denoted by
respectively.
Let X = (x 1 , x 2 , . . . , x N ) be a multi-track of track count N , and r = (r 1 , r 2 , . . . , r N ) be a permutation of (1, . . . , N ). A permuted multi-track of X specified by r is a multi-track (x r1 , x r2 , . . . , x r N ), denoted by either X r 1 , r 2 , . . . , r N or X r . For two multi-tracks X and Y, we say that X permuted-matches Y, denoted by X = Y, if X = Y for some permuted multi-track Y of Y. The problem we consider is defined as following:
Problem 1 (Permuted pattern matching). Given two multi-tracks T = (t 1 , t 2 , . . . , t N ) of length n and P = (p 1 , p 2 , . . . , p N ) of length m, output all positions i that satisfy
For a multi-track X = (x 1 , x 2 , . . . , x N ), let SI (X) = (r 1 , r 2 , . . . , r N ) be a permutation such that x ri
x rj for any 1 ≤ i ≤ j ≤ |X| num , and let Ψ (X) = X SI (X) . All SI (T[i :]) for 1 ≤ i ≤ n and Ψ (T) can be computed in O(nN ) time using the suffix tree [16] or the suffix array [11]. It is known that the suffix tree and the suffix array can be constructed in linear time with respect to the length of the input string [6,7,9,12,13,15]. Therefore, Problem 1 can be solved in O(nmN ) time and O(nN ) space by storing all SI (T[i :]) naively. The aim of this paper is to solve Problem 1 more efficiently than the above naive result.
A trie on Σ is a rooted tree that has the following two properties: (1) each edge is labeled by a character c ∈ Σ, and (2) for each node u and a character c ∈ Σ, u has at most one edge that is labeled by c from u to a child of u. Let T = (V, E) be a trie, where V and E are sets of nodes and edges, respectively. The root node of T is denoted by root. Each edge e ∈ E is denoted by (u, c, v), where c ∈ Σ is the label of e, and v is a child node of a node u. Note that the time required to find the child of a node on the child edge labeled by c ∈ Σ is O(log |Σ|). Because |Σ| is a fixed constant in this paper, so that the above time cost is also constant. For a node v ∈ V , the sequence of nodes and edges from root to v, that is root, e 1 , v 1 , e 2 , v 2 , . . . , e k , v, is called the path from root to v, denoted by path(root, v ). The number of edges on path(root, v ) is called the depth of v, denoted by depth(v). Let c i be the label of e i for i = 1, . . . , k. Then, we say that the string w = c 1 c 2 . . . c k is represented in T , and denote the node v by w and the string w by label (v).
Thus, root = ε and label (root) = ε. For any node v in T , the set of ancestors of v is denoted by Anc(v) and the descendants of v by Des(v).
A sequence hash tree [4] is a trie for hashing a set of strings.
Definition 1 (Sequence hash trees [4]). Let W = {w 1 , w 2 , . . . , w k } be an ordered set of strings, where
, where q i is the shortest prefix of
is called a sequence hash tree of W and denoted by SHT (W ).
For any i, SHT i (W ) is obtained by adding at most one node and one edge. Thus,
Proof. Let v be the node that is added to SHT (W ) when a string w ∈ W is inserted to SHT (W ), and let d = depth(v). Then there exist 1 ≤ i 1 < i 2 < . . . < i d−1 ≤ k such that the strings w i1 , w i2 , . . ., w i d−1 precede w in W , and w ij [: j] = w[: j] holds for each 1 ≤ j ≤ d − 1. These strings also precede w in W , because W is a subset of W . Thus, w i1 , w i2 , . . . , w i d−1 , and w are inserted to SHT (W ) in this order. When w ij is inserted to SHT (W ), the node w[: j] is added to SHT (W ) if w[: j] does not exist in SHT (W ) for 1 ≤ j ≤ d−1. Therefore, when w is inserted to SHT (W ), w[: d − 1] has already been represented in SHT (W ) and w[: d] is added to SHT (W ). As a result, any string represented in SHT (W ) is also represented in SHT (W ), so that the statement holds.
We use the following results for the rooted tree T of n nodes and σ degree.
Lemma 2 (Lowest common ancestor query [14,2]). For any given two nodes u and v, the lowest common ancestor LCA(u, v ) of u and v in T can be answered in O(1) time, after an O(n) time and space preprocessing of T .
Lemma 3 (Nearest marked ancestor query [17,1]). For any given node v, both marking v, denoted by Mark (v ), and finding the nearest ancestor NMA(v ) of v that is marked, can be done in O(1) time, after an O(n log σ) time and O(n) space preprocessing of T .
Lemma 4 (Level ancestor query [3]). For any given node v and an integer d > 0, the ancestor LevA(v , d ) of v at depth d can be answered in O(1) time, after an O(n) time and space preprocessing of T .
In this section, we propose a new data structure, named multi-track position heap (shortly MTPH), based on the sequence hash tree. We define a column concatenated string CS T of a multi-track T = (t 1 , t 2 , . . . , t N ) by
For instance, for T = (abac, deba), we have CS T = adbeabca.
Let T be a multi-track string of length n and track count N over Σ. Let s i,j = CS Ψ (T[i:j]) for 1 ≤ i ≤ j ≤ n, and s i,n is denoted by s i briefly. Let S = {s 1 , s 2 , . . . , s n } be an ordered set of the strings. For 1 ≤ i ≤ n, MTPH i (T) = (V i , E i ) is a trie recursively defined by (V 0 , E 0 ) = ({root}, ∅), and
, where q i is the shortest prefix of s i such that q i / ∈ V i−1 and q i = ε, and
. MTPH n (T) is called a multi-track position heap of T, and denoted by MTPH (T). Figure 1 shows an example of MTPH (T) and column concatenated strings. Both the numbers of nodes and edges of MTPH i (T) increase at most N from MTPH i−1 (T) for each 1 ≤ i ≤ n. Thus, MTPH (T) consumes O(nN ) space. If there exists q i , then we associate the position i to the node s i [:
and call it an indexing node. Otherwise, that is s i ∈ V i−1 , we associate i to the node s i . Therefore, each indexing node stores either one or two positions. In case that an indexing node v stores two positions i and j with i < j, we call that i is the primary position and j is the secondary position in v.
We will show that MTPH (T) can be constructed in O(nN ) time by updating MTPH (T[: i − 1]) to MTPH (T[: i]) iteratively for i = 1, 2, . . . , n, similar to the online construction algorithm for position heaps [10]. We remark that it is not trivial because s i is not necessarily a suffix of s i−1 (see Figure 1, left). Let us focus on the differences between MTPH (T[: i − 1]) and MTPH (T[: i]). For 1 ≤ j ≤ i, if j is a primary position in a node v in MTPH (T[: i − 1]), j must be the primary position stored in the same node v in MTPH (T[: i]). If j is a secondary position in MTPH (T[: i−1]), there are two cases in MTPH (T[: i]): (1) j becomes a primary position in a newly created node v , or (2) j remains the secondary position, but in another node v . In any case, the node v is in Des(v). Thus, we consider how to update the nodes storing two positions.
Let j (1 ≤ j < i) be any secondary position in a node v in MTPH (T[: i − 1]). If the string s j,i is not represented in MTPH (T[: i − 1]) yet, then we create a new path path(root, s j ,i ) and reset the position j from v to a newly created node s j,i . Otherwise, the position j must be a secondary in another existing node v in MTPH (T[: i]). Thus, we should reset j from v to v = s j,i . These update process can be done by traversing the nodes storing the secondary positions.
We will show that for any position b (1 ≤ b < i), if b is a secondary position then b + 1 is also a secondary position, by a series of lemmas as follows.
Lemma 5. For two multi-tracks
and they have been inserted to MTPH in the order of k = 1, 2, . . . , m. At the same time, Ψ (T[j k + 1 : j k + k − 1]) for 1 ≤ k ≤ m have also been inserted in this order, because MTPH is constructed by inserting suffixes in descending order with respect to the length. Lemma 5 leads Ψ (T[j k + 1 : ) should be updated as follows: (1) for b ≤ j < b , build path(s j ,i−1 , s j ,i ) and reset the position j from s j,i−1 to the new node s j,i as its primary position, and (2) for b ≤ j ≤ i, reset the position j from s j,i−1 to the existing node s j,i as its secondary position. We refer the position b as the active position, and the indexing node s b,i−1 as the active node, similarly to [?]. The nodes storing positions b, b + 1, . . . , i − 1 can be traversed efficiently by using the suffix pointers defined below.
Definition 3 (Multi-track suffix pointers). For any indexing node s i,j in MTPH (T), the multi-track suffix pointer of s i,j is a pointer from s i,j to the node s i+1,j , and denoted as mtsp(s i,j ) = s i+1,j .
For every indexing node s i,j in MTPH (T[: i]), the existence of mtsp(s i,j ) is guaranteed by Lemma 6. In our algorithm, we will use a chain of N nodes ⊥ 1 , ⊥ 2 , . . . , ⊥ N , such that each ⊥ k (1 ≤ k ≤ N ) is connected to ⊥ k+1 by an edge labeled by all c ∈ Σ, regarding that ⊥ N +1 = root, and mtsp(root) =⊥ 1 . They play a role of sentinel nodes, similarly to [15] and [?].
We now describe the construction algorithm of MTPH (T). First of all, we compute SI (T[i : n]) for all 1 ≤ i ≤ n in O(nN ) time. It determines every
In each iteration, we do not need to keep all the secondary nodes to update MTPH (T[: i − 1]), because these nodes can be visited through the suffix pointers recursively from the active node. Thus, we only maintain the active position b and the active node s b,i−1 . If there is no secondary node in MTPH (T[: i − 1]), the active node is root and the active position is i.
In i-th iteration, the algorithm checks whether there is path(s b,i−1 , s b,i ) or not. If it does not exist, the algorithm performs the modifications of Case (1) described above. After the modification, the new indexing node s b,i is created as a descendant of s b,i−1 . Then, the active position and the active node are updated to b + 1 and mtsp(s b,i−1 ) = s b+1,i−1 respectively, and the algorithm performs the above process iteratively until the path is found. The multi-track suffix pointer mtsp(s b,i ) is built as mtsp(s b,i ) = s b+1,i after the next modification. When path(s b,i−1 , s b,i ) is found, the algorithm updates the active node to s b,i and makes the suffix pointer from the last created indexing node to the new active node if such a node exists. Hence, for any indexing node, suffix pointer of it is defined indeed. To update MTPH (T[: i − 1]) into MTPH (T[: i]), it is enough to perform only the modifications of Case (1), because the modifications of Case (2) does not add any node nor edge to MTPH. All the secondary positions will be determined after constructing MTPH (T) by traversing nodes through the suffix pointers recursively from the active node.
Algorithm 1 shows a pseudo-code of the construction algorithm, and the function to find path(s b,i−1 , s b,i ) at line 26. Let us analyze the running time of Algorithm 1. Each iteration of the while-loop from line 9 takes O(nN ) time over the whole run of the algorithm, because at most N nodes and edges are visited or created in each iteration and 1 ≤ b ≤ n. Each process in the rest of the for-loop from line 6 takes at most O(N ) time, and the loop iterates exactly n times. Thus, the running time of Algorithm 1 is O(nN ) time. We now consider to solve Problem 1 for a pattern P by using MTPH (T). Let w be the longest prefix of CS Ψ (P) represented in MTPH (T). We can compute w in O(mN ) time by traversing path(root, w ). If w = CS Ψ (P) , all the positions stored in the nodes of the subtree rooted by w are the occurrences of the pattern P in T. We will deal with enumerating all these positions later. Before it, remark where pointerNode is the deepest indexing node visited in the i-th iteration and computed in line 5. Note that, the process of line 5 can be computed in constant time because whether currNode is an indexing node or not is determined by depth(currNode) mod N = 0 or not.
Let us consider the time complexity of Algorithm 2. Each process of line 1, line 7 and line 8 can be done in O(1) time, so that these processes take O(n) time in total. Let us consider the number of executions of while-loop at line 3. In each loop, s i [ ] corresponding to a letter in the text T is read. We assume s i [ i ] belongs to k-th column of T for 1 ≤ k ≤ n. k does not decrease between i-th and (i + 1)-th iterations because (i + 1)-th iteration begins at mtsp(s i,k ) = s i+1,k . In addition, since |s i [ i ]| ≥ N , i ≤ k holds. Thus, all letters in T are read at least one time in all iterations. On the other hand, the letters corresponding to the labels on path(pointerNode, currNode) in i-th iteration can be read redundantly in (i + 1)-th iteration. However, the number of such labels does not exceed N in each iteration. Therefore, the total number of executions of while-loop does not exceed 2nN . As a result, the running time of Algorithm 2 is O(nN ) time.
In the naive matching algorithm with MTPH described above, the cost of the comparison of CS Ψ (P) with s i,i+m−1 for i ∈ I can be reduced from O(mN ) to O(1) by using the MRPs and the lowest common ancestor queries mentioned in Lemma 4, if CS Ψ (P) itself is represented in MTPH (T). Whether CS Ψ (P) = s i,i+m−1 or not is determined by mrp(α i ) ∈ Des(CS Ψ (P) ). If LCA(mrp(α i ), CS Ψ (P) ) = CS Ψ (P) , then mrp(α i ) ∈ Des(CS Ψ (P) ) holds. By Lemma 4, the query LCA(mrp(α i ), CS Ψ (P) ) can be answered in O(1) time after an O(nN ) time and space preprocessing of MTPH (T). Thus, the comparison of CS Ψ (P) with s i,i+m−1 can be done in O(1) time. Hence, the total time is O(mN + occ) in this case, different from O(m 2 N + occ) time of the naive algorithm. Remark that, unfortunately, this result does not improve the upperbound of the time complexity of the matching for the worst case. If CS Ψ (P) is not represented in MTPH (T), we must compute CS Ψ (P) = s i,i+m−1 , that takes O(mN ) time. In this case, all comparisons are done in O(m 2 N ) time because |I| < m. By considering the above two cases, the time bound of the matching is
Theorem 2. Problem 1 can be solved in O(m 2 N +occ) time by using MTPH (T) with MRPs.
We propose a more space-efficient version of MTPH, by omitting non-indexing nodes of MTPH (see Figure 1, right).
Let T be a multi-track string of length n and track count N over Σ. Let S = {s 1 , s 2 , . . . , s n } be an ordered set of strings, where s i = CS Ψ (T[i:]) for 1 ≤ i ≤ n. A contracted multi-track position heap of T, denoted by CMTPH (T), is a sequence hash tree of S, i.e., CMTPH (T) = SHT (S).
Since CMTPH (T) is a sequence hash tree for an ordered set of cardinality n, it has n + 1 nodes and n edges, so that CMTPH (T) consumes only O(n) space. Given T, we can construct easily CMTPH (T) in O(nN + n 2 ) time as follows: compute SI (T[i :]) for 1 ≤ i ≤ n in O(nN ) time, then insert all s i = CS Ψ (T[i:]) to the tree in order; each insertion can be done in O(n), so that O(n 2 ) in total.
We now show a more efficient construction algorithm for CMTPH (T), that runs in O(nN ) time. It re-assign the positions in the nodes in MTPH (T), and eliminates all non-indexing nodes as follows. First let us noticed that in Figure 1, CMTPH (T) is a subtree of MTPH (T) with the same root node, if we ignore the positions stored in the nodes. It is always the cases, as follows.
Lemma 8. For 1 ≤ i ≤ n, CMTPH i (T) is a subtree of MTPH i (T) rooted by the root of MTPH i (T), if we ignore the positions stored in the nodes.
Proof. CMTPH i (T) is a sequence hash tree of S = {s 1 , s 2 , . . . , s i }. On the other hand, MTPH i (T) is equivalent to a sequence hash tree of S = i k=1
Because S is a subset of S , the statement holds by Lemma 1.
Lemma 8 implies that all nodes and edges in CMTPH (T) are included in MTPH (T). Therefore, CMTPH (T) can be obtained by the following process. For each i = 1, 2, . . . , n, we re-assign the position i stored in an indexing node α i to its ancestor node β i ∈ Anc(α i ), that does not store the primary position (i.e., β i may store the secondary position) and the farthest from α i (i.e., nearest from the root). If there is no such a node, then α i keeps storing i. After that, we eliminate all nodes that stores no position. Then, the remaining tree is CMTPH (T).
To find β i efficiently, we use the two types of queries on a rooted tree, that are the nearest marked ancestor query and the level ancestor query referred in Lemma 3 and Lemma 4, respectively. Each query can be answered in constant time after a linear-time preprocess of the tree.
We now show how to find β i from α i . We mark a node to indicate that the node stores some positions in CMTPH (T). At the beginning, only the root of MTPH (T) is marked. Because β i is the farthest unmarked ancestor of α i , it is the depth d + 1 ancestor of α i , where d is the depth of the nearest marked ancestor u of α i . The ancestor u is obtained by NMA(α i ), and then β i by LevA(u, depth(u) + 1 ), both in O(1) time. If u = α i , re-assign the position i from α i to β i , and mark β i . Otherwise, i.e., u = α i , do nothing. Repeating it for i = 1, 2, . . . , n, we get CMTPH (T) in O(n) time from MTPH (T). Because MTPH (T) can be constructed in O(nN ) time, we obtain the following result. CMTPHs is useful for permuted pattern matching instead of MTPHs. Because any node in CMTPH stores at least one position, the candidate positions for matching is at most |I| = O(mN ). Thus, the time complexity is O(m 2 N 2 + occ). It can be improved by using the maximal-reach pointers for CMTPH, denoted by cmrp(β i ), in the same way as MTPH. Because cmrp(β i ) = NMA(mrp(α i )) holds for any i after marking all β i 's, we get them in O(n) time. Thus we have the following results. For the permuted pattern matching, the maximal-reach pointers of CMTPH work similarly to that of MTPH. Thus, it is not difficult to see that the following theorem holds.
Theorem 5. Problem 1 can be solved in O(m 2 N 2 + occ) time by using CMTPH (T) with the maximal-reach pointers.
We proposed two new indexing structures, MTPH and CMTPH, for multi-track strings, that are memory-efficient compared with the multi-track suffix tree in [8]; MTPH and CMTPH need O(nN ) and O(n) space, respectively. We showed an O(nN )-time construction algorithms of MTPH and CMTPH, and proposed MRPs for both of them. By using these data structures, the permuted pattern matching problem can be solved efficiently: O(m 2 N + occ) time by MTPH, and O(m 2 N 2 + occ) time by CMTPH. Our future work is to construct CMPTH directly in O(nN ) time without constructing MTPH. We are also preparing experiments to evaluate these structures.
We now explain how to enumerate all the positions in the nodes of the subtree rooted by w, in case that w = CS Ψ (P) . Let α i be an indexing node that stores the position i in MTPH (T). To obtain these positions efficiently in O(occ) time, we construct another tree T consists only of indexing nodes α i 's in MTPH (T), where a node α i is a child of another node α j in T if and only if α i ∈ Des(α j ) and no other indexing node exists between α i and α j in MTPH (T). Obviously, T can be built by depth-first-traversal of MTPH (T) in O(nN ) time, and by traversing the subtree of T rooted by the node w, we can enumerate all matched positions in O(occ) time. Thus, we can determine all the positions i such that
We now show that the matching by using MTPH can be accelerated by adding maximal-reach pointers (shortly MRPs). MRPs are the auxiliary structures for standard position heaps proposed by Ehrenfeucht et al. [5]. We will extend it to MTPHs as follows.
Definition 4 (MRPs for MTPHs). For an indexing node α i storing i in MTPH (T), the maximal-reach pointer of α i is a pointer from α i to s i [: i ], and denoted by mrp
Algorithm 2 is an algorithm for adding MRPs to MTPH, that is based on Kucherov's algorithm for standard position heaps [?]. First of all, the algorithm preprocesses MTPH (T) so that for any node v, it can obtain the depth of v in O(1) time, by assigning unique numbers to the nodes by the depth first traversal. In i-th iteration between line 2 and line 8, it adds a pointer mrp(α i ) = s i [: i ], where s i [: i ] is determined as follows: beginning by currNode = root, it goes down to a child s i [: ] of depth(currNode) ≤ ≤ |s i | until either currNode does not have a child s i [: ] or = |s i | holds (line 3 to line 6). Then, mrp(α i ) is obtained as s i [: i ] (line 7). The next i+1-th iteration begins at mtsp(pointerNode),