Breaking a Barrier in Constructing Compact Indexes for Parameterized Pattern Matching

An integer interval $\{i,i+1,\dots,j\}$ is denoted by $[i..j]$, where $[i..j]$ represents the empty interval if $i>j$.

Let $\Sigma$ be an ordered finite alphabet. An element of $\Sigma^{*}$ is called a string over $\Sigma$. The length of a string $w$ is denoted by $|w|$. The empty string $\varepsilon$ is the string of length 0, that is, $|\varepsilon|=0$. Let $\Sigma^{+}=\Sigma^{*}-\{\varepsilon\}$ and $\Sigma^{k}=\{x\in\Sigma^{*}\mid|x|=k\}$ for any non-negative integer $k$. The concatenation of two strings $x$ and $y$ is denoted by $x\cdot y$ or simply $xy$. When a string $w$ is represented by the concatenation of strings $x$, $y$ and $z$ (i.e. $w=xyz$), then $x$, $y$ and $z$ are called a prefix, substring, and suffix of $w$, respectively. A substring $x$ of $w$ is called proper if $x\neq w$.

The $i$-th symbol of a string $w$ is denoted by $w[i]$ for $1\leq i\leq|w|$, and the substring of a string $w$ that begins at position $i$ and ends at position $j$ is denoted by $w[i..j]$ for $1\leq i\leq j\leq|w|$, i.e., $w[i..j]=w[i]w[i+1]\cdots w[j]$. For convenience, let $w[i..j]=\varepsilon$ if $j<i$; further let $w[..i]=w[1..i]$ and $w[i..]=w[i..|w|]$ denote abbreviations for the prefix of length $i$ and the suffix starting at position $i$, respectively. For two strings $x$ and $y$, let $\mathsf{lcp}(x,y)$ denote the length of the longest common prefix between $x$ and $y$. We consider the lexicographic order over $\Sigma^{*}$ by extending the strict total order $<$ defined on $\Sigma$: $x$ is lexicographically smaller than $y$ (denoted as $x<y$) if and only if either $x$ is a proper prefix of $y$ or $x[\mathsf{lcp}(x,y)+1]<y[\mathsf{lcp}(x,y)+1]$ holds.

For any string $w$, character $c$, and position $i~{}(1\leq i\leq|w|)$, $\mathsf{rank}_{c}(w,i)$ returns the number of occurrences of $c$ in $w[..i]$ and $\mathsf{select}_{c}(w,i)$ returns the $i$-th occurrence of $c$ in $w$. For $1\leq i\leq j\leq|w|$, a range minimum query $\mathsf{RmQ}_{w}(i,j)$ asks for $\arg\min_{i\leq k\leq j}\{w[k]\}$. We also consider find previous/next queries $\mathsf{FPQ}_{p}(w,i)$ and $\mathsf{FNQ}_{p}(w,i)$, where $p$ is a predicate either in the form of “$c$” (equal to $c$), “$<c$” (less than $c$) or “$\geq c$” (larger than or equal to $c$): $\mathsf{FPQ}_{p}(w,i)$ returns the largest position $j\leq i$ at which $w[j]$ satisfies the predicate $p$. Symmetrically, $\mathsf{FNQ}_{p}(w,i)$ returns the smallest position $j\geq i$ at which $w[j]$ satisfies the predicate $p$. For example with the integer string $w=[2,5,10,6,8,3,14,5]$, $\mathsf{FNQ}_{5}(w,4)=8$, $\mathsf{FNQ}_{6}(w,4)=4$, $\mathsf{FPQ}_{5}(w,4)=2$, $\mathsf{FNQ}_{<5}(w,4)=6$, $\mathsf{FPQ}_{<5}(w,4)=1$, $\mathsf{FNQ}_{\geq 9}(w,4)=7$ and $\mathsf{FPQ}_{\geq 9}(w,4)=3$.

If the answer of $\mathsf{select}_{c}(w,i)$, $\mathsf{FPQ}_{p}(w,i)$ or $\mathsf{FNQ}_{p}(w,i)$ does not exist, it is just ignored. To handle this case of non-existence, we would use them in an expression with $\min$ or $\max$: For example, $\max\{1,\mathsf{FPQ}_{p}(w,i)\}$ returns $1$ if $\mathsf{FPQ}_{p}(w,i)$ does not exist.

Dynamic strings should support insertion/deletion of a symbol to/from any position as well as fast random access. We use the following result:

Dynamic binary strings equipped with $\mathsf{rank}$ and $\mathsf{select}$ queries can be used as a building block for the dynamic wavelet matrix [5] of a string over an alphabet $[0..\sigma]$ to support queries beyond $\mathsf{rank}$ and $\mathsf{select}$. The idea is that each of the other queries can be simulated by performing one of the building block queries on every level of the wavelet matrix, which has $\lceil\lg\sigma\rceil$ levels, cf. [24, Section 6.2.].

Let $\Sigma_{s}$ and $\Sigma_{p}$ denote two disjoint sets of symbols. We call a symbol in $\Sigma_{s}$ a static symbol (s-symbol) and a symbol in $\Sigma_{p}$ a parameter symbol (p-symbol). A parameterized string (p-string) is a string over $(\Sigma_{s}\cup\Sigma_{p})$. Let $\infty$ represent a symbol that is larger than any integer, and let $\mathbf{N}_{\infty}=\mathbf{N}_{+}\cup\{\infty\}$ be the set of natural positive numbers $\mathbf{N}_{+}$ including infinity. We assume that $\mathbf{N}_{\infty}\cap\Sigma_{s}=\emptyset$ and $(\mathbf{N}_{\infty}\cup\Sigma_{s})$ is an ordered alphabet such that all s-symbols are smaller than any element in $\mathbf{N}_{\infty}$. Let $\$$ be the smallest s-symbol, which will be used as an end-marker of p-strings. For any p-string $w$ the p-encoded string $\langle w\rangle$ of $w$, also proposed as $\mathtt{prev}_{\infty}(w)$ in [18], is the string in $(\mathbf{N}_{\infty}\cup\Sigma_{s})^{|w|}$ such that

where $j$ is the largest position in $[1..i-1]$ with $w[i]=w[j]$. In other words, p-encoding transforms an occurrence of a p-symbol into the distance to the previous occurrence of the same p-symbol, or $\infty$ if it is the leftmost occurrence. By definition, p-encoding is prefix-consistent, i.e., $\langle w\rangle=\langle wc\rangle[..|w|]$ for any symbol $c\in(\Sigma_{s}\cup\Sigma_{p})$. On the other hand, $\langle w\rangle$ and $\langle cw\rangle[2..]$ differ if and only if $c\in\Sigma_{p}$ occurs in $w$. If it is the case, the leftmost occurrence $h$ of $c$ in $w$ is the unique position such that $\langle w\rangle$ and $\langle cw\rangle[2..]$ differ with $\langle w\rangle[h]=\infty$ and $(\langle cw\rangle[2..])[h]=\langle cw\rangle[h+1]=h$, i.e., $h=\mathsf{select}_{c}(w,1)$ and $h+1=\mathsf{select}_{c}(cw,2)$.

For any p-string $w$, let $|w|_{p}$ denote the number of distinct p-symbols in $w$, i.e., $|w|_{p}=\mathsf{rank}_{\infty}(\langle w\rangle,|w|)$. We define a function $\pi$ that maps a p-string $w$ over $(\Sigma_{s}\cup\Sigma_{p})$ to an element in $(\Sigma_{s}\cup[1..|w|_{p}])$ such that

where $h+1=\min\{|w|,\mathsf{select}_{w[1]}(w,2)\}$. In the second case, $\pi(w)$ represents the rank of p-symbol $w[1]$ when ordering all p-symbols by their leftmost occurrences in $w[2..]$, considering the rank of p-symbols not in $w[2..]$ to be $|w|_{p}$. If $\mathsf{select}_{w[1]}(w,2)$ exists, it holds that $h=\mathsf{select}_{\infty}(\langle w[2..]\rangle,\pi(w))$. For convenience, let $\pi(\varepsilon)=\$$.

For two p-strings $u$ and $v$, $\mathsf{lcp}^{\infty}(\langle u\rangle,\langle v\rangle)$ denotes the number of $\infty$’s in the longest common prefix of $\langle u\rangle$ and $\langle v\rangle$.

The following lemma states basic but important properties of the p-string encoding and $\pi$, which immediately follow from the definition (see Fig. 1 for illustrations).

By Lemma 4, we have the following corollaries:

Let $T$ be a p-string that has the smallest s-symbol $\$$ as its end-marker, i.e., $T[|T|]=\$$ and $\$$ does not appear anywhere else in $T$. The suffix rank function $\mathsf{R}_{T}:[1..|T|]\rightarrow[1..|T|]$ for $T$ maps a position $i~{}(1\leq i\leq|T|)$ to the lexicographic rank of $\langle T[i..]\rangle$ in $\{\langle T[j..]\rangle\mid 1\leq j\leq|T|\}$. Its inverse function $\mathsf{R}^{-1}_{T}(i)$ returns the starting position of the lexicographically $i$-th p-encoded suffix of $T$.

The main components of parameterized Burrows-Wheeler Transform (pBWT) of $T$ are $\mathsf{F}_{T}$ and $\mathsf{L}_{T}$. $\mathsf{F}_{T}$ (resp. $\mathsf{L}_{T}$) is defined to be the string of length $|T|$ such that $\mathsf{F}_{T}[i]=\pi(T[\mathsf{R}^{-1}_{T}(i)..])$ (resp. $\mathsf{L}_{T}[i]=\pi(T[\mathsf{R}^{-1}_{T}(i)-1..])$), where we assume that $T[0..]=\$$. ¹¹1Previous studies [14, 18, 16] define pBWTs based on sorted cyclic rotations, but our suffix-based definition is more suitable for online construction to prevent unnecessary update on $\mathsf{F}_{T}$ and $\mathsf{L}_{T}$. Since $\{T[\mathsf{R}^{-1}_{T}(i)..]\mid 1\leq i\leq|T|\}=\{T[\mathsf{R}^{-1}_{T}(i)-1..]\mid 1\leq i\leq|T|\}$ is equivalent to the set of all non-empty suffixes of $T$, $\mathsf{F}_{T}$ is a permutation of $\mathsf{L}_{T}$.

The so-called LF-mapping $\mathsf{LF}_{T}$ maps a position $i$ to $\mathsf{R}_{T}(\mathsf{R}^{-1}_{T}(i)-1)$ if $\mathsf{R}^{-1}_{T}(i)>1$, and otherwise $\mathsf{R}_{T}(|T|)=1$. By definition and Corollary 6, we have:

Thanks to Corollary 8, it holds that $\mathsf{LF}_{T}(i)=\mathsf{select}_{c}(\mathsf{F}_{T},\mathsf{rank}_{c}(\mathsf{L}_{T},i))$, where $c=\mathsf{L}_{T}[i]$. The inverse function $\mathsf{FL}_{T}$ of $\mathsf{LF}_{T}$ can be computed by $\mathsf{FL}_{T}(i)=\mathsf{select}_{c}(\mathsf{L}_{T},\mathsf{rank}_{c}(\mathsf{F}_{T},i))$, where $c=\mathsf{F}_{T}[i]$.

Let $\mathsf{LCP}^{\infty}_{T}$ be the string of length $|T|$ such that $\mathsf{LCP}^{\infty}_{T}[0]=0$ and $\mathsf{LCP}^{\infty}_{T}[i]=\mathsf{lcp}^{\infty}(T[\mathsf{R}^{-1}_{T}(i-1)..],T[\mathsf{R}^{-1}_{T}(i)..])$ for any $1<i\leq|T|$. An example of all explained arrays is given in Table 2.

Unlike the existing work [16] that computes $\hat{k}$ by counting the number of p-encoded suffixes that are lexicographically smaller than $\langle\hat{T}\rangle$, we get $\hat{k}$ indirectly by computing the rank of a lexicographically closest (smaller or larger) p-encoded suffix to $\langle\hat{T}\rangle$. The lexicographically smaller (resp. larger) closest element in $\{\langle T[i..]\rangle\mid 1\leq i\leq|T|\}$ to $\langle\hat{T}\rangle$ is called the p-pred (resp. p-succ) of $\langle\hat{T}\rangle$. and its rank is denoted by $k_{-}$ (resp. $k_{+}$). Then it holds that $\hat{k}=k_{+}=k_{-}+1$.

We start with the easy case that the prepended symbol $c$ is an s-symbol.

In the rest of this subsection, we consider the case that $c$ is a p-symbol. If $T$ contains no p-symbol, it is clear that $k_{-}=|T|$. Hence, in what follows, we assume that there is a p-symbol in $T$.

Since $\langle\hat{T}\rangle$ has the longest $\mathsf{lcp}$-value $\hat{\lambda}$ with its p-pred or p-succ, we search for such p-encoded suffixes of $T$ using the following lemmas to leverage the information stored in $\mathsf{LCP}^{\infty}_{T}$.