Substring Compression Variations and LZ78-Derivates
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929509859590144 |
|---|---|
| author | Köppl, Dominik |
| author_facet | Köppl, Dominik |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_14649 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Substring Compression Variations and LZ78-Derivates Köppl, Dominik Data Structures and Algorithms 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. |
| title | Substring Compression Variations and LZ78-Derivates |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2409.14649 |