Bit Packed Encodings for Grammar-Compressed Strings Supporting Fast Random Access

In this work, all numbers are integers represented using two’s complement. The bit width of an integer is the number of bits used in the integer’s binary representation. We denote an integer with a specific bit width $w$ as $in{t}_w$, where $w\in \{8,16,32,64\}$, e.g. the binary representation of $in{t}_{8}i=0$ is $00000000$. The most significant bit (MSB) of an integer is the position of the left-most bit set to $1$, e.g. $\mathrm{𝖬𝖲𝖡}(00000110)=3$. In addition to arithmetic operators, we use the bitwise AND () and OR ($|$) operators. For brevity, these operators may be combined with the assignment ($=$) operator for a compound assignment, e.g. $i|=2$ is equivalent to $i=i|2$. The left shift ($\ll$) operator shifts the bits of a number left, e.g. $01000001\ll 3=00001000$. Similarly, the right shift ($\gg$) operator shifts the bits of a number right, e.g. $00001001\gg 3=00000001$.

Our theoretical model of computation is the word RAM with machine word size $\omega$, in which bitwise operations can be performed in $O(1)$-time. In theory, the MSB of a given integer $i$ in range $[1,2^{\omega }]$ can be computed in $O(1)$-time on the word RAM [5]. In practice, typical implementations of MSBs, or equivalently of counting leading zeros (CLZ), require $O(\log \omega )$-time. We hereby make a reasonable assumption that MSBs take $O(1)$-time in practice as well, as the machine word size is typically $\omega =64$ in modern computers.

A context-free grammar is a set of recursive rules that describe how to form strings from a language’s alphabet. A context-free grammar is called an admissible grammar if the language it generates consists only of a single string. Grammar-based compression is a compression technique that computes an admissible grammar for a given string such that the encoded grammar uses less space than the original string. In this work, we refer to admissible grammars simply as grammars.

Let $T$ be a string over alphabet $\mathrm{\Sigma }=\{c_1,\mathrm{\dots },c_{\sigma }\}$, where $|T|$ denotes the length of $T$. $𝒢=⟨X,\mathrm{\Sigma },R,S⟩$ is a grammar that generates $T$, where $X$ is a set of non-terminal characters, $\mathrm{\Sigma }$ is the alphabet of $T$ (i.e. terminal characters) and is disjoint from $X$, $R$ is a finite relation in $X\times {(X\cup \mathrm{\Sigma })}^{\ast }$, and $S$ is the symbol in $X$ that should be used as the start rule when using $𝒢$ to generate $T$. $R$ defines the rules of $𝒢$ as a set of $N$ productions $\{X_i\to {\mathrm{expr}}_i\mid 1\le i\le m\}$ such that each $X_i$ is a non-terminal in $X$ and ${\mathrm{expr}}_i$ is a non-empty sequence from ${(\mathrm{\Sigma }\cup \{X_1,\mathrm{\dots },X_{i-1}\})}^{+}$. Note that there is a total ordering of the (non-)terminal characters of a grammar: . The size of grammar $𝒢$ is the total length of the right-hand sides of the productions and is denoted $\mathrm{𝗌𝗂𝗓𝖾}(𝒢)={\sum }_{i=1}^m|{\mathrm{expr}}_i|$. We say that a non-terminal $X_i$ represents a string $\alpha$ if $\alpha$ is the (unique) string that $X_i$ derives. We only consider grammars with no useless rules and symbols.

There are three main types of grammars in the literature: straight-line programs (SLPs), Chomsky normal form (CNF) grammars, and RePair grammars. An SLP is simply an admissible grammar. A CNF grammar is an SLP in Chomsky normal form, i.e. every rule (including start rule $S$) is of the form $X_i\to c$ ($c\in \mathrm{\Sigma }$) or $X_i\to X_{\mathrm{\ell }}{X}_r$ (). A RePair grammar is a CNF grammar in which the start rule can have arbitrarily many symbols in its right-hand side, i.e. $S\to \mathrm{expr}$ with $\mathrm{expr}\in {((X\setminus \{S\})\cup \mathrm{\Sigma })}^{+}$ [11]. In this work, all grammars are assumed to be SLPs, unless stated otherwise.

Let $𝒢$ be a grammar that represents a string $T$ of length $n$. A random access query on grammar $𝒢$ is, given a query position $p$ ($1\le p\le |T|$), return the $p$th character $T[p]$ in the uncompressed string $T$. In practice, random access queries can be for entire substrings $T[p..q]$, where $1\le p\le q\le |T|$. Our experiments include results for both single character and substring queries.

The canonical representation of a grammar-compressed string is an array-of-arrays, where each subarray represents a rule in the grammar [17]. Generally speaking, such an array is a jagged array, meaning subarrays can have different lengths. In this representation each non-terminal character is represented as its rule’s index in the array, with the first $\sigma$ values reserved for the alphabet. Subsequently, the subarrays are integer arrays, where the integer bit width is typically 32 or 64 bits. Moreover, this encoding requires $\mathrm{𝗌𝗂𝗓𝖾}(𝒢)\lg N$ bits, where $N=m+\sigma$. Although not optimal in size, the array-of-arrays is a versatile representation of grammar-compressed strings due to its simplicity, direct access to grammar rules and characters, algorithmic flexibility, and memory locality.

In the array-of-arrays representation of a grammar-compressed string each rule is a subarray and every non-terminal character is the index of its subarray in the array. Since every rule $X_i\to {\text{expr}}_i$ has the constraint ${\text{expr}}_i\in {(\mathrm{\Sigma }\cup \{X_1,\mathrm{\dots },X_{i-1}\})}^{+}$ (i.e. no character in a rule can be larger than the rule’s index), we observe that the smaller a rule’s index is, the fewer bits its characters can use in its subarray. Furthermore, it is possible for the largest number of bits required by any single character in a subarray to be much smaller than the subarray’s index. See Figure 1 for an example.

Bit packing is the technique of encoding multiple pieces of data using as few bits as possible by packing the raw bits into contiguous blocks of memory [16]. Given the observations above, we propose encoding grammar-compressed strings represented as an array-of-arrays using bit packing. Specifically, each rule (i.e. subarray) can be encoded using a different bit width, where each character in the rule is encoded using the same number of bits. This bit width can be smaller than the typical 64 bit integer size but still large enough to represent all the bits of each character in the rule. By using the same bit width for an entire rule, a subarray’s characters can be set and accessed just like the typical 64 bit integer arrays. We refer to the bit width for a subarray as its packing width.

In this work, we pack rules into byte arrays since a byte is typically the smallest unit of addressable memory, although our algorithms may be easily extended to other integer widths or raw memory. Given a rule $X_i\to {\mathrm{expr}}_i$ as a 64 bit integer array, Algorithm 1 shows how to pack the rule into a byte array in $O(|{\mathrm{expr}}_i|)$-time and Algorithm 2 shows how to access a single value from the packed byte array in $O(1)$-time. The $\mathrm{𝗀𝖾𝗍𝖯𝖺𝖼𝗄𝖶𝗂𝖽𝗍𝗁}$ function used in both algorithms provides the rule’s packing width, allowing different strategies for determining a subarray’s packing width to be used. It is assumed that $\mathrm{𝗀𝖾𝗍𝖯𝖺𝖼𝗄𝖶𝗂𝖽𝗍𝗁}$ can determine a rule’s packing width in $O(1)$-time, either through direct computation or preprocessing and memoization. We discuss how to compute $\mathrm{𝗀𝖾𝗍𝖯𝖺𝖼𝗄𝖶𝗂𝖽𝗍𝗁}$ in $O(1)$-time in Section 4. The remaining subsections describe three different strategies for determining the packing width for a rule.

Given a rule $X_i\to {\text{expr}}_i$, the simplest strategy for determining the rule’s packing width is to use $\lfloor {\log }_{2}i\rfloor +1$ by computing the MSB for $i$. Due to the rule constraint ${\text{expr}}_i\in {(\mathrm{\Sigma }\cup \{X_1,\mathrm{\dots },X_{i-1}\})}^{+}$, this guarantees that every character in ${\text{expr}}_i$ will fit in the packing width. This strategy is also advantageous because it can be computed directly for a given index, meaning grammars can be encoded online, i.e. as the grammar itself is being computed. We refer to this strategy as Bit Pack Left (BPL). It takes $O(1)$-time and is shown in Algorithm 3.

A strategy that requires preprocessing each rule $X_i\to {\mathrm{expr}}_i$ is to compute the MSB for each character in the rule and use the largest value as the rule’s packing width. Although this requires storing each rule’s packing width for decoding, we observe that these widths can be stored in a byte array $W$ because no width will exceed 64. We refer to this strategy as Bit Pack Right (BPR). It takes $O(|{\mathrm{expr}}_i|)$-time and is shown in Algorithm 3. Technically this is an offline strategy but it can be applied whenever an entire rule is added to the grammar, making it pseudo-online.

The last strategy is a variation of the BPR strategy. In this strategy, the MSB is computed for every character in a rule $X_i\to {\mathrm{expr}}_i$. The largest MSB computed is then compared to the packing width of the previous rule’s subarray and the larger of the two is used as the rule’s packing width. As with BPR, each rule’s packing width needs to be stored for decoding. However, the packing widths of this strategy form a monotonic sequence, meaning the packing width byte array $W$ can be replaced by a unique packing width byte array $W_{\text{unique}}$ that contains at most 64 values. A bit vector $B$ is then used to lookup each rule’s packing width in the unique packing width array using $O(1)$-time rank queries [19]. We refer to this strategy as Bit Pack Right Mono (BPRM). It takes $O(|{\mathrm{expr}}_i|)$-time and is shown in Algorithm 3. Like BPR, this strategy is technically offline but can be used pseudo-online by applying it whenever an entire rule is added to the grammar. Note that the effectiveness of this strategy is determined by the ordering of the rules in the grammar.

To begin, we observe that for CNF and RePair grammars the implementation underlying the array-of-arrays interface need not be an array-of-arrays. Specifically, the array-of-arrays interface can be implemented using a single contiguous byte array with no gaps between the bits of consecutive rules. The byte a rule starts at in this array and the specific bit the rule starts at in that byte can then be computed for each packing width strategy using only the information that strategy already requires, as described in Section 3.

Given a rule $X_i\to {\text{expr}}_i$, the left-side strategy determines a rule’s packing width by computing the MSB for $i$. This is equivalent to using $\lfloor {\log }_{2}i\rfloor +1$ as the packing width for each rule $X_i$. Recall that a CNF grammar has at most 2 characters per rule. This means that, when packing a grammar into a single contiguous byte array, the specific bit position $s(i)$ at which a given rule $X_i=X_{\mathrm{\ell }}{X}_r$ starts is equal to

where $\sigma$ denotes the number of terminal symbols. It is known (c.f. [1]) that

holds. Notice that the binary representation of $2^{\lfloor {\log }_2(i-1)\rfloor }$ is obtained by setting the $\lfloor {\log }_2(i-1)\rfloor$-th bit to 1 and all the other bits to 0, and thus takes $O(1)$-time by computing the MSB of $i-1$. Thus the starting bit position $s(i)$ for $X_i$ can be retrieved in $O(1)$-time using Equations 1 and 2. The byte position and local bit position in the single byte array can then be obtained by computing $\lfloor s(i)/\omega \rfloor$ and $(s(i)mod\omega )$, respectively, where $\omega$ is the byte size.

A RePair grammar can be packed into a single contiguous byte array the same way. This is because only the start rule is variable in size and it is the last rule to be packed into the array, meaning each rule’s position in the array can be computed in the same way as for a CNF grammar.

Observe that using Equations 1 and 2 to compute the bit position $s(i)$ for each rule $X_i$ is equivalent to computing the partial sums of the packing widths for the grammar. This can be computed directly for the left-side strategy using the closed form of the sum because the packing widths are derived directly from the non-terminal character $X_i$, i.e. the sums are a well-defined series. However, for the right-side and right-side monotonic strategies these partial sums must be precomputed and memoized. Fortunately, this can be done without asymptotically increasing the space requirements of these strategies.

For the right-side strategy, this can be done by replacing the packing width array $W$ with an array storing the partial sums of the packing widths $PW$. The packing width for a rule $X_i$ can then be computed as

And the bit position $s(i)$ at which $X_i$ starts can be computed as

Similarly, for the right-side monotonic strategy, the unique packing width array $W_{\text{unique}}$ can be replaced by a partial sum array $P{W}_{\text{unique}}$ such that, for all $j\in \{1,\mathrm{\dots },|W_{\text{unique}}|\}$,

where ${\text{sel}}_j$ and ${\text{sel}}_{j+1}$ are $\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}(B,j)$ and $\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}(B,j+1)$, respectively, and $B$ is the original lookup bit vector for $W_{\text{unique}}$. The packing width of a rule $X_i$ can then be computed as

where $r=\mathrm{𝗋𝖺𝗇𝗄}(B,i)$ and ${\text{sel}}_r$ and ${\text{sel}}_{r+1}$ are $\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}(B,r)$ and $\mathrm{𝗌𝖾𝗅𝖾𝖼𝗍}(B,r+1)$, respectively. The bit position $s(i)$ at which $X_i$ starts can then be computed as

In total, we have shown that the array-of-arrays interface can be implemented using a single contiguous byte array for CNF and RePair grammars while preserving the asymptotic run-time and space complexities of all three bit packing strategies.

We observe that Equation 1 can be used to compute the number of bits in a CNF grammar when using the left-side strategy. Specifically, given a CNF grammar with $N=m+\sigma$ total symbols, where $m$ is the number of non-terminals and $\sigma$ is the number of terminals, the number of bits is

Consider the following summation and the derivation of its closed-form

Using the closed form of Equation 9, we can define an upper bound on Equation 8 as

Thus, using the left-side strategy, a CNF grammar requires no more than $2{\log }_{2}N!+2N-{\log }_2\sigma !$ bits of space. Similarly, a RePair grammar with $N=m+\sigma$ total symbols and start rule $S\to {\text{expr}}_S$ requires at most $2{\log }_{2}N!+2N-{\log }_2\sigma !+|{\text{expr}}_S|{\log }_{2}N$ bits of space. Since the packing widths of the left-side strategy are the worst possible packing widths that may be used by the right-side and right-side monotonic strategies, these bounds can be extended to the right-side and right-side monotonic strategies by simply adding an additional $O(N)$ term to account for the memoized packing width data [17].

For simplicity, here we only consider the bounds for the left-side strategy on CNF grammars. Using Stirling’s approximation, our CNF bound can be expressed as

Again, using Stirling’s approximation, we observe that this is bigger than the information-theoretic bound of Tabei et al. [17], which is

By ignoring minor terms, our bound is $N{\log }_{2}N$ bits away from Tabei et al.’s method. However, in practice, our method can be both faster and smaller than Tabei et al.’s method, as will be seen in the next section.

In [3] Cleary et al. presented a modified version of the folklore algorithm for random access to grammar-compressed strings. Excluding the original folklore algorithm, which only works on CNF grammars, the implementation from [3], called Folklore Random Access for SLPs (FRAS), is currently the fastest random access algorithm in the literature. However, FRAS uses the array-of-arrays grammar representation and is subsequently not the smallest in practice. In this work we extend the FRAS implementation to include all three bit packing strategies described in the Algorithms section. FRAS is implemented in C++. Bitvectors and their respective rank and select data structures are implemented using the Succinct Data Structure Library (SDSL) [10]. The source code is available at https://github.com/alancleary/FRAS.

Reducing the encoding size of grammar-compressed strings in practice is the primary goal of this work. However, we also want to understand how our bit packed encodings affect decoding and random access run-time. For this reason, we compare FRAS to FOLCA [13] and ShapedSLP [7] – two grammar encodings that support random access. Notably, FOLCA achieves the information-theoretic bound of Tabei et al. [17]. Due to its use of the array-of-arrays grammar representation, when randomly accessing a substring FRAS only performs one random access operation to determine where the first character of the substring is located in the grammar. The rest of the substring is then acquired by decoding the grammar from that position. For this reason, comparing FRAS to FOLCA and ShapedSLP on multiple substring lengths across a variety of data sets should elucidate how our bit packed encodings affect both decoding and random access run-times.

We performed experiments on two corpora of data: the Pizza&Chili corpus²²2https://pizzachili.dcc.uchile.cl/ and a collection of pangenomes containing 12 yeast assemblies from the Yeast Population Reference Panel (YPRP) [20] and 1000 copies of Human chromosome 19 (c1000) [7]. For each corpus, we generated grammars and benchmarked FRAS against FOLCA and ShapedSLP, measuring encoding size and random access run-time. For the Pizza&Chili corpus, grammars were generated using Gonzalo Navarro’s implementation³³3https://users.dcc.uchile.cl/~gnavarro/software/repair.tgz of RePair [11] and Isamu Furuya’s implementation⁴⁴4https://github.com/izflare/MR-RePair of MR-RePair [6]. Detailed depth and size metrics for the grammars derived from each dataset can be found in Table 1. For the collection of pangenomes, grammars were generated using BigRePair [8]. Note that RePair and BigRePair generate RePair style grammars, whereas MR-RePair generates SLPs. The original array-of-arrays representation of FRAS is used as a baseline of comparison for the bit packed encodings; we will simply call it Array. For each grammar generated, we accessed substrings of length 1, 10, 100, and 1,000 at pseudo-random positions.⁵⁵5Pseudo-random numbers were generated on a uniform distribution using the xoroshiro128+ generator [2]. The generator was seeded so that the same numbers were used by every algorithm. We performed this procedure 10,000 times for each substring length and computed the average run-time. Experiments were run on a server with two AMD EPYC 7543 32-Core 2.8GHz (3.7GHz max boost) processors and 2TB of 8-channel DDR4 3200MHz memory running CentOS Stream release 9. Note that this server is excessively overpowered for these experiments and was used for the purpose of stability and accuracy of measurement. Similar results can be achieved on a consumer laptop.

Results are given in Table 2. The graphs in Figure 2 summarize the average encoding size and run-times for every algorithm, and the graphs in Figure 3 summarize the encoding sizes and run-times for all of the RePair algorithms on only the c1000 data set. We chose to highlight the c1000 results because it has the largest encodings and some of the slowest run-times across all algorithms, which we will use to emphasize the trade-offs and advantages of our encodings.

Generally, we found that all the bit packing strategies use significantly less space than the original array-of-arrays implementation (Array). Interestingly, BPL and BPRM achieved nearly identical sizes, each consistently about 50% smaller than BPR, although BPRM was slower than BPL across the board. In comparison, BPL and BPRM used significantly less space than FOLCA and ShapedSLP on every grammar. Although every bit packing strategy was slower than the original Array encoding, each one was much faster than FOLCA and ShapedSLP, with BPL being the fastest and BPRM being the slowest. While BPL is only slightly slower than Array, it uses considerably less space, as depicted in Figures 2 and 3. Moreover, BPL provided the best space-time trade-off of the three bit packing strategies. This, coupled with the fact that BPL can be computed online, makes it the most practical of the bit packing strategies. Furthermore, we observed that all FRAS bit packed encodings were both smaller and faster on MR-RePair grammars than on RePair grammars. This suggests that SLP grammars may be generally advantageous in practice and that designing encodings and algorithms that support these types of grammars is a worthwhile endeavor.

To expand on these finding, we first consider specific size differences. Note, however, that here we omit the Pizza&Chili artificial data sets due to the low precision of Table 2. For RePair grammars, we found that BPL is 1.58$\times$-4.69$\times$ smaller than FOLCA/ShapedSLP, and is 2.53$\times$ smaller on average. Similarly, BPR is 0.81$\times$-2.1$\times$ smaller than FOLCA/ShapedSLP, and is 1.22$\times$ smaller on average. And BPRM is 1.58$\times$-4.69$\times$ smaller than FOLCA/ShapedSLP, and is 2.54$\times$ smaller on average. For MR-RePair grammars, we found that MR-BPL is 2$\times$-10.33$\times$ smaller than FOLCA/ShapedSLP, and is 6.91x smaller on average. Similarly, MR-BPR is 2$\times$-4.89$\times$ smaller than FOLCA/ShapedSLP, and is 3.45$\times$ smaller on average. And MR-BPRM is 2$\times$-10.33$\times$ smaller than FOLCA/ShapedSLP, and is 6.91$\times$ smaller on average. These results are especially significant because the FOLCA grammar encoding achieves the information-theoretic bound, as described in Section 4, suggesting that our bit packed encodings can be implemented using minimal additional factors to those described in the bound.

To further expand on our finding, we consider specific run-time differences. For RePair grammars, we found that BPL is 2.23$\times$-17.83$\times$ faster than FOLCA/ShapedSLP, and is 4.87$\times$ faster on average. Similarly, BPR is 1.81$\times$-10.25$\times$ faster than FOLCA/ShapedSLP, and is 3.63$\times$ faster on average. And BPRM is 1.55$\times$-11.89$\times$ faster than FOLCA/ShapedSLP, and is 2.91$\times$ faster on average. For MR-RePair grammars, we found that MR-BPL is 5.17$\times$-26.75$\times$ faster than FOLCA/ShapedSLP, and is 8.96$\times$ faster on average. Similarly, MR-BPR is 3.77$\times$-17.83$\times$ faster than FOLCA/ShapedSLP, and is 6.28$\times$ faster on average. And MR-BPRM is 1.93$\times$-15.29$\times$ faster than FOLCA/ShapedSLP, and is 4.61$\times$ faster on average. Furthermore, every bit packed algorithm achieved submicrosecond run-times on at least one experiment, whereas FOLCA and ShapedSLP did not.

A property of all the algorithms that we observed is that their run-times scale linearly relative to the size of the query string, as illustrated in Figures 2 and 3. This suggests that the disparity in run-time between the bit packed encodings and FOLCA/ShapedSLP will also continue to grow with query size. Figures 2 and 3 also illustrate how our bit packed encodings affect decoding and random access run-time. When computing a random access query, FRAS only performs one random access operation to determine where the first character of the substring is located in the grammar. The rest of the substring is then acquired by traversing the grammar’s parse tree from that position. This means when querying the bit packed encodings, the first character in the substring will likely require many more bits to be unpacked than subsequent characters. However, this additional overhead is not perceptible for the BPL strategy and is barely present for the BPR and BPRM strategies, as illustrated by the size 1 queries in Figures 2 and 3. This shows that the overhead of the bit packed encodings is so negligible that it must be compounded over many character unpackings to make a discernible difference, i.e. query size 1000 in Figures 2 and 3. This makes the use of the bit packed encodings well worth the space savings they provide over the array-of-arrays representation.

In this work, we presented a general bit packing approach for reducing the space required to represent grammars in the canonical array-of-arrays representation. We then presented three bit packing strategies based on this approach and showed that our encodings are $N{\log }_{2}N$ away from the information-theoretic bound. Through our experiments, we demonstrated that in practice these bit packing strategies are much smaller than methods that meet the information-theoretic bound, achieving state-of-the-art performance both in grammar encoding size and run-time performance of random-access queries.

Our approach exploits the total ordering of the non-terminal characters in grammar-compressed strings. It is a simple and natural approach for encoding grammars and in this work we endeavored to characterize it. In future work, we would like to explore other methods for compactly encoding the array-of-arrays representation of grammar-compressed strings, such Elias-$\gamma$ and -$\delta$ codes or, more generally, variable bit-length arrays [4], as well as optimizations that could further improve the run-time performance of our approach, such as utilizing SIMD algorithms for bit packed encodings [12].