In this paper, we propose a new indexing structure for parameterized strings which we call PLSTs, by generalizing linear-size su x tries for ordinary strings. Two parameterized strings are said to match if there is a bijection on the symbol set that makes the two coincide. PLSTs are applicable to the parameterized pattern matching problem, which is to decide whether the input parameterized text has a substring that matches the input parameterized pattern. The size of PLSTs is linear in the text size, with which our algorithm solves the parameterized pattern matching problem in linear time in the pattern size. PLSTs can be seen as a compacted version of parameterized su x tries and a combination of linear-size su x tries and parameterized su x trees. We experimentally show that PLSTs are more space e cient than parameterized su x trees for highly repetitive strings.
The pattern matching problem is to check whether a pattern string occurs in a
text string or not. To e ciently solve the pattern matching problem, a numerous
number of text indexing structures have been proposed. Su x trees are the most
widely used data structures and provide many applications including several
variants of pattern matching problems [
Copyright 2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
non-branching nodes by edges like a su x tree, but the original path labels
are recovered by referring to other edge labels in the LST itself unlike su x
trees. LSTs use less memory space than su x trees for indexing the same highly
repetitive strings [
On the other hand, di erent types of pattern matching have been proposed
and intensively studied. The variant this paper is concerned with is the
parameterized pattern matching problem, introduced by Baker [
In this paper, we propose a new indexing structure for p-strings, which we call PLST. A PLST is a tree structure that combines a linear-size su x trie and a parameterized su x tree. We show that the size of a PLST is O(n) and give an algorithm for the parameterized pattern matching problem for given a pattern and a PLST, to nd the occurrences of a pattern in the text, that runs in O(m) time, where n is the length of the text and m is the length of the pattern. Furthermore, we experimentally show that PLSTs are more space e cient than parameterized su x trees for highly repetitive strings such as Fibonacci strings. 2 2.1
We denote the set of all non-negative integers by N . Let be an alphabet. For a string w = xyz 2 , x, y, and z are called pre x, substring, and su x of w, respectively. The length of w is denoted by jwj and the i-th symbol of w is denoted by w[i] for 1 i jwj. The substring of w that begins at position i and ends at position j is denoted by w[i : j] for 1 i j jwj. For convenience, we abbreviate w[1 : i] to w[: i] and w[i : jwj] to w[i :] for 1 i jwj. The empty string is denoted by ", that is j"j = 0. Moreover, let w[i : j] = " if i > j. For a string u and an extension uv, we write str(u; uv) = v.
Throughout this paper, we x two alphabets and . We call elements of constant symbols and those of parameter symbols. An element of is called a constant string and that of ( [ ) is called a parameterized string, or p-string for short. We assume that the size of and are constant.
Given two p-strings w1 and w2 of length n, w1 and w2 are a parameterized match (p-match), denoted by w1 w2, if there is a bijection f on such that f (a) = a for any a 2 determine whether w1 de ned as follows.
and f (w1[i]) = w2[i] for all 1 i n [
; We call strings over [ N pv-strings.
and w[i] 6= w[j] for 1 j < i; and k = maxfj j w[j] = w[i] and 1 j < ig:
For any p-strings w1 and w2, w1 w2 if and only if prev(w1) = prev(w2). For example, given = fa; bg and = fu; v; x; yg, s1 = uvvvauuvb and s2 = xyyyaxxyb are p-matches by f such that f (u) = x and f (v) = y, where prev(s1) = prev(s2) = 0011a514b.
We de ne parameterized pattern matching as follows.
text T and pattern P , decide whether T has a substring that p-matches P . $ 2 For example, considering a text T = auvaubuavbv and a pattern P = xayby over = fa; bg and = fu; v; x; yg, T has two substrings T [3 : 7] = vaubu and T [7 : 11] = uavbv that p-match P .
Throughout this paper, we assume that a text T ends with a sentinel symbol , which occurs nowhere else in T . 2.2
This subsection brie y reviews tree structures for indexing all the substrings of a constant string T 2 .
The su x trie STrie(T ) is a tree with nodes corresponding to all the substrings of T . Figure 1 (a) shows an example of a su x trie. Throughout this paper, we identify a node with its corresponding string for explanatory convenience. Note that each node does not explicitly remember its corresponding string. For each nonempty substring ua of T where a 2 , we have an edge from u to ua labeled with a. Then by reading the labels on the path from the root to a node u, one can obtain the string u the node corresponds. Then the path label from the node u to a descendant uv is str(u; uv) = v for u; v 2 . Since there are (jT j2) substrings of T , the size of STrie(T ) is (jT j2).
The su x tree STree(T ) is a tree obtained from STrie(T ) by removing all non-branching internal nodes and replacing each path with no branching nodes by a single edge whose label refers to a corresponding interval of the text T . That is, the label on the edge (u; v) is a pair (i; j) such that T [i : j] = str(u; v). $ a a b a $ a $ a b a $ b a $ a b $ a a b $ a a
$ (a) + $ a a b a + $ a $ a b a $ b a $ a b $ a a b + $ a a+
$ (b) Since there are at most O(jT j) branching nodes, the size of STree(T ) is (jT j). An important auxiliary map on nodes is called su x links, denoted by SL, which is de ned by SL(aw) = w for each node aw with a 2 and w 2 .
The linear-size su x trie (LST) [
[
Usually su x links are de ned on nodes of su x trees, but it is convenient to have \implicit su x links" on all nodes except the root of STrie(T ), i.e., all the nonempty substrings of T , as well. For a nonempty pv-string u 2 ( [ N )+, let sl(u) denote the re-encoding hu[2 :]i of the string obtained by deleting the rst symbol. This operation on strings will de ne real su x links in indexing structures for parameterized strings based on parameterized su x tries. Di erently from constant strings, u 2 PrevSub(T ) does not necessarily imply u[2 :] 2 PrevSub(T ). What we actually have is sl(u) = hu[2 :]i 2 PrevSub(T ).
A parameterized su x tree (p-su x tree) [
We now introduce our indexing tree structures for p-strings, which we call PLSTs, based on LSTs and p-su x trees reviewed in Sections 2.2 and 2.3. There are two di culties in extending LSTs to deal with p-strings. Figure 3(a) shows the LST-like structure obtained from PSTrie(T ) in the same way as LST(T ) is obtained from STrie(T ). We want to know str(u; v) for an edge (u; v) by \reduction by su x links", but 1. it is not necessarily that str(u; v) = str(sl(u); sl(v)), 2. there can be a branching node u of PSTrie(T ) such that sl(u) is not branching. An example edge (u; v) exhibiting the rst di culty consists of u = 00 and v = 00b3$, where str(u; v) = b3$ but str(sl(u); sl(v)) = b0$. This is caused by the fact that sl(u) = hu[2 :]i rather than sl(u) = u[2 :]. Then, the path label str(sl(u); sl(v)) referenced by the su x link may not give exactly what we want. We solve this problem by giving the node v a \re-encoding sign" with which one can recover str(u; v) from str(sl(u); sl(v)). An example node for the second case is 00ab. This is a branching node but hsl(00ab)i = 0ab does not appear as a node. To handle this case, we simply refer to the corresponding interval of the original text T by keeping the necessary subsequence, where, as we will observe in experiments, the necessary subsequence tends to be rather small. Our proposed structure PLST is shown in Figure 3(b). In what follows we explain PLSTs. 3.1
Let U = PrevSub(T ) be the set of nodes of PSTrie(T ). The set V of nodes of the
PLST PLST(T ) for T is a subset of U , which is partitioned as V = V1 [ V2 U .
Nodes in Vi are called Type i for i = 1; 2. The de nition of Type 1 and Type 2
nodes follows the one for original LSTs [
Edges of PLST(T ) are trivially determined: we have (u; uv) 2 V V as an edge if and only if v 6= " and there is no proper nonempty pre x v0 of v such that uv0 2 V . We will show in Section 3.3 that jV j 2 O(jT j). We say that u 2 V is good if sl(u) 2 V , and u 2 V is bad otherwise. Note that any u 2 V2 is good by the de nition of V2, and that the root " is bad.
To obtain str(u; v) for an edge (u; v), if jvj juj = 1, we simply read the edge
label v[
a ure, we check whether str(u; v) matches and the parent of v is u = 0a of length 2. pattern p = a04b using fast links.
For the node sl(v) = acb00, Re(sl(v)) = 0. substring of the original text T , like p-su x trees. However, di erently from psu
x trees, not every part of the original text is referenced by an edge in our case. We keep only the subsequence T 0 of T obtained by removing parts that are not referred to. We label an edge (u; v) connected to a bad node with an integer triple (i; j; k) such that str(u; v) = hT 0ik[i : j].
In summary, PLST(T ) consists of three kinds of nodes: good Type 1, bad Type 1, and Type 2 (all good). If u 2 V is a good node, u has its depth, su x link and re-encoding sign, i.e., the triple (juj; SL(u); Re(u)), where SL(u) = sl(u). Here we use the notation SL(u) to emphasize that the su x link SL(u) is a pointer to the node corresponding to the string sl(u) rather than the string itself. Therefore, it requires only constant size of memory space. If u 2 V is bad, u dose not have a su
x link, i.e., u has the triple (juj; null; Re(u)). Each
edge (u; v) has either a label character or triple; if both u and v are good or
str(u; v) = 1, the edge label is str(u; v)[
and ai 2
We remark that another idea to overcome the problem of the absence of sl(u) in a PLST for a node u might be to add sli(u) to V for all i = 1; : : : ; juj so that V is closed under sl, where sli(u) = sl(sli 1(u)) and sl0(u) = u. However, there exists for each i, for which the number of those additional nodes will be (jTnj2). Thus, the size of the index structures cannot be kept in linear. 3.2
This subsection presents our algorithm for solving the parameterized pattern matching problem as an application of PLSTs. The function P-Match of Algorithm 1 takes a prev-encoded string p and a node in PLST(T ) and checks whether there is v 2 PrevSub(T ) such that p = str(u; v). If it is the case, it returns the least extension v0 of v such that v0 2 V . In other words, p is a pre x of str(u; v0), where v0 should be v itself if v 2 V . Otherwise, it returns null.
For an input pair (p; u), if p = ", then P-Match returns u, as it is required.
Otherwise, it rst tries to regain str(u; v) for the p[
The above discussion is valid when jpj jvj juj. If Re(v) = 0 or Re(v) > jpj, then p is a pre x of str(u; v) i p is a pre x of str(sl(u); sl(v)). Otherwise, p is a pre x of str(u; v) i p[Re(v)] = juj + Re(v) 1 and p0 is a pre x of str(sl(u); sl(v)). Thus the recursion is justi ed. If P-Match(p0[1 : l]; SL(u)) returns a node, p is a pre x of str(u; v) and we call P-Match("; v), which returns v. Proposition 1. We can decide whether T has a substring that p-matches P using Algorithm 1.
The time complexity of Algorithm 1 is not linear as it is. Suppose that
P-Match(p; u) is called. It can be the case jvj juj jpj 2 and either
Re(v) = 0 or Re(v) > l where v = child(u; p[
Algorithm 1 will run in linear time by replacing SL(u) in Line 14 by FL(u; v). If jvkj < jvj k = jslk(v)j, the node vk occurs between slk(u) and slk(v). Then, P-Match(p; SLk(u)) will call P-Match(p[1 : jvkj jSLk(u)j]; SLk+1(u)). When
0 < Re(vk), we change the Re(vk)-th symbol of p, which must be a positive
integer, to 0. Therefore, the number of fast links we follow is bounded by 2jpj.
Figure 5 shows how to p-match str(u; v) and p = a04b using fast links. We know
that p[
We now show that the size of PLST(T ) is linear with respect to the length n of a
text T . First, we show a linear upper bound on the number of nodes of PLST(T ).
The nodes of Type 1 appear in the p-su x tree, so they are at most 2n [
De ne a binary relation R between V1 and V2 by R = f (u; v) 2 V1
V2 j there is i s.t. v = sli(u) and slj(u) 2= V2 for all j < i g and let R2 = f v 2 V2 j (u; v) 2 R for some u 2 V1 g. Since R is a partial function from branching nodes to Type 2 nodes, we have jR2j n. By the above argument on a chain, each chain has at most one Type 2 node v 2 V2 such that v 2= R2. Since there are n 1 chains, we have jV2 n R2j < n. All in all, jV2j = jR2j + jV2 n R2j < n + n = 2n. tu
The number of edges and their labels, as well as the number of su x links, depth and re-encoding sign for nodes, is asymptotically bounded above by the number of nodes in PLST(T ). T 0 is a subsequence of prev(T ), thus its length is O(n). Therefore, the size of PLST(T ) is O(n).
Theorem 2. Given a p-string T of length n, the size of PLST(T ) is O(n). 4
We performed comparative experiments on the number of nodes of PLSTs and p-su x trees for four sorts of text strings changing their length. Text strings we used are random strings of length n = 10; : : : ; 10240 over a constant alphabet with j j = 2 and those over a parameter alphabet with j j = 2, and the 11th through 22nd Fibonacci strings over with j j = 2 and those over with j j = 2. PLSTs for constant strings are of course identical to LSTs. For random strings, we measured the average number of nodes for 100 strings of each length. The results of our experiments are shown in Table 1. Recall that p-su x trees consist of Type 1 nodes and prev(T ), while PLSTs have Type 1 and Type 2 nodes and T 0. For random strings, we can see that the number of Type 2 nodes is close to the text length. Since a node requires much more memory size than a character, PLSTs will be bigger than p-su x trees for random strings. On the other hand, for Fibonacci strings, PLSTs have few Type 2 nodes and T 0 = . Thus, PLSTs will use less space than p-su x trees for Fibonacci strings.
In addition to Fibonacci strings, we constructed PLSTs for other kinds of
highly repetitive strings such as period-doubling and Thue-Morse strings [
In this paper, we presented an indexing structure called a PLST for the parameterized pattern matching problem. Given a p-string T of length n, the size of PLST for T is O(n). We presented an algorithm that solves the problem in O(m) time, where m is the length of the pattern. We experimentally showed that PLST is space-saving from p-su x tree for indexing highly repetitive strings.
For PLSTs to be useful for various applications, like computing the longest
common substrings, an e cient algorithm for constructing PLSTs is required
like LSTs [