Efficient Large-Scale Text Precompression via Approximate LZ77 Parsings

We process $S$ blockwise using block size $B=𝒪\left(n/s\right)$ such that a block fits into RAM. Each block is further partitioned into $p$ workloads, i.e., one per thread.

Every thread scans its workload using a sliding window of length $w$ to identify trigger strings. To enable fast modulus operations for computing fingerprints and for identifying trigger strings, we (1) require $q$, the prime for computing Karp-Rabin fingerprints, be a Mersenne prime (one less than a power of two) and (2) require $s$, the sampling parameter for trigger string detection, be a power of two. For every input character, we update two fingerprints. We maintain a rolling trigger fingerprint for the sliding window to identify a trigger string. We chose to represent these in 32 bits, as these are very fast to compute and fingerprint collisions can safely be ignored for this use case. For this, we choose the prime $q_{\text{trigger}}:=2^{31}-1$, the largest Mersenne prime to fit into a 32-bit word.

Furthermore, we maintain a metacharacter fingerprint that represents a metacharacter – from the beginning of the last trigger string until the end of the next – in later steps. We do care about collisions here: Collisions of metacharacter fingerprints will cause different metacharacters to be treated as being equal, ultimately leading to an output that cannot be decoded back to the original input (our implementation is Monte Carlo and produces correct results only w.h.p.). Thus, we represent these as 64-bit integers using the Mersenne prime $q_{\text{meta}}:=2^{61}-1$, which is the largest to fit into 64 bits and large enough to lower the chance of collisions to the point where we never observed any in practice¹¹1If the fingerprint base is a power of two (e.g., 256, a common choice for byte alphabets), then modular arithmetics with the Mersenne prime $2^{61}-1$ (a sequence of 61 set bits, the most significant byte being 31), in combination with the ASCII encoding of capital versus small letters (e.g. $\text{ASCII}(\text{A})-\text{ASCII}(\text{a})=32$), cause a clustering of fingerprint collisions for ASCII-encoded text. This may seem surprising, but follows directly from the definitions. As an example, consider the strings The␣Work and the␣Worl, which have the same fingerprint $modq$ with base 256. We therefore enforce the base is not a power of two. .

Special care needs to be taken at block boundaries as well as workload boundaries. Simply cutting off metacharacters at these boundaries would be harmful to our goal of compressing $S$, thus each thread may scan beyond its own workload until it finds the next trigger string ($𝒪\left(s\right)$ extra steps in expectation). At a block boundary, the last thread leaves information (starting position and fingerprint of the current metacharacter’s prefix up to the boundary) for the first workload of the next block to smoothly detect metacharacters across blocks.

The result of this step is a preliminary parsing that consists of $p\lceil n/B\rceil$ sequences of metacharacters defined by their starting positions, lengths (including the trigger strings at the borders) and metacharacter fingerprints. Because the threads do not communicate, there has been no deduplication regarding equal metacharacters yet. We address this next.

The next step is finding the set $𝒳$ of distinct metacharacters. At the same time, we want to produce the parsing $P$ as a sequence of pointers into $𝒳$, preferably represented as integers from $[1,|𝒳|]$. To solve this in parallel, we looked at a similar problem from a preliminary step of constructing wavelet trees, which we can formalize as follows.

Given a sequence $𝒮=s_1\mathrm{\cdots }{s}_n\in {\mathbb{N}}^N$ of some length $N\in \mathbb{N}$, we want to

1. 1.

   identify the smallest set $X\subseteq \mathbb{N}$ such that $𝒮\in X^N$ (effective alphabet),

2. 2.

   precompute a bijective function $f:X\to [1,|X|]$ (effective mapping) and then

3. 3.

   produce the sequence $f(S)=f(s_1)\mathrm{\cdots }f(s_n)\in {[1,|X|]}^N$ (effective transform).

To make use of multiple threads, we borrow the solution from [10, Section 7] for distributed memory. We first partition the metacharacter sequences from the previous step in $p$ parts and independently compute $p$ hash tables representing the sets ${𝒳}_i$ of distinct metacharacters for every part $i\in [1,p]$ (in the hash tables, we map metacharacter fingerprints to their position of occurrence and length). We then merge the hash tables in a parallel all-reduce operation. Conceptually, this can be done using a merge tree of height $𝒪\left(\lg p\right)$ [44]; in our implementation, we use the reduction framework of OpenMP [42] When merging two hash tables, we tie-break metacharacters with the same fingerprints by preferring the leftmost occurrence. The bijection $f$ is computed in sequential, but that can already be done in time $𝒪\left(|𝒳|\right)$. The parsing $P$ is then the effective transform, which can straightforwardly be computed in parallel by applying $f$ to every metacharacter.

We now load the dictionary $𝒟$ from the input file which stores $S$. The size $|𝒟|$ can be computed as a byproduct of the previous step so that we can accurately pre-allocate memory. Since we want to make no assumption about the storage (e.g., hard disk, SSD, NVMe), we load sequentially. First, we sort the metacharacters of $𝒳$ by their starting position in $S$ in parallel (using std::sort and the parallel execution policy), then we load them in this order to ensure sequential reads of the input file.

With $𝒟$, we proceed to sort the metacharacters lexicographically in parallel, again using the C++ STL. (We are aware of sophisticated parallel string sorters (e.g., [5]), but decided not to put to use an external implementation for a task that accounts only for a tiny fraction of the total running time.) With this, we have effectively computed function lexrank from Section 3 and can compute $P^{\prime }$ from $P$ in parallel by partitioning $P$ into equisized workloads.

Before we can finally compute the approximate LZ77 parsing of $S$, we need to compute the LZ77 parsing of $P^{\prime }$. We first construct its suffix array using libsais [18], a highly engineered implementation of the SA-IS [39] algorithm that features integer alphabets (which we have in $[1,𝒳|]$). We do use libsais’ parallel implementation for OpenMP, but the author claims that it is essentially memory-bound and no noteworthy speedups are to be expected. (We are aware of Bertram et al.’s modification of GSACA [1], which features good parallel speedup [2]. In our experiments, however, it was still clearly outperformed by libsais). From the suffix array, we can compute the inverse in parallel.

We now partition $P^{\prime }$ into $p$ workloads. Every thread processes its workload using an algorithm similar to KKP [25] and produces a sequence of potential copy phrases for $S$. The differences to KKP are twofold: first, we work only using the suffix array and its inverse, which allows us to operate in parallel. We do not precompute next/previous smaller values or the LCP array, but compute the necessary values on the fly by scanning the suffix array or the parsing, respectively. Second, we inline the conversion of copy phrases as follows.

Assume that at some position $i^{\prime }\in [1,m]$ we want to output a copy phrase $(j^{\prime },{\mathrm{\ell }}^{\prime })$ with . Note that $i^{\prime }$, $j^{\prime }$ and ${\mathrm{\ell }}^{\prime }$ pertain to the parsing $P^{\prime }$, i.e., metacharacters. We can translate $i^{\prime }$ and $j^{\prime }$ to their corresponding positions $i$ and $j$ in $S$ using a mapping computed (and stored alongside $P^{\prime }$) as a byproduct of computing the parsing (Section 4.2). Furthermore, let $\mathrm{\ell }={\sum }_{k=i^{\prime }}^{i^{\prime }+{\mathrm{\ell }}^{\prime }-1}|X_k|$, which we can compute directly from the parsing. By the fact that the suffix array of $P^{\prime }$ is a sparse suffix array of $S$, the copy phrase $(j,\mathrm{\ell })$ indeed corresponds to a repeated occurrence of $S[j..j+\mathrm{\ell }-1]$ at position $i$ in $S$.

Even though the set $𝒳$ of metacharacters is prefix-free, it can occur that the prefix of one metacharacter is the suffix of another or vice versa even beyond the the trigger string that they may have in common. If this occurs at the beginning or the end of the copy phrase, we can greedily expand the copy phrase accordingly on the character level (as shown in the bottom part of Figure 2). The necessary accesses to $S$ can be simulated via $P^{\prime }$ and $𝒟$ if we store a mapping from lexicographic rank to the corresponding entry in $𝒟$, which we can compute as a byproduct when sorting the dictionary (Section 4.3).

It is important to note that around workload boundaries, because threads do not communicate, we may introduce multiple copy phrases replacing the same position. This will be handled in the following step.

It remains to encode the copy phrases produced in the previous step. Again, we make no assumption about the storage (which may be a pipe) and thus do this in sequential. Because the workloads were assigned left to right and each thread processed its workload left to right, it holds that the copy phrases are in input order. We can thus simultaneously stream the input and the copy phrases and greedily encode a copy phrase whenever possible, or otherwise copy literal characters directly from the input. Overlapping copy phrases around workload boundaries in the previous step are truncated accordingly in the process. If more than one copy phrase is available starting at the current position, we greedily take one that maximizes the copy length (as shown in Figure 2).

We implement only a straightforward encoding where we keep uncompressed characters byte-aligned and encode copy phrases using VByte codes (a VByte code for the copy length followed by a VByte code for the copy source, given as the distance from the phrase’s starting position). The intention is that a downstream standard compressor (such as gzip) takes care of a succinct encoding. We consider two different ways of encoding strings of uncompressed characters. The straightforward approach is to collapse them: we first encode the number of uncompressed characters to be decoded, followed by the string. This works best for LZ-based encoders (e.g., gzip and zstd). Interestingly, for encoders based on block sorting (e.g., bzip2 and bsc), we achieved better overall compression by preceding every uncompressed character by a zero byte individually, generating higher redundancy.

If the input $S$ is sufficiently small to be loaded in RAM, we can allow random access on $S$. In this case, there is no need to process $S$ blockwise in the first step (Section 4.1). Furthermore, we can skip loading the dictionary for sorting the metacharacters (Section 4.3), as we can instead use pointers into $S$. Lastly, because we no longer need to simulate accesses via $P^{\prime }$ and $𝒟$, but simplify left and right extension when computing copy phrases (Section 4.4) accessing $S$ directly, potentially saving a number of cache misses.

Our experiments are conducted on a Ubuntu 24.04 system with two AMD EPYC 7452 CPUs (32/64x 2.35-3.35GHz, 2/16/128MB L1/2/3 cache) featuring up to 128 threads, and 1TB of RAM (3200 MT/s DDR4). All software is compiled using the GNU compiler collection (gcc) version 13.3.0 with flags for maximum optimization (-O3 -DNDEBUG -march=native).

Before comparing alz to the competitors, we evaluate the impact of the main parameters to the running time of the individual steps of alz according to Section 4: the sampling parameter $s$ that governs the size of the PFP (and the average length of a metacharacter), and the number $p$ of available threads. We evaluate this on the largest possible input, which is sars (approximately $57\mathrm{GiB}$). The results are shown in Figure 3.

We first look at Figure 3(a), showing the impact of the sampling parameter $s$ on the relative running times of each step in relation to the total running time (later given and discussed in Section 5.3) using the maximum number of available threads (128). Recall that the parsing size is $n/s$ in expectation; for sars, this holds almost precisely for all $s$. For small $s$, we see that computing the suffix array of the parsing dominates the running time ($91\%$ for $s=2$), rendering the other steps nearly negligible except for computing the LZ77 parsing. This is the expected behaviour as the parsing approaches the size of the input. On the other extreme that we consider ($s=2^9$), suffix array construction takes even less time than loading the dictionary from disk or computing the set of trigger strings that later defines the parsing. Here, encoding becomes the dominating step taking about $42\%$ of the running time, which is also expected since we have fewer copy phrases and encoding is mostly reduced to Huffman-coding large uncompressed portions of the input.

Figure 3(b) shows the parallel speedup of the individual steps. Here, we fixed an exemplary sampling rate of $s=2^6$, which yields a reasonable balance of work to do in every step when using all threads, as seen in Figure 3(a). The preliminary parsing that detects and takes note of trigger strings benefits the most from multiple threads, which is expected given the linearity of the task (computing fingerprints and pushing metacharacter borders to a thread-private list). Still, at $p=128$, we only achieve a speedup of about 16, where it also appears to plateau, likely because of being memory-bound. Using a binary merge tree to find the set of distinct metacharacters appears to achieve the desired affect of logarithmic speedups up to $p=12$. The speedups for representing the parsing as lexicographic ranks (concurrent reading from a hash table) as well as computing the approximate LZ77 parsing (via suffix array and dictionary) are rather disappointing, but given the fact that these steps involve mostly random access, this is likely an indication that these steps are memory-bound. This is also the case for suffix sorting, confirming the statement of the author of (libsais) that no speedup can be expected. At the very least, computing the inverse suffix array does benefit somewhat from parallelization. Overall, we can reduce the running time of alz to almost a third using 32 threads; using more, however, does not yield much benefit. In a productive environment, it may be advisable to do some steps in sequential to reduce potential overhead coming from parallelization²²2We thank the anonymous reviewer for noting this. .

We now evaluate alz with different sampling parameters $s$ against the competitors (pfp-lz77, relz and ssszip) regarding running time, peak memory usage and approximation of the LZ77 parsing for all input files. We set the block size for the preliminary parsing (Section 4.1) to $B:=\min \{n/2,1\mathrm{GiB}\}$ (and thus do not take advantage of Section 4.6). Recall how alz does not do any sophisticated encoding in itself but is designed to have its output encoded by a downstream successor (see Section 4.5). For a fair running time comparison, in this experiment, we configure ssszip to use pigz (parallel gzip) as its encoder with the -0 flag for no compression. The encodings of pfp-lz77 and relz are already straightforward: pfp-lz77 writes phrases as source and length pairs of $\lceil \log n\rceil$ bits each, while relz encodes these pairs using VByte codes. Similarly, rle-lz77-o encodes phrases of pairs of 32-bit integers³³3This does mean that the output of rle-lz77-o cannot be decoded for input files $\ge 2\mathrm{GiB}$. We conjecture this to be an oversight in the implementation, but double-checked that it affects only the output. The entire prior computation of the parsing is done using 64-bit integers, i.e., the results are still meaningful. .

Figure 4 shows the average running times over three executions (except for pfp-lz77 and rle-lz77-o on inputs of size $16\mathrm{GiB}$ and up, where they required over 10 hours and were only executed once). Even for the rather impractical sampling rate of $2$, alz is faster than pfp-lz77 by an order of magnitude on prefixes of sars. On the smaller inputs, pfp-lz77 is always slower when our sampling rate is $4$ or higher. For different sampling rates, the running time of our implementation behaves consistently for almost every input as already seen in Figure 3(a) for sars. For very high sampling rates ($s\ge 2^9$), the encoding begins to dominate the overall running time (see Section 5.2) causing the alz to become slower in some cases (e.g., cere). For the large inputs, ssszip is about as fast as alz with a sampling rate of $2^5$; for other inputs, this varies. Their repetitiveness seems to benefit relz, which becomes competitive only for the large inputs but runs relatively slowly for the smaller corpus. On all inputs, topk-lz77 is comparatively slow and rle-lz77-o is the slowest for most inputs as expected. Remarkably, however, rle-lz77-o outperforms pfp-lz77 on longer prefixes of sars despite using only a fraction of the memory.

Next, we look at peak memory consumption shown in Figure 5. For small sampling rates ($s⪅2^3$), alz requires more memory than pfp-lz77, which is excessive considering that we only compute an approximation of LZ77, albeit much faster. The memory footprint becomes more reasonable at around $s=2^7$, where for many inputs, it approaches or falls below the size of the input. We see that our strategy to pre-parse blockwise and only load the dictionary into RAM pays off: The space is dominated by the size of the PFP and the dictionary. For suitable $s$, this allows us to work in memory less than the input size (e.g., sars for $s\ge 2^6$). However, it must be noted that this behaviour depends on the size of the dictionary, and hence ultimately on the repetitiveness of the input. In any event, we have an advantage over ssszip, which always fully loads the input into RAM. In relz, memory consumption is constrained to $8000\mathrm{MB}$ by making use of external memory if needed. This becomes apparent for the longer prefixes of sars. Unsurprisingly, rle-lz77-o uses the least memory in all instances as it works in compressed space. Furthermore, topk-lz77 always uses space somewhat less than the input size as configured.

Judging by the results thus far, it appears that $s=2^6$ is a good time/space trade-off for alz, yielding acceptable running times and memory consumption for all inputs.

Preparing to evaluate compression in the next section, we look at the approximation of the LZ77 parsing displayed in Figure 6. Already for $s=2^4$, the number of phrases produced by alz is more than ten times that of the exact LZ77 parsing (which is computed by pfp-lz77). This effect is somewhat diminishing: when doubling the sampling rate (e.g., $2^5$), we do not double the number of phrases, which is also thanks to left and right extension of copy phrases as described in Section 4.4.

We recall that ssszip follows a similar strategy as our implementation. It uses the (hardcoded) parameter $\tau =512$ for computing the string synchronizing set. This leads us to conjecture that the resulting parsing should be roughly comparable to alz using a sampling rate of $s=512=2^9$. In direct comparison to that, ssszip is significantly slower on most inputs and has a greater memory footprint. However, it appears to be better than alz at capturing long copy phrases, producing less phrases overall. As stated earlier, relz computes the exact LZ77 parsing for sufficiently small inputs and only approximates it if a memory threshold would be exceeded. This is the case, e.g., for the prefixes of sars. However, the approximation ratio clearly remains very small ($1.45$ for sars).

Given the results from the previous section, particularly regarding the number of produced phrases, we now get to the most interesting experiment that evaluates the compression ratio, which we define as the size of the output file divided by the size of the input file.

For this experiment, we use alz with sampling parameter $s=2^6$ and encode its output using the following the standard compressors zstd (Facebook’s ZStandard compressor [9]) and bsc (a highly engineered block-sorting compressor [17]). They are run with flags to achieve the best compression (i.e., -19 for zstd and -b2047e2 for bsc). We apply our observations from Section 4.5 and produce a slightly different intermediate encoding for the LZ-based compressor (zstd) and that based on sorting (bsc). Note that we considered further standard compressors (namely pigz, xz and bzip2) in preliminary experiments. They are omitted for the sake of readability of the plot because they were not competitive. Because the output of rle-lz77-o is correct only for inputs of size less than $2\mathrm{GiB}$ (see footnote 3) and the encoding is naïve, we omit it in this experiment as well.

By default, ssszip, uses zstd for encoding (we also pass -19 here for best compression). To level the playing field, we also plug in bsc as its encoder (passing also -b2047e2). Furthermore, we also apply zstd and bsc to the output of ReLZ. To argue about the usefulness of precompression via alz (or ssszip) in the first place, we also compress all files with just those standard compressors.

Figure 7 shows compression time versus compression ratio for all competitors and inputs. Our pipeline alz|bsc produces the smallest outputs for all files except influenza, where it is only marginally surpassed by zstd (albeit much slower) and bsc itself (on par). As expected, computing the exact LZ77 factorization is always a comparatively slow approach (pfp-lz77, but also relz for the files from the Pizza & Chili corpus). On the largest input, sars, we can clearly see that computing the exact parsing is completely impractical, pfp-lz77 taking several orders of magnitude longer than all other compressors.

Our conceptually close competitor ssszip yields varying results: encoding using bsc appears to be faster than the default zstd, but the compression ratio appears to be indifferent to that. On some inputs, ssszip is competitive (namely influenza, kernel and para) while on others, it is clearly slower than our alz pipelines (e.g., einstein.en.txt or sars). Similar observations can be made for relz and topk-lz77. While they achieve competitive compression, they are overall slower than alz.