Papers › LZD-style Compression Scheme with Truncation and Repetitions
LZD-style Compression Scheme with Truncation and Repetitions
Linus Götz, Dominik Köppl
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
Lempel-Ziv-Double (LZD) is a variation of the LZ78 compression scheme that achieves better compression on repetitive datasets. Nevertheless, prior research has identified computational inefficiencies and a weakness in its compressibility for certain datasets. In this paper, we introduce LZD+, an enhancement of LZD, which enables expected linear-time online compression by allowing truncated references. To avoid the compressibility weakness exhibited by a lower bound example, we propose LZDR (LZD-runlength compressed), a further enhancement on top of LZD+, which introduces a repetition-based factorization rule while maintaining linear expected time complexity. The both time bounds can be de-randomized by a lookup data structure like a balanced search tree with a logarithmic dependency on the alphabet size. Additionally, we present three flexible parsing variants of LZDR that yield fewer factors in practice. Comprehensive benchmarking on standard corpora reveals that LZD+, LZDR, and its flexible variants outperform existing LZ-based methods in the number of factors while keeping competitive runtime efficiency. However, we note that the difference in the number of factors becomes marginal for large datasets like those of the Pizza&Chili corpus.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections