=Paper=
{{Paper
|id=Vol-1326/041-Katsura
|storemode=property
|title=Position Heaps for Permuted Pattern Matching on Multi-Track String
|pdfUrl=https://ceur-ws.org/Vol-1326/041-Katsura.pdf
|volume=Vol-1326
|dblpUrl=https://dblp.org/rec/conf/sofsem/KatsuraONS15
}}
==Position Heaps for Permuted Pattern Matching on Multi-Track String==
https://ceur-ws.org/Vol-1326/041-Katsura.pdf
Position Heaps for Permuted Pattern Matching
on Multi-Track Strings
Takashi Katsura, Yuhei Otomo, Kazuyuki Narisawa, and Ayumi Shinohara
Graduate School of Information Sciences, Tohoku University, Japan
{katsura@shino.,otomo@shino.,narisawa@,ayumi@}ecei.tohoku.ac.jp
Abstract. A multi-set of N strings of length n is called a multi-track
string. The permuted pattern matching is the problem that given two
multi-track strings T = {t1 , . . . , tN } of length n and P = {p1 , . . . , pN }
of length m, outputs all positions i such that {p1 , . . . , pN } = {t1 [i :
i + m − 1], . . . , tN [i : i + m − 1]} We propose two new indexing structures
for multi-track stings. One is a time-efficient structure for T that needs
O(nN ) space and enables us to solve the problem in O(m2 N + occ) time,
where occ is the number of occurrences of the pattern P in the text T.
The other is memory-efficient, it requires only O(n) space, whereas the
matching consumes O(m2 N 2 + occ) time. We show that both of them
can be constructed in O(nN ) time.
Keywords: string matching, multi-track, indexing structure
1 Introduction
The string indexing problem is fundamental and important for information re-
trieval, 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 posi-
tion 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 con-
structing position heaps. By using position heaps, the occurrences of the pat-
tern can be found in O(m2 + 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 match-
ing 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,
42 T. Katsura et al.
Table 1. Data structures for the permuted pattern matching
data structure space # of nodes construction search
GST O(nN ) 2nN − 1 O(nN ) O(mN + occ)
MTST [8] O(nN ) 2n − 1 O(nN ) O(mN + occ)
MTPH (proposal) O(nN ) nN + 1 O(nN ) O(m2 N + occ)
CMTPH (proposal) O(n) n+1 O(nN ) O(m2 N 2 + occ)
two multi-sets of strings T = {t1 , . . . , tN } and P = {p1 , . . . , pN } are given, where
|tk | = n and |pk | = m for 1 ≤ k ≤ N , and m ≤ n. P is said to permuted-match
T at position i if there exists a permutation (j1 , . . . , jN ) of a subsequence of
(1, . . . , N ) such that p1 = tj1 [i : i + m − 1], . . . , pN = tjN [i : i + m − 1], where
tj [b : e] is the substring of tj 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 struc-
ture 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(m2 N +
occ) or O(m2 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.
2 Preliminaries
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 ≤ i ≤ j ≤ |w|. Moreover, let w[: i] = w[1 : i] and w[i :] = w[i : |w|].
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.
Position Heaps for Permuted Pattern... 43
An N -tuple 1 of strings over Σ of length n is called a multi-track string over
Σ or simply multi-track.
For a multi-track T = (t1 , t2 , . . . , tN ) over Σ, the i-th element ti of T is called
the i-th track, the length of multi-track T is denoted by |T|len = |t1 | = |t2 | =
· · · = |tN | = n, 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 = (x1 , x2 , . . . , xN ) and
Y = (y1 , y2 , . . . , yN ), we say that X equals Y, denoted by X = Y, if xi = yi for
all 1 ≤ i ≤ N .
For a multi-track T = XYZ, multi-track X, Y, and Z are called prefix, sub-
string, and suffix of T, respectively. T[i] denotes (t1 [i], t2 [i], . . . , tN [i]) for 1 ≤ i ≤
|T|len , i.e., T = T[1]T[2] . . . T[|T|len ]. The substring of T that begins at position
i and ends at position j is denoted by T[i : j] = (t1 [i : j], t2 [i : j], . . . , tN [i : j])
for 1 ≤ i ≤ j ≤ |T|len . Moreover, let T[: i] = T[1 : i] and T[i :] = T[i : |T|len ],
respectively.
Let X = (x1 , x2 , . . . , xN ) be a multi-track of track count N , and r =
(r1 , r2 , . . . , rN ) be a permutation of (1, . . . , N ). A permuted multi-track of X spec-
ified by r is a multi-track (xr1 , xr2 , . . . , xrN ), denoted by either Xhr1 , r2 , . . . , rN i
or Xhri. For two multi-tracks X and Y, we say that X permuted-matches Y, de-
noted by X = ./
Y, if X = Y0 for some permuted multi-track Y0 of Y. The problem
we consider is defined as following:
Problem 1 (Permuted pattern matching). Given two multi-tracks T = (t1 , t2 ,
. . . , tN ) of length n and P = (p1 , p2 , . . . , pN ) of length m, output all positions i
./
that satisfy P = T[i : i + m − 1].
For a multi-track X = (x1 , x2 , . . . , xN ), let SI (X) = (r1 , r2 , . . . , rN ) be
a permutation such that xri xrj for any 1 ≤ i ≤ j ≤ |X|num , and let
Ψ (X) = XhSI (X)i. 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, e1 , v1 , e2 , v2 , . . . , ek , v, is called the path from root to
1
A multi-track string was regarded as a multi-set of strings in [8]. In this paper,
however, we define it as a tuple of strings for notational convenience.
44 T. Katsura et al.
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 ci be the label of ei for i = 1, . . . , k. Then,
we say that the string w = c1 c2 . . . ck 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 = {w1 , w2 , . . . , wk } be an
ordered set of strings, where wi ∈ Σ ∗ . For 1 ≤ i ≤ k, SHT i (W ) = (Vi , Ei )
is a trie recursively defined by (V0 , E0 ) = ({root}, ∅), and SHT i (W ) = (Vi−1 ∪
{qi }, Ei−1 ∪ {(qi [: |qi | − 1], c, qi )}), where
qi is the shortest prefix of wi satisfying qi ∈/ Vi−1 , and c = qi [|qi |]. SHT k (W )
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, SHT (W ) = SHT k (W ) consumes O(k) space. SHT i (W ) is obtained by
adding a node corresponding to wi into SHT i−1 (W ). When the node correspond-
ing to wi is added into SHT i−1 (W ), we say that wi is inserted to SHT i−1 (W ).
Lemma 1. Let W = {w1 , w2 , . . . , wK } and W 0 = {w10 , w20 , . . . , wk0 } (k ≤ K)
be ordered sets of strings such that W 0 is a subset of W . Then SHT (W 0 ) is
a subtree of SHT (W ) rooted by the root of SHT (W ).
Proof. Let v be the node that is added to SHT (W 0 ) when a string w ∈ W 0 is
inserted to SHT (W 0 ), and let d = depth(v). Then there exist 1 ≤ i1 < i2 <
. . . < id−1 ≤ k such that the strings wi01 , wi02 , . . ., wi0d−1 precede w in W 0 , and
wi0j [: j] = w[: j] holds for each 1 ≤ j ≤ d − 1. These strings also precede w in W ,
because W 0 is a subset of W . Thus, wi01 , wi02 , . . . , wi0d−1 , and w are inserted to
SHT (W ) in this order. When wi0j 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 0 )
is also represented in SHT (W ), so that the statement holds. t
u
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 .
Position Heaps for Permuted Pattern... 45
Fig. 1. The column concatenated strings si = CSΨ (T[i:]) in the left, MTPH (T)
in the middle, and CMTPH (T) in the right for a multi-track T =
(aabbaabbaaabbaa, ababababbababba). Maximal-reach pointers mrp(v) in MTPH and
CMTPH are drawn as broken lines, where they are omitted if mrp(v) = v for clarity.
In indexing nodes, its associated positions (either one or two) are written.
3 Multi-Track Position Heaps
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 CST of a multi-track T = (t1 , t2 , . . . , tN ) by
CST = t1 [1]t2 [1] . . . tN [1] t1 [2]t2 [2] . . . tN [2] . . . t1 [n]t2 [n] . . . tN [n].
For instance, for T = (abac, deba), we have CST = adbeabca.
Definition 2 (MTPH). Let T be a multi-track string of length n and track
count N over Σ. Let si,j = CSΨ (T[i:j]) for 1 ≤ i ≤ j ≤ n, and si,n is denoted by
si briefly. Let S = {s1 , s2 , . . . , sn } be an ordered set of the strings. For 1 ≤ i ≤ n,
MTPH i (T) = (Vi , Ei ) is a trie recursively defined by (V0 , E0 ) = ({root}, ∅), and
S∆i −1 S∆i −1
Vi = Vi−1 ∪ j=0 {si [: |qi | + j]}, Ei = Ei−1 ∪ j=0 {(si [: |qi | + j − 1], si [|qi | +
j], si [: |qi | + j])}), where qi is the shortest prefix of si such that qi ∈ / Vi−1 and
qi 6= ε, and ∆i = N − ((|qi | − 1) mod N ). If no such qi exists, that is si ∈ Vi−1 ,
then (Vi , Ei ) = (Vi−1 , Ei−1 ). 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 qi , then we associate the position i to the node si [: |qi | + ∆i − 1],
and call it an indexing node. Otherwise, that is si ∈ Vi−1 , we associate i to the
node si . 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
46 T. Katsura et al.
online construction algorithm for position heaps [10]. We remark that it is not
trivial because si is not necessarily a suffix of si−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 0 , or (2) j remains the secondary
position, but in another node v 0 . In any case, the node v 0 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 sj,i is not represented in MTPH (T[: i − 1]) yet, then we create
a new path path(root, sj ,i ) and reset the position j from v to a newly created
node sj,i . Otherwise, the position j must be a secondary in another existing node
v 0 in MTPH (T[: i]). Thus, we should reset j from v to v 0 = sj,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 X = (x1 , x2 , . . . , xN ) and Y = (y1 , y2 , . . . , yN ),
if Ψ (X) = Ψ (Y) then Ψ (X[2 :]) = Ψ (Y[2 :]).
Proof. Trivial. t
u
Lemma 6. For any multi-track W of length m, if CSΨ (W) is represented in
MTPH i (T), then CSΨ (W[2:]) is also represented in MTPH i (T) for any 1 ≤ i ≤ n.
Proof. Because CSΨ (W) is represented in MTPH i (T), there are 1 ≤ j1 ≤ j2 ≤
. . . ≤ jm ≤ i such that Ψ (T[jk : jk + k − 1]) = Ψ (W[: k]) for 1 ≤ k ≤ m, and
they have been inserted to MTPH in the order of k = 1, 2, . . . , m. At the same
time, Ψ (T[jk + 1 : jk + 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[jk + 1 : jk + k]) = Ψ (W[2 : k]).
Thus, CSΨ (T[jm +1:jm +m]) = CSΨ (W)[2:] is represented in MTPH i (T ). t
u
Lemma 7. If b is a secondary position of a node v in MTPH i (T) for 1 ≤ b < i,
then b + 1 is also a secondary position of another node in it.
Proof. Let b0 be the primary position of v. Then, b0 < b and sb = sb0 [: |sb |] hold.
From Lemma 6, sb+1 is represented in MTPH i (T). In addition, sb0 +1 [: |sb+1 |]
is also represented. From Lemma 5, sb+1 = sb0 +1 [: |sb+1 |] holds. Since b0 < b,
b0 + 1 < b + 1. Thus, b + 1 is a secondary position of sb0 +1 . t
u
Let b be the smallest position that is a secondary position in MTPH (T[: i−1])
with 1 ≤ b ≤ i − 1. By Lemma 7, all the secondary positions are written as
b, b + 1, . . . , i − 1. In addition, these positions are partitioned into two intervals.
Let b0 be the smallest position such that sb0 ,i is represented in MTPH (T[: i − 1]).
Then, sb0 +1,i is also represented in it by Lemma 6. Similarly, all sb0 +2,i , . . . , si−1,i
are represented in it, too. Therefore, all the positions b, b+1, . . . , b0 −1 in the first
Position Heaps for Permuted Pattern... 47
interval are primary positions in MTPH (T[: i]), while all b0 , b0 + 1, . . . , i − 1 in
the second interval are secondary positions in MTPH (T[: i]). Summarizing the
above discussion, to obtain MTPH (T[: i]), MTPH (T[: i − 1]) should be updated
as follows: (1) for b ≤ j < b0 , build path(sj ,i−1 , sj ,i ) and reset the position j from
sj,i−1 to the new node sj,i as its primary position, and (2) for b0 ≤ j ≤ i, reset
the position j from sj,i−1 to the existing node sj,i as its secondary position. We
refer the position b as the active position, and the indexing node sb,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 si,j in
MTPH (T), the multi-track suffix pointer of si,j is a pointer from si,j to the
node si+1,j , and denoted as mtsp(si,j ) = si+1,j .
For every indexing node si,j in MTPH (T[: i]), the existence of mtsp(si,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
si = CSΨ (T[i:]) . 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 sb,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(sb,i−1 , sb,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 sb,i is created
as a descendant of sb,i−1 . Then, the active position and the active node are
updated to b + 1 and mtsp(sb,i−1 ) = sb+1,i−1 respectively, and the algorithm
performs the above process iteratively until the path is found. The multi-track
suffix pointer mtsp(sb,i ) is built as mtsp(sb,i ) = sb+1,i after the next modification.
When path(sb,i−1 , sb,i ) is found, the algorithm updates the active node to sb,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(sb,i−1 , sb,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
48 T. Katsura et al.
Algorithm 1: MTPH construction algorithm
Input: T
Output: MTPH (T)
1 compute SI (T[i : n]) for all 1 ≤ i ≤ n;
2 create root and ⊥N ; create edge (⊥N , c, root) for each character c;
3 for j = N − 1 downto 1 do
4 create node ⊥j ; create edge (⊥j , c, ⊥j+1 ) for each character c;
5 mtsp(root) =⊥1 ; activeNode = root; b = 1;
6 for i = 1 to n do
7 lastNode = undefined;
8 targetNode = find (activeNode, sb [depth(activeNode)+1 :]);
9 while targetNode = undefined do
10 for j = 1 to N do
11 u = activeNode;
12 if there is not an edge labeled by w[j] from u then
13 create a node v and an edge (u, w[j], v) where
label (v) = label (u) · w[i];
14 else
15 Let v be a child of u connected by the edge (u, w[j], v);
16 u = v;
17 if lastNode 6= undefined then mtsp(lastNode) = u;
18 lastNode = u; Let lastNode store b;
19 activeNode = mtsp(activeNode); b = b + 1;
20 targetNode = find (activeNode, sb [depth(activeNode)+1 :]);
21 activeNode = targetNode;
22 if lastNode 6= undefined then mtsp(lastNode) = activeNode;
23 if b 6= n + 1 then
24 for b ≤ j ≤ n do
25 Let activeNode store j ; activeNode = mtsp(activeNode);
26 Function find (node, w )
27 for j = 1 to N do
28 if exist edge (node, w[j], v) then node = v;
29 else return undefined;
30 return node;
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.
Theorem 1. Algorithm 1 constructs MTPH (T) in O(nN ) time and space.
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
Position Heaps for Permuted Pattern... 49
Algorithm 2: Adding maximal reach pointers for MTPH
Input: Tand MTPH (T) with multi-track suffix pointers
1 currNode = root; pointerNode = root; ` = 1;
2 for i = 1 to n do
3 while currNode has an outgoing edge labeled by si [`] and ` < |si | do
4 currNode = si [: `];
5 if currNode is an indexing node then pointerNode = currNode;
6 ` = ` + 1;
7 mrp(αi ) = currNode; currNode = mtsp(pointerNode);
8 pointerNode = currNode; ` = depth(currNode);
that we should also consider another type of occurrences; let I be the set of
positions stored in the nodes on path(root, w ). These are also candidates for the
occurrences. Because path(root, w ) contains at most m indexing nodes, |I| =
./
O(m). For each i ∈ I, we check whether P = T[i : i + m − 1] or not by simply
comparing CSΨ (P) with si,i+m−1 = CSΨ (T[i:i+m−1]) , and report it if it does. Both
the computation of si,i+m−1 and the comparison are done in O(mN ) time.
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
./
P= T[i : i + m − 1] in O(m2 N + occ) time.
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 si [: `i ], and
denoted by mrp(αi ) = si [: `i ], where si [: `i ] is the longest prefix of si = CSΨ (T[i:])
represented in MTPH (T).
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 ) = si [: `i ],
where si [: `i ] is determined as follows: beginning by currNode = root, it goes
down to a child si [: `] of depth(currNode) ≤ ` ≤ |si | until either currNode does
not have a child si [: `] or ` = |si | holds (line 3 to line 6). Then, mrp(αi ) is ob-
tained as si [: `i ] (line 7). The next i+1-th iteration begins at mtsp(pointerNode),
50 T. Katsura et al.
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, si [`] corresponding to a letter in the text T is read. We assume si [`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(si,k ) = si+1,k . In
addition, since |si [`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 si,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) =
si,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 Lem-
ma 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 si,i+m−1 can be done in O(1) time. Hence, the total time is
O(mN + occ) in this case, different from O(m2 N + occ) time of the naive al-
gorithm. Remark that, unfortunately, this result does not improve the upper-
bound 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) = si,i+m−1 , that takes
O(mN ) time. In this case, all comparisons are done in O(m2 N ) time because
|I| < m. By considering the above two cases, the time bound of the matching is
O(mN + occ + m2 N ) = O(m2 N + occ).
Theorem 2. Problem 1 can be solved in O(m2 N +occ) time by using MTPH (T)
with MRPs.
4 Contracted Multi-Track Position Heaps
We propose a more space-efficient version of MTPH, by omitting non-indexing
nodes of MTPH (see Figure 1, right).
Definition 5 (CMPTH). Let T be a multi-track string of length n and track
count N over Σ. Let S = {s1 , s2 , . . . , sn } be an ordered set of strings, where si =
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).
Position Heaps for Permuted Pattern... 51
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 + n2 ) time as follows:
compute SI (T[i :]) for 1 ≤ i ≤ n in O(nN ) time, then insert all si = CSΨ (T[i:])
to the tree in order; each insertion can be done in O(n), so that O(n2 ) 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 = {s1 , s2 , . . . , si }. On the other
Si S∆k
hand, MTPH i (T) is equivalent to a sequence hash tree of S 0 = k=1 j=1 {sk } =
{s1 , . . . , s1 , s2 , . . . , s2 , . . . , si , . . . , si }. Because S is a subset of S 0 , the statement
| {z } | {z } | {z }
∆1 ∆2 ∆i
holds by Lemma 1. t
u
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 6= α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.
Theorem 3. Given a multi-track T of length n and track count N , CMTPH (T)
can be constructed in O(nN ) time and space.
CMTPHs is useful for permuted pattern matching instead of MTPHs. Be-
cause any node in CMTPH stores at least one position, the candidate posi-
tions for matching is at most |I| = O(mN ). Thus, the time complexity is
52 T. Katsura et al.
O(m2 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.
Theorem 4. Given a multi-track T of length n and track count N , CMTPH (T)
with the maximal-reach pointers for CMTPH (T) can be constructed in O(nN )
time and space.
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(m2 N 2 + occ) time by using
CMTPH (T) with the maximal-reach pointers.
5 Conclusion and Future Work
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(m2 N + occ) time by MTPH, and
O(m2 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.
References
1. Amir, A., Farach, M., Idury, R.M., Poutre, J.A.L., Schäffer, A.A.: Improved dy-
namic dictionary matching. Information and Computation 119(2), 258–282 (1995)
2. Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: LATIN 2000:
Theoretical Informatics, 88–94 (2000)
3. Bender, M.A., Farach-Colton, M.: The level ancestor problem simplied. Theoretical
Computer Science 321(1), 5–12 (2004)
4. Coffman, Jr., E.G., Eve, J.: File structures using hashing functions. Communica-
tions of the ACM 13(7), 427–432 (1970)
5. Ehrenfeucht, A., McConnell, R.M., Osheim, N., Woo, S.W.: Position heaps:
A simple and dynamic text indexing data structure. Journal of Discrete Algo-
rithms 9(1), 100–121 (2011)
6. Farach, M.: Optimal suffix tree construction with large alphabets. In: FOCS.
137–143 (1997)
7. Kärkkäinen, J., Sanders, P.: Simple linear work suffix array construction. In:
ICALP. 943–955 (2003)
8. Katsura, T., Narisawa, K., Shinohara, A., Bannai, H., Inenaga, S.: Permuted pat-
tern matching on multi-track strings. In: SOFSEM, 280–291 (2013)
Position Heaps for Permuted Pattern... 53
9. Ko, P., Aluru, S.: Space efficient linear time construction of suffix arrays. In: CPM,
200–210 (2003)
10. Kucherov, G.: On-line construction of position heaps. Journal of Discrete Algo-
rithms 20, 3–11 (2013)
11. Manber, U., Myers, G.: Suffix arrays: a new method for on-line string searches.
SIAM Journal on Computing 22(5), 935–948 (1993)
12. McCreight, E.M.: A space-economical suffix tree construction algorithm. Journal
of the ACM 23(2), 262–272 (1976)
13. Nong, G., Zhang, S., Chan, W.H.: Linear suffix array construction by almost pure
induced-sorting. In: DCC, 193–202 (2009)
14. Schieber, B., Vishkin, U.: On finding lowest common ancestors: Simplification and
parallelization. SIAM Journal on Computing 17(6), 1253–1262 (1988)
15. Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14(3), 249–260
(1995)
16. Weiner, P.: Linear pattern matching algorithms. In: SWAT, 1–11 (1973)
17. Westbrook, J.: Fast incremental planarity testing. In: ICALP, 342–353 (1992)