Text Indexing for Simple Regular Expressions

Let ${𝒟}_k$ be the set of subsets $D\subseteq \mathrm{\Sigma }$ of size $k$ that occur as a $k$-run in $T$. Our data structure consists of the following:

• $\mathrm{■}$

  The suffix tree $𝒯$ of $T$ and the suffix tree ${𝒯}^{rev}$ of the reversed text, $T^{rev}$.

• $\mathrm{■}$

  A data structure $S_D$ for each set $D\in {𝒟}_k$ indexing all the text positions $P_D=\{i|D_{i,k}=D\}$. The structure consists of an orthogonal range reporting data structure for a four-dimensional grid in ${[1..n]}^4$ with $|P_D|$ points, one per $k$-run $[i..j]$ with $i\in P_D$. For each such $k$-run $[i..j]$ we store a point with coordinates $(x_i,y_i,z_i,j-i+1)$, where

  • –

    $x_i$ is the lexicographic rank of $T{[1..i-1]}^{rev}$ among all the reversed prefixes of $T$.

  • –

    $y_i$ is the lexicographic rank of $T{[1..j]}^{rev}$ among all the reversed prefixes of $T$.

  • –

    $z_i$ is the lexicographic rank of $T[j+1..n]$ among all the suffixes of $T$.

  Each point stores the limits $[i..j]$ of its $k$-run (so as to report occurrence positions).

• $\mathrm{■}$

  A trie ${\tau }_k$ storing all the strings $s_D$ of length $k$ formed by sorting in increasing order the $k$ characters of $D$, for every $D\in {𝒟}_k$.

Note that the fourth coordinate $j-i+1$ of point $(x_i,y_i,z_i,j-i+1)$ could be avoided (i.e. using a 3D range reporting data structure) by defining $y_i$ to be the lexicographic rank of $T{[1..j]}^{rev}\$$ (where $\$$ is a special terminator character) in the set formed by all the reversed prefixes of $T$ and strings of the form $T{[1..j]}^{rev}\$$, for all $k$-runs $T[i..j]$. While this solution would work in the same asymptotic space and query time (because we will only need one-sided queries on the fourth coordinate), we will need the fourth dimension in Subsection 3.4.

At query time, we first compute ${\mathrm{pref}}_D(P_2)$. For any occurrence of the query pattern, ${\mathrm{pref}}_D(P_2)$ will necessarily be the suffix of a $k$-run. This is why we need $P_2$ to contain an anchor; $P_1$ is not restricted because we index every possible initial position $i$.

We then sort the symbols of $D$ and use the trie ${\tau }_k$ to find the data structure $S_D$.

We now find the lexicographic range $[x_1,x_2]\times [y_1,y_2]\times [z_1,z_2]\times [|{\mathrm{pref}}_D(P_2)|,+\mathrm{\infty }]$ using the suffix tree $𝒯$ of $T$ and the suffix tree ${𝒯}^{rev}$ of the reversed text, $T^{rev}$. The range $[x_1,x_2]$ then corresponds to the leaf range of the locus of $P_1^{rev}$ in ${𝒯}^{rev}$, the range $[y_1,y_2]$ to the leaf range of the locus of ${\mathrm{pref}}_D{(P_2)}^{rev}$ in ${𝒯}^{rev}$, and the range $[z_1,z_2]$ to the leaf range of the locus of ${\mathrm{suff}}_D(P_2)$ in $𝒯$.

Once the four-dimensional range is identified, we extract all the points from $S_D$ in the range using the range reporting data structure.

The suffix trees use space $O(n)$. The total number of points in the range reporting data structures is $O(n)$ as there are at most $n$ $k$-runs. Because we will perform one-sided searches on the fourth coordinate, the grid of $S_D$ can be represented in $O(|P_D|{\log }^{1+ϵ}n)$ space, for any constant $ϵ>0$, so that range searches on it take time $O(\mathrm{occ}+\log n/\log \log n)$ to report the $\mathrm{occ}$ points in the range [38, Thm. 7]. Thus, the total space for the range reporting data structures is $O(n{\log }^{1+ϵ}n)$. The space of the trie ${\tau }_k$ is $k|{𝒟}_k|\in O(kn)$.

The string ${\mathrm{pref}}_D(P_2)$ can easily be computed in $O(k+|P_2|)$ time with high probability using a dictionary data structure [15]. Sorting $D$ can be done in $O(k\log \log k)$ time [1]. By implementing the pointers of node children in ${\tau }_k$ and in the suffix trees $𝒯$ and ${𝒯}^{rev}$ using perfect hashing (see [36]), the search in ${\tau }_k$ takes $O(k)$ worst-case time and the three searches in $𝒯$ and ${𝒯}^{rev}$ take total time $O(|P_1|+|P_2|)$. The range reporting query takes time $O(\log n/\log \log n+\mathrm{occ})$. In total, a query takes $O(m+k\log \log k+\log n/\log \log n+\mathrm{occ})$ time with high probability¹¹1Unfortunately, [38, Thm. 7] does not describe construction of the range reporting data structure that we use, so we are not able to provide construction time and working space of our index..

Let $𝒟={\bigcup }_{1\le k\le k_{\max }}{𝒟}_k$. Our data structure consists of the following.

• $\mathrm{■}$

  The suffix tree $𝒯$ of $T$ and the suffix tree ${𝒯}^{rev}$ of the reversed text, $T^{rev}$.

• $\mathrm{■}$

  The data structure $S_D$ from Section 3.1 for each set $D\in 𝒟$.

• $\mathrm{■}$

  A trie $\tau$ storing all the strings of length 1 to $k_{\max }$, in increasing alphabetic order of characters, that correspond to some $D\in 𝒟$.

The suffix trees uses linear space. The space for each of the $k$ range reporting data structures is $O(n{\log }^{1+ϵ}n)$. Added over all $k\in [1..k_{\max }]$, the total space becomes $O(k_{\max }n{\log }^{1+ϵ}n)$. The space for the trie $\tau$ is $O(n{k}_{\max }^2)$ since there are at most $k_{\max }n$ strings each of length at most $k_{\max }$. Since we assume , the total space is $O(k_{\max }n{\log }^{1+ϵ}n)$.

To perform the search, we traverse $\tau$ to find all the subsets of $D$ as follows. Let $s_D=c_1{c}_2\mathrm{\dots }{c}_k$ be the string formed by concatenating all symbols of $D$ in sorted order. Letting $N_i$ be the set of nodes of $\tau$ reached after processing $s_D[1..i]$ (initially, $i=0$ and $N_0$ contains only the root of $\tau$), $N_{i+1}$ is obtained by inserting in $N_i$ the nodes reached by following the edges labeled with character $s_D[i+1]$ from nodes in $N_i$. In other words, for each symbol of $s_D$ we try both skipping it or descending by it in $\tau$. The last set, $N_k$, contains all the $2^k-1$ nodes of $\tau$ corresponding to subsets of $D$. Each time we are in a node of $\tau$ corresponding to some set $D^{\prime }\subseteq D$ which has an associated range reporting data structure $S_{D^{\prime }}$, we perform a range reporting query $(x_1,x_2,y_1,y_2,z_1,z_2,|{\mathrm{pref}}_{D^{\prime }}(P_2)|,\mathrm{\infty })$.

Since the range $[x_1,x_2]$ is the same for all queries, we only compute this once. This is done by a search for $P_1^{rev}$ in ${𝒯}^{rev}$. The intervals $[y_1,y_2]$ and $[z_1,z_2]$, on the other hand, change during the search, as the split of $P_2$ into ${\mathrm{pref}}_{D^{\prime }}(P_2)$ and ${\mathrm{suff}}_{D^{\prime }}(P_2)$ depends on the subset $D^{\prime }$. To compute these intervals we first preprocess $P_2$ as follows. Compute the ranges $[y_1,y_2]$ for all reversed prefixes of $P_2$ using the suffix tree ${𝒯}^{rev}$: Start by looking up the locus for $P_2^{rev}$ and then find the remaining ones by following suffix links. Similarly, we compute the ranges $[z_1,z_2]$ for the suffixes of $P_2$ following suffix links in $𝒯$. If we know the length $\mathrm{\ell }$ of ${\mathrm{pref}}_{D^{\prime }}(P_2)$, we can then easily look up the corresponding intervals.

Maintaining $\mathrm{\ell }$. We now explain how to maintain the length $\mathrm{\ell }$ of ${\mathrm{pref}}_{D^{\prime }}(P_2)$ for $D^{\prime }\subset D$ in constant time for every trie node we meet during the traversal of $\tau$. The difficulty with maintaining $|{\mathrm{pref}}_{D^{\prime }}(P_2)|$ while $D^{\prime }$ changes is that when traversing the trie we add the characters to $D^{\prime }$ in lexicographical order and not in the order they occur in $P_2$ (see Figure 2).

First we compute for each character $c\in D$ the position $p_c$ of the first occurrence of $c$ in ${\mathrm{pref}}_D(P_2)$. If $c$ does not occur in ${\mathrm{pref}}_D(P_2)$, we set $p_c=\mathrm{\infty }$. For each $c\in D$, we furthermore compute the position rank $r_c$ of $c$, i.e., the rank of $p_c$ in the sorted set $\{p_c:c\in D\}$. We build:

• $\mathrm{■}$

  a dictionary $R$ saving the position rank $r_c$ of each element $c\in D$.

• $\mathrm{■}$

  an array $B$ containing the position of the first occurrence of the characters in $D$ in rank order, i.e., for each character $c\in D$, $B[r_c]=p_c$.

Let $\alpha$ be the first character in position rank order that is not in $D^{\prime }$. Then $\mathrm{\ell }=p_{\alpha }-1$. The main idea is to maintain the intervals $I_{D^{\prime }}$ of characters in $D^{\prime }$ in position rank order. The position rank $r_{\alpha }$ of $\alpha$ can then easily be computed from the set of intervals $I_{D^{\prime }}$ and used to compute $p_{\alpha }=B[r_{\alpha }]$. Let $[i,j]$ be the first interval in $I_{D^{\prime }}$ in sorted order. If $i\ne 1$ then $r_{\alpha }=1$ otherwise, $r_{\alpha }=j+1$. We use an array $A[0..|D|+1]$ to store the intervals of $I_{D^{\prime }}$. We will maintain the invariant that $A[i]\ne 0$ if and only if the element with position rank $i$ is in $D^{\prime }$. Furthermore, we will maintain the invariant that the first, respectively last, position of an interval of nonzero entries in $A$ contains the position of the end, respectively start, of the interval. Initially, all positions in $A$ are $0$.

We proceed as follows. Initialize $\mathrm{\ell }=0$ and initialize an empty stack $S$. We now maintain $\mathrm{\ell }=|{\mathrm{pref}}_{D^{\prime }}(P_2)|$ as follows:

When we go down during the traversal adding a character $c$ to the set, we first lookup $r_c$ in $R$ and set $p_c=B[r_c]$. If $p_c=\mathrm{\infty }$ there are no changes. Otherwise, let $D^{\prime \prime }=D\setminus \{c\}$, i.e., $D^{\prime \prime }$ is the set we had before inserting $c$. We set $A[r_c]=r_c$ and compute the leftmost position $lp$ of the interval in $I_{D^{\prime }}$ containing $c$: If $A[r_c-1]=0$ then set $lp=r_c$. Otherwise, there is an interval in $I_{D^{\prime \prime }}$ ending at position $r_c-1$ that must be merged with $[r_c,r_c]$, and $A[r_c-1]$ contains the left endpoint of this interval. Therefore we set $lp=A[r_c-1]$. To compute the rightmost position $rp$ of the interval in $I_{D^{\prime }}$ containing $c$: If $A[r_c+1]=0$ then set $rp=r_c$. Otherwise, there is another interval starting at position $r_c-1$ and we set $rp$ to be the end of this interval, i.e., $rp=A[r_c+1]$. We then push $(lp,A[lp],rp,A[rp],\mathrm{\ell })$ onto the stack to be able to quickly undo the operations later. Then we update $A$ by setting $A[lp]=rp$ and $A[rp]=lp$. Finally, we update $\mathrm{\ell }$: If $A[1]\ge r_c$ set $\mathrm{\ell }=B[A[1]+1]-1$. Otherwise, $\mathrm{\ell }$ does not change.

When going up in the traversal removing character $c$ we first lookup $p_c$. If $p_c=\mathrm{\infty }$ there are no changes. Otherwise, we pop $(lp,lv,rp,rv,{\mathrm{\ell }}^{\prime })$ from the stack and set $A[lp]=lv$, $A[rp]=rv$, $A[r_c]=0$, and $\mathrm{\ell }={\mathrm{\ell }}^{\prime }$.

It takes $O(|P_1|)$ time to search for $P_1^{rev}$ in ${𝒯}^{rev}$. Computing $[y_1,y_2]$ and $[z_1,z_2]$ for all splits of $P_2$ takes time $O(|P_2|)$. Sorting $D$ can be done in time $O(k\log \log k)$ [1]. Computing $p_c$ for all characters in $D$, sorting them, computing the ranks $r_c$, and constructing the arrays $B$ and $P$ and the dictionary $R$ takes linear time in the pattern length with high probability. The size of the subtrie we visit in the search is $O(2^k)$ and in each step we use constant time to compute the length of $\mathrm{\ell }$. The total time for the range queries is $O(2^k\log n/\log \log n+\mathrm{occ})$. Thus, in total we use $O(m+2^k\log n/\log \log n+\mathrm{occ})$ time with high probability.