Substring Compression Variations and LZ78-Derivates
<|reference_start|>Substring Compression Variations and LZ78-Derivates: 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.<|reference_end|>
@article{köppl2024substring,
    title={Substring Compression Variations and LZ78-Derivates},
    author={Dominik K"oppl},
    journal={full version of conference paper published at DCC 2024},
    year={2024},
    doi={10.1109/DCC58796.2024.00021},
    archivePrefix={arXiv},
    eprint={2409.14649},
    primaryClass={cs.DS}
}