R-Enum Revisited: Speedup and Extension for Context-Sensitive Repeats and Net Frequencies

Context-sensitive repeats are closely related to and efficiently computed from suffix data structures. A folklore algorithm [17] uses suffix trees. To reduce the (rather big) working space of suffix trees by a constant factor, algorithms based on enhanced suffix arrays [1] have been proposed. A compact- or compressed-space solution can be achieved by using LF-mapping and range distinct queries (see Section 2) on BWTs or RLBWTs to simulate a traversal on suffix link trees. Table 1 summarizes representative algorithms.

The study for net frequencies/occurrences was initiated recently by Guo et al. [14]. Given a string $T$ of length $n$ over an integer alphabet of size $\sigma =n^{O(1)}$, we can perform All-NF in $O(n)$ time and words of space using an algorithm [31, 32] based on enhanced suffix arrays. The problem has also been studied in an online setting, where we maintain a data structure to perform All-NF and Single-NF while allowing monotonic updates to the left and/or right ends of $T$. The current state-of-the-art online algorithm [25] is based on online construction of implicit suffix trees and implicit CDAWGs. In this paper, we achieve the first offline algorithm for All-NF and Single-NF that works in $O(r)$ words of compressed space.

This paper is organized as follows. In Section 2, we introduce notation and tools we use in the following sections. In Section 3, we prove that the total number of net occurrences is less than $2r$, which is crucial to bound the time and space complexities of our algorithms for net frequencies/occurrences. In Section 4, we speed up r-enum and extend it to enumerate other context-sensitive repeats. In Section 5, we present an $O(r)$-space data structure for NF-queries based on RLBWTs. In Section 6, we conclude the paper with some remarks.

We assume a standard word-RAM model with word size $w=\mathrm{\Theta }(\log n)$, where $n$ is the length of string $T$ defined later. A space complexity is evaluated by the number of words unless otherwise noted. Any integer treated in this paper is represented in $O(1)$ space, i.e., $O(w)$ bits. A set of consecutive integers is called an interval, which can be represented in $O(1)$ space by storing its beginning and ending integers. For two integers $b$ and $e$, let $[b..e]$ denote the interval $\{b,b+1,\mathrm{\dots },e\}$ beginning at $b$ and ending at $e$ if $b\le e$, and otherwise, the empty set. We also use $[b..e):=[b..e-1]$ to exclude the right-end integer.

A string (or an array) $x$ over a set $S$ is a sequence $x[1]x[2]\mathrm{\cdots }x[|x|]$, where $|x|$ denotes the length of $x$ and $x[i]\in S$ is the $i$-th element of $x$ for any $i\in [1..|x|]$. The string of length $0$ is called the empty string and denoted by $\epsilon$. Let $S^{\ast }$ denote the set of strings over $S$, and let $S^n\subset S^{\ast }$ be the set of strings of length $n\ge 0$. For integers $1\le b\le e\le |x|$, the substring of $x$ beginning at $b$ and ending at $e$ is denoted by $x[b..e]=x[b]x[b+1]\mathrm{\cdots }x[e]$. For convenience, let $x[b..e]$ with $b>e$ represent the empty string. We also use $x[b..e)=x[b..e-1]$ to exclude the right-end character. A prefix (resp. suffix) of $x$ is a substring that matches $x[1..e]$ (resp. $x[b..|x|]$) for some $e\in [0..|x|]$ (resp. $b\in [1..|x|+1]$). We use the abbreviation $x[..e]=x[1..e]$ and $x[b..]=x[b..|x|]$. For a non-negative integer $d$, let $x^d$ denote the string of length $|x|d$ such that $x^d[|x|(i-1)+1..i|x|]=x$ for any $i\in [1..d]$.

A function that injectively maps a set $S$ of integers to $[1..O(|S|)]$ can be used as a compact dictionary for $S$ to look up a value associated with an integer in $S$. We use the following known result:

A predecessor query for an integer $i$ over the set $S$ of integers asks to compute $\max \{j\in S\mid j\le i\}$, which can be efficiently supported by the data structure of [5, Appendix A]:

A range distinct query $\mathrm{𝖱𝖣}(x,p,q)$ for a string $x$ and integers $1\le p\le q\le |x|$ asks to enumerate $(c,p_c,q_c)$ such that $p_c$ and respectively $q_c$ are the smallest and largest positions in $[p..q]$ with $x[p_c]=x[q_c]=c$ for every distinct character $c$ that occurs in $x[p..q]$. It is known that a range distinct query can be supported in output-optimal time after preprocessing $x$.

A minor remark is that the output of range distinct queries of Lemma 3 may not be sorted in any order of characters.

Let ${\mathrm{\Sigma }}_{\$}=[1..\sigma ]$ be an ordered alphabet with the smallest character $\$$, and let $\mathrm{\Sigma }={\mathrm{\Sigma }}_{\$}\setminus \{\$\}$. Throughout this paper, $T[1..n]\in {\mathrm{\Sigma }}_{\$}^n$ is a string of length $n\ge 2$ that contains all characters in ${\mathrm{\Sigma }}_{\$}$. ¹¹1If $T$ is a string over a larger inefficient alphabet, we first replace every occurrence of a character with its rank in the character set actually used in $T$ to satisfy the assumption. Given the RLBWT of $T$ of size $r$, this task can be done in $O(n)$ time and $O(r)$ space using the sorting algorithm of [29, Lemma 13]. We assume for convenience that $\$$ is used as a sentinel that exists at $T[n]$ and $T[0]$, and does not occur in $T[1..n-1]$. A position $b\in [1..n]$ is called an occurrence of a string $x\in {\mathrm{\Sigma }}_{\$}^{\ast }$ in $T$ if $T[b..b+|x|)=x$. Let $\mathrm{𝖮𝖼𝖼}(x)$ denote the set of occurrences of $x$ in $T$. The left context $\mathrm{𝗅𝖼}(x)$ (resp. right context $\mathrm{𝗋𝖼}(x)$) of a substring $x\in {\mathrm{\Sigma }}^{\ast }$ of $T$ is the set of characters immediately precedes (resp. follows) the occurrences of $x$, i.e., $\mathrm{𝗅𝖼}(x)=\{T[b-1]\mid b\in \mathrm{𝖮𝖼𝖼}(x)\}$ (resp. $\mathrm{𝗋𝖼}(x)=\{T[b+|x|]\mid b\in \mathrm{𝖮𝖼𝖼}(x)\}$). The context diversity of $x$ is the pair $(|\mathrm{𝗅𝖼}(x)|,|\mathrm{𝗋𝖼}(x)|)$ of integers in $[1..\sigma ]$. A substring $x$ of $T$ is called a repeat if $|\mathrm{𝖮𝖼𝖼}(x)|\ge 2$, and called unique if $|\mathrm{𝖮𝖼𝖼}(x)|=1$. A repeat $x\in {\mathrm{\Sigma }}^{\ast }$ in $T$ is a left-maximal repeat (LMR) (resp. right-maximal repeat (RMR)) if $|\mathrm{𝗅𝖼}(x)|>1$ (resp. $|\mathrm{𝗋𝖼}(x)|>1$), and is a maximal repeat (MR) if $x$ is both left- and right-maximal. A repeat $x$ in $T$ is a supermaximal repeat (SMR) if it is not a substring of another repeat. An occurrence $b$ of a repeat $x$ is called a net occurrence if there is no occurrence $b^{\prime }$ of another repeat $x^{\prime }$ such that $[b..b+|x|)\subset [b^{\prime }..b^{\prime }+|x^{\prime }|)$. Let $\mathrm{𝖭𝖮𝖼𝖼}(x)\subseteq \mathrm{𝖮𝖼𝖼}(x)$ be the set of net occurrences of $x$ and let $\mathrm{𝖭𝖥}(x):=|\mathrm{𝖭𝖮𝖼𝖼}(x)|$ be the number of net occurrences called the net frequency of $x$. A near-supermaximal repeat (NSMR) is a repeat with a positive net frequency. Let $𝒮$, ${𝒮}^{𝗋}$, ${𝒮}^{\mathrm{𝗅𝗆𝗋}}$, ${𝒮}^{\mathrm{𝗋𝗆𝗋}}$, ${𝒮}^{\mathrm{𝗆𝗋}}$, ${𝒮}^{\mathrm{𝗇𝗌𝗆𝗋}}$ and ${𝒮}^{\mathrm{𝗌𝗆𝗋}}$ be the sets of all substrings, repeats, LMRs, RMRs, MRs, NSMRs and SMRs in $T[1..n]$, respectively.

To describe algorithms uniformly, we assume that the empty string is a repeat that occurs at every position $b$ in $[1..n]$, i.e., $\mathrm{𝖮𝖼𝖼}(\epsilon )=[1..n]$. Since $\mathrm{𝗅𝖼}(\epsilon )=\mathrm{𝗋𝖼}(\epsilon )={\mathrm{\Sigma }}_{\$}$, $\epsilon$ is always in ${𝒮}^{\mathrm{𝗅𝗆𝗋}}$, ${𝒮}^{\mathrm{𝗋𝗆𝗋}}$ and ${𝒮}^{\mathrm{𝗆𝗋}}$. We set the following exception for the definition of net occurrences of $\epsilon$: An occurrence $b\in \mathrm{𝖮𝖼𝖼}(\epsilon )$ is a net occurrence of $\epsilon$ if and only if $T[b-1]$ and $T[b]$ are both unique. This exception provides a smooth transition to another characterization of net occurrences based on the uniqueness of extended net occurrences [14, 25].

Table 3 summarizes the concepts introduced in this subsection for $T=\mathrm{𝚊𝚋𝚌𝚋𝚋𝚌𝚋𝚌𝚊𝚋𝚌}\$$.

The suffix trie of $T$ is the tree defined on the set $𝒮$ of nodes and edges from $x\in 𝒮$ to $xc\in 𝒮$ with $c\in {\mathrm{\Sigma }}_{\$}$. The suffix tree of $T$ is the compacted suffix trie in which every non-branching internal node of the suffix trie is removed and considered to be an implicit node. Every internal node of the suffix tree is a right-maximal repeat $x$ and has $|\mathrm{𝗋𝖼}(x)|$ children. A link from a node $x$ to a (possibly implicit) node $ax\in 𝒮$ for some $a\in {\mathrm{\Sigma }}_{\$}$ is called a Weiner link. It is known that every node can be reached by following Weiner links from the root $\epsilon$, and the total number of Weiner links is at most $3n$, which can be seen from the duality between suffix trees and DAWGs [8].

The suffix array $\mathrm{𝖲𝖠}[1..n]$ of $T$ is the integer array such that, for any $i\in [1..n]$, $T[\mathrm{𝖲𝖠}[i]..]$ is the lexicographically $i$-th suffix among the non-empty suffixes of $T$. For any string $x\in 𝒮$, the SA-interval of $x$, denoted by $ℐ(x)$, is the maximal interval $[p..q]$ such that $x$ is a prefix of $T[\mathrm{𝖲𝖠}[i]..]$ for any $i\in [p..q]$. Then, it holds that $\mathrm{𝖮𝖼𝖼}(x)=\{\mathrm{𝖲𝖠}[i]\mid i\in ℐ(x)\}$.

The Burrows-Wheeler transform (BWT) $𝖫[1..n]$ of $T$ is the string such that $𝖫[i]=T[\mathrm{𝖲𝖠}[i]-1]$ for any $i\in [1..n]$. Note that $T[\mathrm{𝖲𝖠}[i]-1]=T[0]=\$$ for $i$ with $\mathrm{𝖲𝖠}[i]=1$ due to the sentinel at $T[0]$. By definition, it holds that $\mathrm{𝗅𝖼}(x)=\{𝖫[i]\mid i\in ℐ(x)\}$ for any string $x$. The LF-mapping $\mathrm{𝖫𝖥}$ is the permutation on $[1..n]$ such that $\mathrm{𝖫𝖥}(i)$ represents the lexicographic rank of the suffix $T[\mathrm{𝖲𝖠}[i]-1..]$ if $\mathrm{𝖲𝖠}[i]\ne 1$, and otherwise $\mathrm{𝖫𝖥}(i)=1$. The FL-mapping $\mathrm{𝖥𝖫}$ is the inverse mapping of $\mathrm{𝖫𝖥}$. Given an integer $i$ in $ℐ(x)$ for a string $x$, we can compute $x$ by using FL-mapping $|x|$ times from $i$ because $x[k]=𝖫[{\mathrm{𝖥𝖫}}^k(i)]$ holds for any $k(1\le k\le |x|)$, where ${\mathrm{𝖥𝖫}}^k(i)$ is defined recursively ${\mathrm{𝖥𝖫}}^k(i)=\mathrm{𝖥𝖫}({\mathrm{𝖥𝖫}}^{k-1}(i))$ with the base case ${\mathrm{𝖥𝖫}}^1(i)=\mathrm{𝖥𝖫}(i)$.

Table 3 shows an example of $\mathrm{𝖲𝖠}$, $\mathrm{𝖫𝖥}(\cdot )$, $\mathrm{𝖥𝖫}(\cdot )$ and $𝖫$ for $T=\mathrm{𝚊𝚋𝚌𝚋𝚋𝚌𝚋𝚌𝚊𝚋𝚌}\$$. Figure 1 also illustrates the suffix tree of $T=\mathrm{𝚊𝚋𝚌𝚋𝚋𝚌𝚋𝚌𝚊𝚋𝚌}\$$ and a relationship between Weiner links and BWTs.

The run-length encoded BWT (RLBWT) of $T$ represents $𝖫$ in $O(r)$ space by string ${𝖫}^{\prime }[1..r]\in {\mathrm{\Sigma }}_{\$}^r$ and array $𝖽[1..r]\in {[1..n]}^r$ such that $𝖫={𝖫}^{\prime }{[1]}^{𝖽[1]}{𝖫}^{\prime }{[2]}^{𝖽[2]}\mathrm{\dots }{𝖫}^{\prime }{[r]}^{𝖽[r]}$ and ${𝖫}^{\prime }[i]\ne {𝖫}^{\prime }[j]$ for any . Each component ${𝖫}^{\prime }{[i]}^{𝖽[i]}$ is called a run of $𝖫$. While $r\le n$ is obvious, inequality $\sigma \le r$ holds under the assumption that $T$ contains all characters in ${\mathrm{\Sigma }}_{\$}$.

A notable property of $\mathrm{𝖫𝖥}$ is that $\mathrm{𝖫𝖥}(i)=k_1+k_2$ holds, where $k_1$ is the number of characters smaller than $𝖫[i]$ in $𝖫$ and $k_2$ is the number of occurrences of $𝖫[i]$ in $𝖫[1..i]$. In particular, if $𝖫[p..q]$ consists of a single character, then $\mathrm{𝖫𝖥}(i)=\mathrm{𝖫𝖥}(p)+i-p$ for any $i\in [p..q]$, and $\mathrm{𝖥𝖫}(i^{\prime })=\mathrm{𝖥𝖫}(p^{\prime })+i^{\prime }-p^{\prime }$ for any $i^{\prime }\in [p^{\prime }..q^{\prime }]$ with $p^{\prime }=\mathrm{𝖫𝖥}(p)$ and $q^{\prime }=\mathrm{𝖫𝖥}(q)$. Hence, LF-mapping can be implemented in $O(r)$ space by constructing the predecessor data structure for the set of beginning positions of runs of $𝖫$ and remembering the $\mathrm{𝖫𝖥}(\cdot )$ values for those positions (FL-mapping can be implemented similarly). Using the predecessor data structure of Lemma 2, we get:

Nishimoto and Tabei [28] proposed a novel data structure, called the move data structure, to implement LF-mapping by a simple linear search on a list of intervals without predecessor queries. We consider a list $[p_1..p_2),[p_2..p_3),\mathrm{\dots },[p_{\widehat{r}}..p_{\widehat{r}+1})$ of $\widehat{r}=O(r)$ intervals such that $p_1=1$, $p_{\widehat{r}+1}=n+1$, and for any $k\in [1..\widehat{r}]$, $𝖫[p_k..p_{k+1})$ consists of a single character and $[\mathrm{𝖫𝖥}(p_k)..\mathrm{𝖫𝖥}(p_{k+1}-1)]$ intersects with $O(1)$ intervals in the list. We let each $[p_k..p_{k+1})$ have a pointer to the interval $[p_{k^{\prime }}..p_{k^{\prime }+1})$ that contains $\mathrm{𝖫𝖥}(p_k)$ and offset $o_k=\mathrm{𝖫𝖥}(p_k)-p_{k^{\prime }}$. Then, $\mathrm{𝖫𝖥}(i)=\mathrm{𝖫𝖥}(p_k)+i-p_k=p_{k^{\prime }}+o_k+i-p_k$ holds for any $i\in [p_k..p_{k+1})$. Given $i$ and interval $[p_k..p_{k+1})$ that contains $i$, we can compute $\mathrm{𝖫𝖥}(i)$ and find the interval that contains $\mathrm{𝖫𝖥}(i)$ by assessing $O(1)$ intervals from $[p_{k^{\prime }}..p_{k^{\prime }+1})$ to the right in the list. Note that $\mathrm{𝖫𝖥}(i)$ computation on the move data structure works along with the pointer to the interval in the list that contains $i$, which is handled implicitly hereafter. Under the assumption that $\sigma \le r$ in this paper, we can construct the data structure needed for LF-mapping (and FL-mapping) in $O(r\log r)$ time [29, Appendix D]:

Conceptually, r-enum performs a breadth-first traversal on the internal nodes ${𝒮}^{\mathrm{𝗋𝗆𝗋}}$ of the suffix tree by following Weiner links using RLBWT-based data structures. Each node $x\in {𝒮}^{\mathrm{𝗋𝗆𝗋}}$ is visited with its suffix interval $ℐ(x)$ and length $|x|$ together with the information about its right extensions $\mathrm{𝗋𝗅𝗂𝗌𝗍}(x)$, which is the list of the set $\{(c,ℐ(xc))\mid c\in \mathrm{𝗋𝖼}(x)\}$ sorted by the character $c$. The triplet $\mathrm{𝗋𝖾𝗉𝗋}(x)=(ℐ(x),\mathrm{𝗋𝗅𝗂𝗌𝗍}(x),|x|)$ is called the rich representation [4, 30] of $x$, which can be stored in $O(|\mathrm{𝗋𝖼}(x)|)$ space.

Given $\mathrm{𝗋𝖾𝗉𝗋}(x)=([p..q],{\{(c_i,[p_i..q_i])\}}_{i=1}^k,|x|)$, we can compute $\{\mathrm{𝗋𝖾𝗉𝗋}(ax)\mid ax\in 𝒮,a\in \mathrm{\Sigma }\}$ as follows: A null-initialized array $A[1..\sigma ]$ is used as a working space to build $\mathrm{𝗋𝗅𝗂𝗌𝗍}(ax)$ at $A[a]$ for $a\in \mathrm{𝗅𝖼}(x)\setminus \{\$\}$. For every $i\in [1..k]$, we compute $\mathrm{𝗅𝖼}(x{c}_i)$ by a range distinct query on $𝖫[p_i..q_i]$, and for each $a\in \mathrm{𝗅𝖼}(x{c}_i)\setminus \{\$\}$ we compute $ℐ(ax{c}_i)$ by LF-mapping and append $(c_i,ℐ(ax{c}_i))$ to the list being built at $A[a]$. After processing all $i\in [1..k]$, $A[a]$ becomes $\mathrm{𝗋𝗅𝗂𝗌𝗍}(ax)$. Finally, we enumerate $\mathrm{𝗅𝖼}(x)$ by a range distinct query on $𝖫[p..q]$ to go through only the used entries of $A$ to compute $\mathrm{𝗋𝖾𝗉𝗋}(ax)$ and clear the entries. For the next round of the breadth-first traversal on ${𝒮}^{\mathrm{𝗋𝗆𝗋}}$, we keep only the set $\{\mathrm{𝗋𝖾𝗉𝗋}(ax)\mid ax\in {𝒮}^{\mathrm{𝗋𝗆𝗋}}\}$, discarding $\mathrm{𝗋𝖾𝗉𝗋}(ax)$ if $\mathrm{𝗋𝗅𝗂𝗌𝗍}(ax)$ contains only one element.

R-enum executes the above procedure in $O(r)$ space using range distinct queries on ${𝖫}^{\prime }[1..r]$ and RLBWT-based LF-mapping. The breadth-first traversal on ${𝒮}^{\mathrm{𝗋𝗆𝗋}}$ can be made in $O(r)$ space because the space needed to store the rich representations for all strings in $\{ax\in 𝒮\mid a\in \mathrm{\Sigma },x\in {𝒮}^{\mathrm{𝗋𝗆𝗋}},|x|=t\}$ for any $t\in [0..n]$ was proved to be $O(r)$ in Section 3.3 of [30]. The total number of outputs of range distinct queries is upper bounded by $O(n)$ because each output can be charged to a distinct Weiner link. Similarly, the total number of LF-mapping needed is bounded by $O(n)$.

The original r-enum used Lemma 5 to implement LF-mapping and runs in $O(n\log {\log }_w(n/r))$ time in total (excluding the time to output patterns for MAWs). We show that this can be improved to $O(n)$ time.

In this subsection, we extend r-enum to compute the NSMRs and SMRs, and the context diversity for every RMR. Since ${𝒮}^{\mathrm{𝗌𝗆𝗋}}\subseteq {𝒮}^{\mathrm{𝗇𝗌𝗆𝗋}}\subseteq {𝒮}^{\mathrm{𝗆𝗋}}\subseteq {𝒮}^{\mathrm{𝗋𝗆𝗋}}$ holds, for enumerating SMRs (resp. NSMRs), it is enough to check every element in ${𝒮}^{\mathrm{𝗋𝗆𝗋}}$ if it is in ${𝒮}^{\mathrm{𝗌𝗆𝗋}}$ (resp. ${𝒮}^{\mathrm{𝗇𝗌𝗆𝗋}}$).

Recall that r-enum traverses $x\in {𝒮}^{\mathrm{𝗋𝗆𝗋}}$ while computing $\{\mathrm{𝗋𝖾𝗉𝗋}(ax)\mid ax\in 𝒮\}$ from $\mathrm{𝗋𝖾𝗉𝗋}(x)=([p..q],{\{(c_i,[p_i..q_i])\}}_{i=1}^k,|x|)$. First, we can compute the context diversity $(|\mathrm{𝗅𝖼}(x)|,|\mathrm{𝗋𝖼}(x)|)$ of $x\in {𝒮}^{\mathrm{𝗋𝗆𝗋}}$ because $|\mathrm{𝗋𝖼}(x)|$ is $k$ and $|\mathrm{𝗅𝖼}(x)|$ is the number of outputs of a range distinct query on $𝖫[p..q]$. Since $x$ is an SMR if and only if $|\mathrm{𝗅𝖼}(x)|=|\mathrm{𝗋𝖼}(x)|=|\mathrm{𝖮𝖼𝖼}(x)|=q-p+1$, the context diversity has enough information to choose SMRs from RMRs. On the other hand, NSMRs cannot be determined from the context diversities.

To determine if $x\in {𝒮}^{\mathrm{𝗋𝗆𝗋}}$ is an NSMR or not, we check if there is a net occurrence of $x$ in $\{\mathrm{𝖲𝖠}[j]\mid j\in [p..q]\}$ using the array $A[1..\sigma ]$ that stores $\mathrm{𝗋𝗅𝗂𝗌𝗍}(ax)$ at $A[a]$ for any $a\in \mathrm{𝗅𝖼}(x)\setminus \{\$\}$. Thanks to Lemma 7, we only have to consider $\mathrm{𝖲𝖠}[p_i]$ for intervals $[p_i..q_i]$ with $p_i=q_i$ as candidates of net occurrences. For an interval $[p_i..q_i]$ with $p_i=q_i$, we check if $a=𝖫[p_i]$ is $\$$ or $ℐ(ax)$ computed in $A[a]$ is a singleton, and then, $\mathrm{𝖲𝖠}[p_i]$ is a net occurrence if and only if the condition holds. We can also compute $\mathrm{𝖭𝖮𝖼𝖼}(x)$ if we store $\mathrm{𝖲𝖠}[i]$ for all run’s boundaries $i$, which can be precomputed using LF-mapping $O(n)$ times.

Since we can check the conditions for NSMRs and SMRs along with the traversal of ${𝒮}^{\mathrm{𝗋𝗆𝗋}}$, the time and space complexities of r-enum are retained.