An upper bound and linear-space queries on the LZ-End parsing
Lempel–Ziv (LZ77) compression is the most commonly used lossless compression
algorithm. The basic idea is to greedily break the input string into blocks (called “phrases”) …
algorithm. The basic idea is to greedily break the input string into blocks (called “phrases”) …
Optimal LZ-End parsing is hard
LZ-End is a variant of the well-known Lempel-Ziv parsing family such that each phrase of the
parsing has a previous occurrence, with the additional constraint that the previous …
parsing has a previous occurrence, with the additional constraint that the previous …
Compressing and querying integer dictionaries under linearities and repetitions
We revisit the fundamental problem of compressing an integer dictionary that supports
efficient and operations by exploiting simultaneously two kinds of regularities arising in real …
efficient and operations by exploiting simultaneously two kinds of regularities arising in real …
On the Number of Factors in the LZ-End Factorization
P Gawrychowski, M Kosche, F Manea - International Symposium on String …, 2023 - Springer
Kreft and Navarro [DCC 2010] introduced a restricted variant of the well-known Lempel-Ziv
factorization, called the LZ-End factorization. Only recently Kempa and Saha [SODA2022] …
factorization, called the LZ-End factorization. Only recently Kempa and Saha [SODA2022] …
Indexing highly repetitive string collections
G Navarro - arXiv preprint arXiv:2004.02781, 2020 - arxiv.org
Two decades ago, a breakthrough in indexing string collections made it possible to
represent them within their compressed space while at the same time offering indexed …
represent them within their compressed space while at the same time offering indexed …
On the complexity and approximability of bounded access Lempel Ziv coding
F Cicalese, F Ugazio - … Conference on Developments in Language Theory, 2024 - Springer
We study the complexity of constructing an optimal parsing φ of a string s= s 1⋯ sn under the
constraint that given a position p in the original text, and the LZ76 (also known as LZ77 or …
constraint that given a position p in the original text, and the LZ76 (also known as LZ77 or …