Efficient Terabyte-Scale Text Compression via Stable Local Consistency and Parallel Grammar Processing

A string $T[1..n]$ is a sequence of $n$ symbols over an alphabet $\mathrm{\Sigma }=\{1,2,\mathrm{\dots },\sigma \}$. We use $T[j]$ to refer to the $jth$ symbol in $T$ from left to right, and $T[a..b]$ to refer to the substring starting in $T[a]$ and ending in $T[b]$. An equal-symbol run $T[a..b]=s^c$ is a substring storing $c$ consecutive copies of $s\in \mathrm{\Sigma }$, with $a=1$ or $T[a-1]\ne s$; and $b=n$ or $T[b+1]\ne s$.

We consider a collection $𝒯=\{T_1,T_2,\mathrm{\dots },T_k\}$ of $k$ strings as a multiset where each element $T_j\in 𝒯$ has an arbitrary order $j\in [1..k]$. In addition, we use the operator $\Vert 𝒯\Vert ={\sum }_{T_j\in 𝒯}|T_j|$ to express the total number of symbols. We also use subscripts to differentiate collections (e.g. ${𝒯}_a$ and ${𝒯}_b$). The expression ${𝒯}_{ab}={𝒯}_a\circ {𝒯}_b$ denotes the combination of ${𝒯}_a$ and ${𝒯}_b$ into a new collection ${𝒯}_{ab}$. We assume that all collections have the same constant-size alphabet $\mathrm{\Sigma }$.

Grammar compression consists in representing a string $T[1..n]\in {\mathrm{\Sigma }}^{\ast }$ as a small context-free grammar that generates only $T$ [23, 4]. Formally, a grammar $𝒢=\{\mathrm{\Sigma },V,ℛ,S\}$ is a tuple where $\mathrm{\Sigma }$ is the alphabet of $T$ (the terminals), $V$ is the set of nonterminals, $ℛ\subseteq V\times {(\mathrm{\Sigma }\cup V)}^{\ast }$ is the set of rewriting rules in the form $X\to Q[1..q]$. The symbol $S\in V$ is the grammar’s start symbol. Given two strings $w_a=A\cdot X\cdot B,w_b=A\cdot Q[1..q]\cdot B\in {(\mathrm{\Sigma }\cup V)}^{\ast }$, $w_b$ rewrites $w_a$ (denoted $w_a\Rightarrow w_b$) if $X\to Q[1..q]$ exists in $ℛ$. Furthermore, $w_a$ derives $w_b$, denoted $w_a{\Rightarrow }^{\ast }{w}_b$, if there is a sequence $u_1,u_2,\mathrm{\dots },u_x$ such that $u_1=w_a$, $u_x=w_b$, and $u_j\Rightarrow u_{j+1}$ for . The string $exp(X)\in {\mathrm{\Sigma }}^{\ast }$ resulting from $X{\Rightarrow }^{\ast }exp(X)$ is the expansion of $X$, with the decompression of $T$ expressed as $S{\Rightarrow }^{\ast }exp(S)=T$. Compression algorithms ensure that every $X\in V$ occurs only once on the left-hand sides of $ℛ$. In this way, there is only one possible string $exp(X)$ for each $X$. This type of grammar is referred to as straight-line. The sum of the lengths of the right-hand sides of $ℛ$ is the grammar size.

The parse tree $PT(X)$ of $X\in V$ represents $X{\Rightarrow }^{\ast }exp(X)$. Given the rule $X\to Q[1..q]$, the root of $PT(X)$ is a node $r$ labelled $X$ that has $q$ children, which are labelled from left to right with $Q[1],Q[2],\mathrm{\dots },Q[q]$, respectively. The $jth$ child of $r$, labelled $Q[j]$, is a leaf if $Q[j]\in \mathrm{\Sigma }$; otherwise, it is an internal node whose subtree is recursively defined according to $Q[j]$ and its rule in $ℛ$.

Post-processing a grammar consists of capturing the remaining repetitions in its rules. For instance, if $XY\in V^{\ast }$ appears multiple times on the right-hand sides of $ℛ$, one can create a new rule $Z\to XY$ and replace the occurrences of $XY$ with $Z$. Run-length compression encapsulates each distinct equal-symbol $X^{\mathrm{\ell }}\in {(\mathrm{\Sigma }\cup V)}^{\ast }$ appearing in the right-hand sides of $ℛ$ as a constant-size rule $X^{\prime }\to (X,\mathrm{\ell })$. Grammar simplification removes every rule $X\to Q[1..q]$ whose symbol $X$ appears once on the right-hand sides, replacing its occurrence with $Q[1..q]$.

A parsing is a partition of a string $T[1..n]$ into a sequence of phrases $T=T[1..j_1-1]T[j_1..j_2-1]\mathrm{\cdots }T[j_x..n]$, where the indices are breaks. Let $par(o,o^{\prime })=T[j_y..j_{y+1}-1]T[j_{y+1}..j_{y+2}-1]\mathrm{\dots }T[j_{y+u-1}..j_{y+u}-1]$ denote the $u$ phrases that cover a substring $T[o..o^{\prime }]$, with $o\in [j_y..j_{y+1})$ and $o^{\prime }\in [j_{y+u-1},j_{y+u})$. A parsing is locally consistent [6] iff, for any pair of equal substrings $T[a..b]=T[a^{\prime }..b^{\prime }]$, $par(a,b)$ and $par(a^{\prime },b^{\prime })$ differ in $O(1)$ phrases at the beginning and $O(1)$ at the end, with their internal phrase sequences identical.

A locally consistent parsing scheme relevant to this work is that of Nong et al. [35]. They originally described their idea to perform induced suffix sorting, but it has been shown that it is also locally consistent [10, 7]. They define a type for each position $T[\mathrm{\ell }]$:

Their method scans $T$ from right to left and sets a break at each LMS-type position.

One can create a grammar $𝒢=\{\mathrm{\Sigma },V,ℛ,S\}$ that only generates $T$ by applying successive rounds of locally consistent parsing. Different works present this idea slightly differently (see [38, 30, 18, 3, 5, 10]), but the procedure is similar: in every round $i$, the algorithm receives a string $T^i$ as input ($T^i=T$ with $i=1$) and performs the following steps:

1. 1.

   Break $T^i$ into phrases using a locally consistent parsing.

2. 2.

   Assign a nonterminal $X$ to each distinct sequence $Q[1..q]$ that is a phrase in $T^i$.

3. 3.

   Store every $X$ in $V$ and its associated rule $X\to Q[1..q]$ in $ℛ$.

4. 4.

   Replace the phrases in $T^i$ by their nonterminals to form the string $T^{i+1}$ for $i+1$.

The process ends when $T^i$ does not have more breaks, in which case it creates the rule $S\to T^i$ for the start symbol and returns the resulting grammar $𝒢$. The phrases have a length of at least two, so the length of $T^{i+1}$ is half the length of $T^i$ in the worst case. Consequently, the algorithm incurs in $O(\log n)$ rounds and runs in $O(n)$ time.

The output grammar $𝒢$ is locally consistent because it compresses the occurrences of a pattern $P[1..m]$ largely in the same way. The first parsing round transforms the occurrences into substrings in the form $A^2[1..a^2]\cdot P^2[1..m^2]\cdot Z^2[1..z^2]\in V^{\ast }$, where the superscripts indicate symbols in $T^2$. The blocks $A^2[1..a^2]$ and $Z^2[1..z^2]$ have $O(1)$ variable nonterminals that change with $P$’s context, while $P^2[1..m^2]$ remains the same in all occurrences. In the second round, $P^2[1..m^2]$ yields strings in the form $A^3[1..a^3]\cdot P^3[1..m^3]\cdot Z^3[1..z^3]$ that recursively have the same structure. The substring $P^i[1..m^i]$ remains non-empty during the first $O(\log m)$ rounds. The substrings $P^i$, with $i=1,\mathrm{\dots },O(\log m)$, conform the core of $P$ [38] (see Figure 1).

Hashing refers to the idea of using a function $h:𝒰\to [m]$ to map elements in a universe $𝒰$ to integers in a range $[m]=\{0,1,\mathrm{\dots },m-1\}$ uniformly at random. When the universe $𝒰$ is large and only an unknown subset $𝒦\subset 𝒰$ requires fingerprints over a range $[m]$ with , the typical solution is to use a universal hash function. For any pair $x,y\in 𝒰$, a universal hash function ensures that the collision probability is $\text{Pr}[h(x)=h(y)]=1/m$. Let $𝒰=\{0,1,2,\mathrm{\dots },\sigma \}$ be the universe, $p>\sigma$ a prime number, and $a\in {[p]}_{+}=\{1,2,\mathrm{\dots },p-1\}$ and $b\in [p]=\{0,1,\mathrm{\dots },p-1\}$ integers chosen uniformly at random. One can make $h:𝒰\to [m]$ universal using the formula $h(x)=((ax+b)modp)modm$, with $p>m$.

These ideas can be adapted to produce fingerprints for a set $𝒦\subset {\mathrm{\Sigma }}^{\ast }$ of strings over an alphabet $\mathrm{\Sigma }=\{1,2,\mathrm{\dots },\sigma \}$ [12]. Pick a prime number $p>\sigma$ and choose an integer $c\in {[p]}_{+}$ uniformly at random. Then, build the degree $q$ polynomial $h(Q[1..q])=({\sum }_{i=1}^{q}Q[i]\cdot c^{i-1})modp$ over $[p]$ and regard the symbols $Q[1],Q[2],\mathrm{\dots },Q[q]$ in $Q[1..q]\in 𝒰$ as the polynomial’s coefficients. Additionally, compose $h$ with a universal hash function $h^{\prime }:[p]\to [m]$ to obtain a fingerprint in $[m]$. Let $a,b,c\in {[p]}_{+}$ be three integers chosen uniformly at random. Then the function becomes $h^{\prime }(Q[1..q])=((a({\sum }_{i=1}^{q}Q[i]\cdot c^{i-1})+b)modp)modm.$

We first introduce the features of the locally consistent grammar $𝒢=\{\mathrm{\Sigma },V,ℛ,S\}$ we build with BuildGram and MergeGrams. Given a rule $X\to Q[1..q]\in ℛ$, the operator $rhs(X)$ is an alias for the string $Q[1..q]$, with $rhs(s)=s$ when $s\in \mathrm{\Sigma }$. The grammar $𝒢$ is fully balanced, which means that, for any $X\in V\setminus \{S\}$, all root-to-leaf paths in $PT(X)$ have the same number $e$ of edges. We refer to $e$ as the level of $X$, and extend the use of level to the rule $X\to Q[1..q]\in ℛ$ associated with $X$. We indistinctly use the terms nonterminal and metasymbol to refer to $X\in V$.

The start symbol $S$ is associated with a rule $S\to C[1..k]$ where $C[1..k]$ is a sequence such that each $exp(C[j])=T_j[1..n_j]\in 𝒯$ and $PT(C[j])$ has height $O(\log n_j)$. The symbols in $C[1..k]$ can have different heights and, hence, different levels (this idea will become clear in Section 3.3). Let $l_{max}$ be the highest level among the elements in $C[1..k]$. We set the level of $S$ equal to $l=l_{max}+1$, which we regard as the height of $𝒢$.

We define the partitions $ℛ=\{{ℛ}^1,\mathrm{\dots },{ℛ}^{l-1}\}$ and $V=\{V^1,V^2,\mathrm{\dots },V^{l-1}\}$, where every pair $({ℛ}^i,V^i)$ is the set of rules and nonterminals (respectively) with level $i\in [1..l-1]$. In each subset ${ℛ}^i$, the left-hand sides are symbols over the alphabet $V^i$, while the right-hand sides are strings over $V^{i-1}$. Further, we consider $V^0=\mathrm{\Sigma }$ to be the set of terminals.

In this section, we describe the set $\mathscr{H}$ of hash functions that assign fingerprints in BuildGram. The universal hash function $h^0:\mathrm{\Sigma }\to [m_0]$ maps terminal symbols to integers over an arbitrary range $[0,1,\mathrm{\dots },m_0-1]$, with $m_0>\sigma$. Furthermore, each function $h^i$, with , recursively assigns fingerprints to the right-hand sides of ${ℛ}^i$. Let $[m_{i-1}]$ be the integer range for the fingerprints emitted by $h^{i-1}$. We choose a random prime number $p_i>m_{i-1}$, three integer values $a_i,b_i,c_i\in {[p_i]}_{+}$, and a new integer $m_i$. Now, given a rule $X\to Q[1..q]\in {ℛ}^i$, we compute the fingerprint for $Q[1..q]$ as

Although $h^i:{[m_{i-1}]}^{\ast }\to [m_i]$ computes a fingerprint for a string, we associate this fingerprint with $X\in V^i$ because each $Q[1..q]$ has one possible $X$. Notice that the recursive definition of $h^i$ implicitly traverses $PT(X)$ and ignores the nonterminals labelling $PT(X)$. As a result, the value that $h^i$ assigns to $Q[1..q]$ (or equivalently, to $X$) depends on $exp(X)$, the functions $h^0,h^1,\mathrm{\dots },h^i$, and the topology of $PT(X)$. In practice, we avoid traversing $PT(X)$ by operating bottom-up over $𝒢$: When we process ${ℛ}^i$, the fingerprints in $h^{i-1}$ for $V^{i-1}$ that we require to obtain the fingerprints in $h^i$ are available.

BuildGram does not know a priori the number of hash functions $\mathscr{H}$ needs to compress an input. However, the locally consistent grammar algorithm that we use requires $O(\log n)$ rounds of parsing to compress $T[1..n]$ (Section 3.3). If we consider the number of rounds plus the function $h^0$ for the terminals, then $|\mathscr{H}|\ge \lceil \log n\rceil +1$ is enough to process $T[1..n]$.

Our procedure $\text{BuildGram}(𝒯,\mathscr{H})$ receives as input a collection $𝒯=\{T_1,T_2,\mathrm{\dots },T_k\}$ of $k$ strings and a set $\mathscr{H}$ of hash functions, and returns a locally consistent grammar $𝒢=\{\mathrm{\Sigma },V,ℛ,S\}$ that only generates strings in $𝒯$. We assume $\mathscr{H}$ has at least $\lceil \log n_{max}\rceil +1$ elements (see Section 3.2), where $n_{max}$ is the length of the longest string in $𝒯$.

The algorithm of BuildGram is inspired by the parsing of Nong et al. [28], which has been used not only for compression [35], but also for the processing of strings [9] (see Section B). However, as noted in the Introduction, the ideas we present here and in the next sections are compatible with any locally consistent grammar that uses hashing.

Calculating the LMS-type positions of RandLMSPar during the round $i$ requires Equation 3 to obtain the type of each $T_j^i[\mathrm{\ell }]$, which involves knowing the relative $\prec$ order of $T_j^i[\mathrm{\ell }]$ and $T_j^i[\mathrm{\ell }+1]$. We obtain this information by feeding $rhs(T_j^i[j])$ and $rhs(T_j^i[\mathrm{\ell }+1])$ to Equation 2. The problem is that Equation 2 decompresses $T_j^i[\mathrm{\ell }]$ and $T_j^i[\mathrm{\ell }+1]$ from $𝒢$, adding a logarithmic penalty on the grammar construction. We avoid decompression by keeping an array $F[1..|\mathrm{\Sigma }\cup V|]$ that stores the fingerprints of the symbols we already have in $\mathrm{\Sigma }\cup V$.

At the beginning of BuildGram, we initialize $F$ with $\mathrm{\Sigma }$ elements, where every $F[s]=h^0(s)$ stores the fingerprint of $s\in \mathrm{\Sigma }$. Then, each round $i$ keeps in $F[T^i[\mathrm{\ell }]]$ the fingerprint $h^{i-1}(rhs(T^i[\mathrm{\ell }]))$. After we finish round $i$, we store the fingerprint $F[X]=h^i(rhs(X))$ of every $X\in V^i$ so that we can compute the types of ${𝒯}^{i+1}$ in the next round $i+1$.

Let $rhs(X)=Q[1..q]$ be the replacement for $X$. We modify Equation 2 as follows:

This operation is valid because the alphabet of $Q[1..q]$ is $V^{i-1}$, and $F$ already has its fingerprints.

We now present our algorithm for merging grammars. Let ${𝒯}_a$ and ${𝒯}_b$ be two collections, with $n_a$ and $n_b$ being the lengths of the longest strings in ${𝒯}_a$ and ${𝒯}_b$, respectively, and ${𝒯}_{ab}={𝒯}_a\circ {𝒯}_b$ being their union (Section 2.1). Furthermore, let ${𝒢}_a=\text{BuildGram}({𝒯}_a,\mathscr{H})$ and ${𝒢}_b=\text{BuildGram}({𝒯}_b,\mathscr{H})$ be grammars that only generate strings in ${𝒯}_a$ and ${𝒯}_b$, respectively. We assume that $\mathscr{H}$ has $|\mathscr{H}|\ge \lceil \log \max (n_a,n_b)\rceil +1$ elements (see Section 3.2). The instance $\text{MergeGrams}({𝒢}_a,{𝒢}_a)$ returns a locally consistent grammar ${𝒢}_{ab}$ that only generates strings in ${𝒯}_{ab}$, and that is equivalent to the output of $\text{BuildGram}({𝒯}_{ab},\mathscr{H})$.

For the grammar ${𝒢}_a$, let ${ℛ}_a$ be its set of rules, let $V_a$ be its set of nonterminals, and let $l_a$ be its height. The symbols ${ℛ}_b$, $V_b$, and $l_b$ denote equivalent information for ${𝒢}_b$. We consider the partitions ${ℛ}_a=\{{ℛ}_a^1,{ℛ}_a^2,\mathrm{\dots },{ℛ}_a^{l_a-1}\}$ and $V_a=\{V_a^1,V_a^2,\mathrm{\dots },V_a^{l_a-1}\}$, where every $({ℛ}_a^i,V_a^i)$ is the set of rules and nonterminals (respectively) that $\text{BuildGram}({𝒯}_a,\mathscr{H})$ produced during the parsing round $i\in [1..l_a-1]$. The elements ${ℛ}_b=\{{ℛ}_b^1,{ℛ}_b^2,\mathrm{\dots },{ℛ}_b^{l_b-1}\}$ and $V_b=\{V_b^1,V_b^2,\mathrm{\dots },V_b^{l_b-1}\}$ are equivalent partitions for ${𝒢}_b$.

MergeGrams processes the grammar levels $1,2,\mathrm{\dots },\max (l_a,l_b)-1$ in increasing order. In each round $i$, we keep the invariant that the right-hand sides of ${ℛ}_a^i$ and ${ℛ}_b^i$ are comparable. That is, given two rules $X_a\to Q_a[1..q_a]\in {ℛ}_a^i$ and $X_b\to Q_b[1..q_b]\in {ℛ}_b^i$, $Q_a[1..q_a]=Q_b[1..q_b]$ implies $exp(X_a)=exp(X_b)\in {\mathrm{\Sigma }}^{\ast }$. When $i=1$, the invariant holds as the right-hand sides of ${ℛ}_a^1$ and ${ℛ}_b^1$ are over $\mathrm{\Sigma }$, which is the same for ${𝒯}_a$ and ${𝒯}_b$ (Section 2.1).

We begin the algorithm by creating an array $L_a[0..l_a]$ that stores in $L_a[i]={\sum }_{j=0}^{i-1}|V_a^j|$ the number of nonterminals with level . Observe that $L_a[0]=0$ and $L_a[1]=|\mathrm{\Sigma }|$ because $V_a^0=\mathrm{\Sigma }$. We create an equivalent array $L_b$ for ${𝒢}_b$. We also initialize the sets $E^1,E^2,\mathrm{\dots },E^{l_b-1}$ where every $E^i\subseteq [1..k_b]$ keeps the indexes of $C_b[1..k_b]$ with level-$i$ symbols.

The first step of the merge round $i$ is to scan the right-hand sides of ${ℛ}_a^i$, and for each $X_a\to Q_a[1..q_a]$, we modify $X_a=X_a-L_a[i]$ and $Q_a[j]=Q_a[j]-L_a[i-1]$, with $j\in [1..q_a]$. The change $X_a=X_a-L_a[i]$ allows us to append new elements to $V_a^i$ and ${ℛ}_a^i$ while maintaining the validity of the symbols on the right-hand sides of ${ℛ}_a^{i+1}$, whose alphabet is $V_a^i$. Then, we create a hash table $H_a$ that stores every modified rule $X_a\to Q[1..q_a]\in {ℛ}_a^i$ as a key-value pair $(Q_a[1..q_a],X_a)$, and an empty array $M_b[1..|V_b^i|]$ to update the right-hand sides of $R_b^{i+1}$.

We check which right-hand sides in ${ℛ}_b^i$ occur as keys in $H_a$. Recall that, when $i=1$, the strings in ${ℛ}_a^i$ are already comparable to the keys in $H_a$ because they are over $\mathrm{\Sigma }$ and the subtraction of $L_a[i-1=0]$ does not change their values. For $i>1$, we make these strings comparable during the previous round $i-1$. If the string $Q_b[1..q_b]$ of a rule $X_b\to Q_b[1..q_b]$ occurs in $H_a$ as a key, we extract the associated value $X_a$ from the hash table. On the other hand, if $Q_b[1..q_b]$ does not exist in $H_a$, we create a new symbol $X_a=|V_a^i|+1$ and set $V_a^i=V_a^i\cup \{X_a\}$. Subsequently, we record the new rule $X_a\to Q_b[1..q_b]$ in ${ℛ}_a^i$ and store $M[X_b-L_b[i]]=X_a$. Once we process ${ℛ}_b^i$, we scan the right-hand sides of ${ℛ}_b^{i+1}$ and use $M$ to update their symbols. We also use $E^i$ to update each position $j\in E^i$ as $C_b[j]=M[C_b[j]-L_b[j]]$. Now, we discard ${ℛ}_b^i$ and continue to the next merge round $i+1$.

When we finish round $i$, the right-hand sides of ${ℛ}_b^{i+1}$ are over $[1..|V_a^i|]$, and the right-hand sides of ${ℛ}_a^{i+1}$ will be over $[1..|V_a^i|]$ after we update their values with $L_a$. These modifications will make both strings sets comparable, and our invariant will hold for $i+1$.

After $\min (l_a,l_b)-1$ rounds of merge, one of the input grammars will run out of levels. The remaining rounds will skip the creation and query of $H_a$, and will append new rules directly to ${ℛ}_a^i$ (if any). After we finish the rounds, we concatenate the compressed strings to form $C_{ab}[1..k_a+k_b]=C_a[1..k_a]\cdot C_b[1..k_b]$ and update the starting rule $S_a\to C_{ab}[1..k_a+k_b]$. The last step of MergeGrams is to modify the symbols in ${𝒢}_a$. For that purpose, we recompute $L_a$, and for every level-$i$ rule $X_a\to Q_a[1..q_a]$, we set $X_a=X_a+L_a[i]$ and $Q_a[j]=Q_a[j]+L_a[i-1]$, with $j\in [1..q_a]$. Figure 3 shows an example of MergeGrams.