# Substring Compression Variations and LZ78-Derivates

Source: [Substring Compression Variations and LZ78-Derivates](<https://www.sota2.com/research/paper/68fa74ea1e209131cea64b80>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-26T03:22:19.696Z

Authors: Dominik K\\"oppl

Published: 2024-09-23T01:29:56.000Z

## Abstract

We propose algorithms computing the semi-greedy Lempel-Ziv 78 (LZ78), the Lempel-Ziv Double (LZD), and the Lempel-Ziv-Miller-Wegman (LZMW) factorizations in linear time for integer alphabets. For LZD and LZMW, we additionally propose data structures that can be constructed in linear time, which can solve the substring compression problems for these factorizations in time linear in the output size. For substring compression, we give results for lexparse and closed factorizations.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2409.14649>)

[PDF](<https://arxiv.org/pdf/2409.14649.pdf>)
