LZ78 Substring Compression in Compressed Space
Hiroki Shibata, Dominik Köppl · 2025
Read LZ78 Substring Compression in Compressed Space by Hiroki Shibata, Dominik Köppl (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-17217.txt.
Introduction
Hiroki Shibata and Dominik Köppl work on LZ78, a classic method for compressing data that sits behind formats such as compress and GIF. Most past work splits a whole file into pieces from the start. The pair instead study a setup where an index is built once, and later a user asks for the split of just one chosen substring.
Their algorithm answers such queries while staying inside compressed space, so the data never has to be fully expanded. The cost is a slowdown that grows only with the logarithm of the size, close to the best possible time. The same approach covers close variants of LZ78 as well. Work like this helps tools search and reuse parts of very large compressed files.
Catalog record
| CREATOR | Hiroki Shibata, Dominik Köppl |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-17217
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
LZ78 Substring Compression in Compressed Space Hiroki Shibata, Dominik Köppl Abstract The Lempel–Ziv 78 (LZ78) factorization is a well-studied technique for data compression. It and its derivates are used in compression formats such as compress or gif . Although most research focuses on the factorization of plain data, not much research has been conducted on indexing the data for fast LZ78 factorization. Here, we study the LZ78 factorization and its derivates in the substring compression model, where we are allowed to index the data and return the factorization of a substring specified at query time. In that model, we propose an algorithm that works in compressed space, computing the factorization with a logarithmic slowdown compared to the optimal time complexity. 1 Introduction The substring compression problem [ 13 ] is to preprocess a given input text T such that computing a compressed version of a substring of T[i..j] can be performed efficiently. This problem has been originally stated for the Lempel–Ziv-77 (LZ77) factorization [ 41 ] , but extensions to the generalized LZ77 factorization [ 23 ] , the Lempel–Ziv 78 (LZ78) factorization [ 27 ] as well as two of its derivates [ 28 ] , the run-length encoded Burrows–Wheeler transform (RLBWT) [ 2 ] , and the relative LZ factorization [ 26 , Sect. 7.3] have been studied. Given that n is the length of T , a trivial solution would be to precompute the compressed output of T[\mathcal{I}] for all intervals \mathcal{I}\subseteq[1..n] . This, however, gives us already \mathop{}\mathopen{}\mathup{\Omega}\mathopen{}\left(n^{2}\right) solutions to store. For an appealing solution, we want to be able to index a large amount of data efficiently within a fraction of space; two criteria (speed and space) that are likely to be anti-correlated. However, as far as we are aware, the substring compression problem has not yet been studied with compressed space bounds that can be sublinear for compressible input data. Our main target is therefore a solution that works in compressed space and can answer a query in time linear in the output size with a polylogarithmic term on the text length. In this paper, we build upon the line of research on LZ78 factorization algorithms that superimpose the LZ trie on the suffix tree [ 33 , 18 , 27 , 28 , 29 ] , which all use the \mathop{}\mathopen{}\mathup{\Omega}\mathopen{}\left(n\right) space (in words) to store the suffix tree. Here, we make the algorithmic idea of the superimposition compatible with the compact directed acyclic word graph (CDAWG) [ 10 ] , trading a tiny time penalty with a large space improvement for compressible texts. Furthermore, we generalize the LZ78 substring compression algorithm to work with any data structure that can perform a limited set of suffix tree operations. As a result, we obtain alternative solutions for computing the LZ78 substring compression. We also apply the proposed method for LZ78 substring compression to LZD [ 22 ] and LZMW [ 32 ] compression, which are derivates of the LZ78 factorization. table 1 summarizes both known and newly proposed solutions for the substring compression problem of LZ78, LZD, and LZMW. Table 1: Solutions for computing the LZ78 (or alternatively LZD, or LZMW) substring compression for a string of length n over an alphabet of size \sigma , with z LZ78 (LZD, or LZMW) factors, e CDAWG edges, r BWT runs, and having substring complexity \delta [ 12 ] . Extra space means the additional working space required for processing queries in addition to the index. All space complexities are measured in words. method space time index extra space query naive {\mathop{}\mathopen{}\mathup{\Omega}\mathopen{}\left(n^{2}\right)} {\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(z\right)} {\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(z\right)} Köppl [ 27 ] {\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(n\right)} {\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(z\right)} {\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(z\right)} theorem 4 {\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(e\right)} {\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(z\right)} {\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(z\lg n\right)} theorem 5 {\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(r\lg\frac{n}{r}\right)} {\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(z\right)} {\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(z\left(\lg\lg\frac{r}{\lg n}+\lg\frac{n}{r}+\lg z\right)\right)} theorem 6 {\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(\delta\lg\frac{n\lg\sigma}{\delta\lg n}\right)} {\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(z\right)} {\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(z\lg^{4+\varepsilon}n\right)} Our contribution fits into the line of research focused on data compression with the CDAWG. Given e and z are the number of edges of the CDAWG and the number of LZ78 factors, respectively, in that line, [ 7 ] proposed a straight-line program (SLP), which can be computed in \mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(e\right) time taking \mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(e\right) words of space. Given an SLP of size \mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(g\right) , [ 4 ] showed how to compute LZ78 from that SLP in \mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(g+z\lg z\right) time and space. Combining both solutions, we can compute LZ78 from the CDAWG in \mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(e+z\lg z\right) time and space. Recently, [ 1 ] showed how to compute, among others, the RLBWT and LZ77 in \mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(e\right) time and space. Beyond LZ78, variants such as LZD [ 22 ] and LZMW [ 32 ] have been introduced to improve compression performance. Both factorizations represent each factor as the concatenation of two previous factors. Since the length of each factor can grow exponentially in the best case, the lower bound on the number of factors becomes \mathop{}\mathopen{}\mathup{\Omega}\mathopen{}\left(\log n\right) . This is significantly smaller than the lower bound for standard LZ78 factorization, which is \mathop{}\mathopen{}\mathup{\Omega}\mathopen{}\left(\sqrt{n}\right) . However, while the standard LZ78 factorization can be computed in an online manner in O(n) time using O(z) additional words of space where z is the number of LZ78 factors, computing these two variants within the same additional space is more difficult. [ 3 ] showed that the greedy algorithm for these variants takes \Omega(n^{5/4}) time in the worst case. The fastest known solution for this problem runs in expected O(n+z^{\prime}\log^{2}n) time, where z^{\prime} is the size of the corresponding parsing [ 3 ] . This gap in the computational complexity motivates the investigation into the possibility of computing these factorizations in compressed space. We also note that our research can be viewed as a practical application of compressed suffix trees. The majority of the queries needed to compute substring compressions correspond to standard suffix tree operations. Indeed, the compressed indexes we employ can be seen as specific instances or variants of compressed suffix trees. Our approach shows how to maintain the LZ78, LZD, and LZMW tries within this framework, leveraging the capabilities of these compressed structures. This perspective not only unifies different parsing algorithms but also broadens the applicability of compressed suffix tree-based methods. This article is an extended version of our contribution [ 39 ] to the SPIRE’24 conference. Our extension is as follows. First, we have adapted our techniques for substring compression to LZD and LZMW. Second, we formulate an abstract data type for the data structure we need for our algorithm computing the substring compression for any of the addressed compression types (LZ78/LZMW/LZD). We subsequently provide examples of implementations other than CDAWGs for this abstract data type. Finally, we provide additional experimental results. 2 Preliminaries With \lg we denote the logarithm \log_{2} to base two. Our computational model is the word RAM model with machine word size \mathop{}\mathopen{}\mathup{\Omega}\mathopen{}\left(\lg n\right) bits for a given input size n . Accessing a word costs \mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(1\right) time. Unless stated otherwise, we measure space complexity in words rather than bits. Let T be a text of length |T|=n whose characters are drawn from an integer alphabet \Sigma=[1..\sigma] with \sigma\leq n^{\mathop{}\mathopen{}\mathcal{O}\mathopen{}\left(1\right)} . Given X,Y,Z\in\Sigma^{*} with T=XYZ , then X , Y and Z are called a prefix , substring and suffix of T , respectively. We call T[i..] the i -th suffix of T , and denote a