Counting on General Run-Length Grammars

Context-free grammars (CFGs) have proven to be an elegant and efficient model for data compression. The idea of grammar-based compression [51, 29] is, given a text $T[1..n]$, to construct a context-free grammar $G$ of size $g$ that only generates $T$. One can then store $G$ instead of $T$, which achieves compression if $g\ll n$. Compared to more powerful compression methods like Lempel-Ziv [35], grammar compression offers efficient direct access to arbitrary snippets of $T$ without the need of full decompression [49, 3]. This has been extended to offering indexed searches (i.e., in time $o(n)$) for the occurrences of string patterns in $T$ [8, 16, 10, 7, 40], as well as more complex computations over the compressed sequence [32, 21, 18, 19, 41, 28]. Since finding the smallest grammar $G$ representing a given text $T$ is NP-hard [49, 5], many algorithms have been proposed to find small grammars for a given text [34, 49, 46, 50, 36, 23, 24]. Grammar compression is particularly effective when handling repetitive texts; indeed, the size $g^{\ast }$ of the smallest grammar representing $T$ is used as a measure of its repetitiveness [39].

Nishimoto et al. [47] proposed enhancing CFGs with “run-length rules” to improve the compression of repetitive strings. These run-length rules have the form $A\to B^s$, where $B$ is a terminal or a non-terminal symbol and $s\ge 2$ is an integer. CFGs that may use run-length rules are called run-length context-free grammars (RLCFGs). Because CFGs are RLCFGs, the size $g_{rl}^{\ast }$ of the smallest RLCFG generating $T$ always satisfies $g_{rl}^{\ast }\le g^{\ast }$, and it can be $g_{rl}^{\ast }=o(g^{\ast })$ in text families as simple as $T=a^n$, where $g_{rl}^{\ast }=O(1)$ and $g^{\ast }=\mathrm{\Theta }(\log n)$.

The use of run-length rules has become essential to produce grammars with size guarantees and convenient regularities that speed up indexed searches and other computations [32, 21, 18, 7, 28, 30]. The progress made in indexing texts with CFGs has been extended to RLCFGs, reaching the same status in most cases. These functionalities include extracting substrings, computing substring summaries, and locating all the occurrences of a pattern string [7, App. A]. It has also been shown that RLCFGs can be balanced [42] in the same way as CFGs [19], which simplifies many compressed computations on RLCFGs.

Interestingly, counting, that is, determining how many times a pattern occurs in the text without spending the time to list those occurrences, can be done efficiently on CFGs, but not so far on RLCFGs. Counting is useful in various fields, such as pattern discovery and ranked retrieval, for example to help determine the frequency or relevance of a pattern in the texts of a collection [37].

Navarro [44] showed how to count the occurrences of a pattern $P[1..m]$ in $T[1..n]$ in $O(m^2+m{\log }^{2+ϵ}n)$ time using $O(g)$ space if a CFG of size $g$ represents $T$, for any constant $ϵ>0$ chosen at indexing time. Christiansen et al. improved this time to $O(m{\log }^{2+ϵ}n)$ by using more recent underlying data structures for tries. Christiansen et al. [7] and Kociumaka et al. [30] extended the result to particular RLCFGs, even achieving optimal $O(m)$ time by using additional space, but could not extend their mechanism to general RLCFGs. Their paper [7] finishes, referring to counting, with “However, this holds only for CFGs. Run-length rules introduce significant challenges […] An interesting open problem is to generalize this solution to arbitrary RLCFGs.”

In this paper we give the first solution to this open problem, by introducing an index that counts the occurrences of a pattern $P[1..m]$ in a text $T[1..n]$ represented by a RLCFG of size $g_{rl}$. Our index uses $O(g_{rl})$ space and answers queries in time $O(m{\log }^{2+ϵ}n)$ for any constant $ϵ>0$ chosen at indexing time. This is the same time complexity that holds for CFGs, which puts on par our capabilities to handle RLCFGs and CFGs on all the considered functionalities. As an example of our new capabilities, we show how a recent result on finding the maximal exact matches of $P$ using CFGs [45] can now run on RLCFGs.

While our solution builds on the ideas developed for CFGs and particular RLCFGs [44, 7, 30], arbitrary RLCFGs lack crucial structure that holds in those particular cases, namely that if there exists a run-length rule $A\to B^s$, then the period [11] of the string represented by $A$ is the length of that of $B$. We show, however, that the general case still retains some structure relating the shortest periods of $P$ and the string represented by $A$. We exploit this relation to develop a solution that, while considerably more complex than that for those particular cases, retains the same theoretical guarantees obtained for CFGs.

A grammar index represents a text $T[1..n]$ using a grammar $G$ that generates only $T$. As opposed to mere compression, the index supports three primary pattern-matching queries: locate (returning all positions of a pattern in the text), count (returning the number of times a pattern appears in the text), and extract (extracting any desired substring of $T$). In order to locate, grammar indexes identify “initial” pattern occurrences and then track their “copies” throughout the text. The former are the primary occurrences, defined as those that cross phrase boundaries, and the latter are the secondary occurrences, which are confined to a single phrase. This approach [25] forms the basis of most grammar indexes [8, 9, 10] and related ones [16, 33, 12, 17, 13, 2, 43, 52], which first locate the primary occurrences and then derive their secondary occurrences through the grammar tree.

As mentioned in Section 2.5, the grammar tree leaves cut the text into phrases. In order to report each primary occurrence of a pattern $P[1..m]$ exactly once, let $v$ be the lowest common ancestor of the first and last leaves the occurrence spans; $v$ is called the locus node of the occurrence. Let $v$ have $t$ children and the first leaf that covers the occurrence descend from the $i$th child of $v$. If $v$ represents $A\to {\alpha }_1\mathrm{\cdots }{\alpha }_t$, it follows that $\exp ({\alpha }_i)$ finishes with a pattern prefix $R=P[1..q]$ and that $\exp ({\alpha }_{i+1})\mathrm{\cdots }\exp ({\alpha }_t)$ starts with the suffix $Q=P[q+1..m]$. We will denote such cuts as $P=R\mid Q$. The alignment of $R\mid Q$ within $\exp ({\alpha }_i)\mid \exp ({\alpha }_{i+1})\mathrm{\cdots }\exp ({\alpha }_t)$ is the only possible one for that primary occurrence.

Following the original scheme [25], grammar indexing builds two sets of strings, $𝒳$ and $𝒴$, to find primary occurrences [8, 9, 10]. For each grammar rule $A\to {\alpha }_1\mathrm{\cdots }{\alpha }_t$, the set $𝒳$ contains all the reverse expansions of the children of $A$, $\exp {({\alpha }_i)}^{\mathrm{rev}}$, and $𝒴$ contains all the expansions of the nonempty rule suffixes, $\exp ({\alpha }_{i+1})\mathrm{\cdots }\exp ({\alpha }_t)$. Both sets are sorted lexicographically and placed on a grid with (less than) $g$ points, $t-1$ for each rule $A\to {\alpha }_1\mathrm{\cdots }{\alpha }_t$. Given a pattern $P[1..m]$, for each cut $P=R\mid Q$, we first find the lexicographic ranges $[s_x,e_x]$ of $R^{\mathrm{rev}}$ in $𝒳$ and $[s_y,e_y]$ of $Q$ in $𝒴$. Each point $(x,y)\in [s_x,e_x]\times [s_y,e_y]$ represents a primary occurrence of $P$. Grid points are augmented with their locus node $v$ and offset $|\exp ({\alpha }_1)\mathrm{\cdots }\exp ({\alpha }_i)|$. The cut-based approach naturally extends to the case $m=1$ by allowing empty prefixes, that is, cuts of the form $P=\epsilon \mid P[1]$. We then search for suffixes matching $P[1]$ in $𝒴$, combining them with all rows in $𝒳$ to retrieve all primary occurrences of the character.

Once we identify the locus node $v$ (with label $A$) of a primary occurrence, every other mention of $A$ or its ancestors in the grammar tree, and recursively, of the ancestors of those mentions, yields a secondary occurrence of $P$. Those are efficiently tracked and reported [9, 10, 7]. An important consistency observation for counting is that the amount of secondary occurrences triggered by each primary occurrence is fixed. See Figure 1.

The original approach [9, 10] spends time $O(m^2)$ to find the ranges $[s_x,e_x]$ and $[s_y,e_y]$ for the $m-1$ cuts of $P$; this was later improved to $O(m\log n)$ [7]. Each primary occurrence found in the grid ranges takes time $O({\log }^{ϵ}g)$ using geometric data structures, whereas each secondary occurrence requires $O(1)$ time. Overall, the $occ$ occurrences of $P$ in $T$ are listed in time $O(m\log n+occ{\log }^{ϵ}g)$.

To generalize this solution to RLCFGs [7, App. A.4], rules $A\to B^s$ are added as a point $(x,y)=(\exp {(B)}^{\mathrm{rev}},\exp {(B)}^{s-1})$ in the grid. This suffices to capture every primary occurrence of the corresponding rule $A\to B\mathrm{\cdots }B$: If there are primary occurrences with the cut $P=R\mid Q$ in $B\mathrm{\cdots }B$, then one is aligned with the first phrase boundary, $\exp (B)\mid \exp {(B)}^{s-1}$. Precisely, there is space to place $Q$ right after the first $t=s-\lceil |Q|/|B|\rceil$ phrase boundaries. When the point $(x,y)$ is retrieved for a given cut, then, $t$ primary occurrences are declared with offsets $|B|-|R|$, $2|B|-|R|$, $\mathrm{\dots }$, $t|B|-|R|$ within $\exp (A)$. The amount of secondary occurrences triggered by each such primary occurrence still depends only on $A$.

Navarro [44] obtained the first result in counting the number of occurrences of a pattern $P[1..m]$ in a text $T[1..n]$ represented by a CFG of size $g$, within time $O(m^2+m{\log }^{2+ϵ}g)$, for any constant $ϵ>0$, and using $O(g)$ space. His method relies on the consistency observation above, which allows enhancing the grid described in Section 3 with the number $c(A)$ of (primary and) secondary occurrences associated with each point. At query time, for each pattern cut, one sums the number of occurrences in the corresponding grid range using the technique mentioned in Section 2.4. The final complexity is obtained by aggregating over all $m-1$ cuts of $P$ and considering the $O(m^2)$ time required to identify all the ranges. Christiansen et al. [7, Thm. A.5] later improved this time to just $O(m\log n+m{\log }^{2+ϵ}g)$, by using more modern techniques to find the grid range of all cuts of $P$.

Christiansen et al. [7] also presented a method to count in $O(m+{\log }^{2+ϵ}n)$ time on a particular RLCFG of size $g_{rl}=O(\gamma \log (n/\gamma ))$, where $\gamma$ is the size of the smallest string attractor [27] of $T$. They also show that by increasing the space to $O(\gamma \log (n/\gamma ){\log }^{ϵ}n)$ one can reach the optimal counting time, $O(m)$. The grammar properties allow reducing the number of cuts of $P$ to check to $O(\log m)$, instead of the $m-1$ cuts used on general RLCFGs.

Christiansen et al. build on the same idea of enhancing the grid with the number of secondary occurrences, but the process is considerably more complex on RLCFGs, because the consistency property exploited by Navarro [44] does not hold on run-length rules $A\to B^s$: the number of occurrences triggered by a primary occurrence with cut $P=R\mid Q$ found from the point $(\exp {(B)}^{\mathrm{rev}},\exp {(B)}^{s-1})$ depends on $s$, $|B|$, and $|Q|$. Their counting approach relies on another property that is specific of their RLCFG [7, Lem. 7.2]:

This property facilitates the division of the counting process into two cases. For each run-length rule $A\to B^s$, they introduce two points, $(x,y^{\prime })=(\exp {(B)}^{\mathrm{rev}},\exp (B))$ and $(x,y^{\prime \prime })=(\exp {(B)}^{\mathrm{rev}},\exp {(B)}^2)$, in the grid. These points are associated with the values $c(A)$ and $(s-2)\cdot c(A)$, respectively. The counting process is as follows: for a cut $P=R\mid Q$ where $R$ is a suffix of $\exp (B)$, if $Q⊑\exp (B)$, then it will be counted $c(A)+(s-2)\cdot c(A)=(s-1)\cdot c(A)$ times, as both points will be within the search range. If $Q$ instead exceeds $\exp (B)$, but still $Q⊑\exp {(B)}^2$, then it will be counted $(s-2)\cdot c(A)$ times, solely by point $(x,y^{\prime \prime })$. Finally if $Q$ exceeds $\exp {(B)}^2$, then $Q$ is periodic (with $p(Q)=|B|$).

They handle that remaining case as follows. Given a cut $P=R\mid Q$ and the period $p=p(Q)=|B|$, where $|Q|>2p$, the number of primary occurrences of this cut inside rule $A\to B^s$ is $s-\lceil |Q|/p\rceil$ (cf. the end of Section 3). Let $D$ be the set of rules $A\to B^s$ such that $R$ is a suffix of $\exp (B)$ and $Q$ is a prefix of $\exp {(B)}^{s-1}$, that is, those within the grid range of the cut, and $c(A)$ the number of (primary and secondary) occurrences of $A$. Then, the number of occurrences triggered by the primary occurrences found within symbols in $D$ for this cut is

For each run-length rule $A\to B^s$, they compute a Karp–Rabin signature (Section 2.3) $\kappa (\exp (B))$ and store it in a perfect hash table [15, 1], associated with values

Additionally, for each such $B$, the authors store the set $s(B)=\{s:A\to B^s\}$.

At query time, they calculate the shortest period $p=p(P)$. For each cut $P=R\mid Q$, $Q$ is periodic if $|Q|>2p$. If so, they compute $k=\kappa (Q[1..p])$, and if there is an entry $B$ associated with $k$ in the hash table, they add to the number of occurrences found up to then

where $s_{min}=\min \{s\in s(B),(s-1)\cdot |B|\ge |Q|\}$ is computed using exponential search over $s(B)$ in $O(\log m)$ time. Note that they exploit the fact that the number of repetitions to subtract, $\lceil |Q|/p\rceil$, depends only on $p=|B|$, and not on the exponent $s$ of rules $A\to B^s$.

Since fingerprints $\kappa (\pi )$ are collision-free on substrings of $T$, and the nonterminals in their particular RLSLP produce distinct expansions, each valid fingerprint $\kappa (Q[1..p])$ corresponds to at most one nonterminal $B$. This guarantees that, if a match is found in the hash table, it uniquely identifies a single candidate $B$. Further, they show how to filter out false positives for prefixes of $Q$ that do not occur in the set [7, Lem. 6.5].

The total counting time, on a grammar of size $g_{rl}$, is $O(m\log n+m{\log }^{2+ϵ}{g}_{rl})$. In their grammar, the number of cuts to consider is $O(\log m)$, which allows reducing the cost of computing the grid ranges to $O(m)$. The signatures of all substrings of $P$ are also computed in $O(m)$ time, as mentioned in Section 2.3. Considering the grid searches, the total cost for counting the pattern occurrences drops to $O(m+{\log }^{2+ϵ}{g}_{rl})\subseteq O(m+{\log }^{2+ϵ}n)$ [7, Sec. 7].

Recently, Kociumaka et al. [30] employed this same approach to count the occurrences of a pattern in a smaller RLCFG that uses $O(\delta \log \frac{n\log |\mathrm{\Sigma }|}{\delta \log n})$ space, where $\delta \le \gamma$. They demonstrated that the RLCFG they produce satisfies Property 1 [7, Lem. 7.2], which is necessary to apply the described scheme.

We now describe a solution to count the occurrences in arbitrary RLCFGs, where the convenient Property 1 used in the literature may not hold. We start with a simple observation.