We study the complexity of constructing an optimal parsing of a string under the constraint that given a position p in the original text, and the LZ76 (also known as LZ77 or simply Lempel-Ziv) encoding of T based on , it is possible to identify/decompress the character by performing at most c accesses to the LZ encoding, for a given integer c. We refer to such a parsing as a c-bounded access LZ parsing or c-BLZ parsing of We show that for any constant c the problem of computing the optimal c-BLZ parsing of a string, i.e., the one with the minimum number of phrases, is NP-hard and also APX hard, i.e., no PTAS can exist under the standard complexity assumption We also study the ratio between the sizes of an optimal c-BLZ parsing of a string and an optimal LZ76 parsing of (which can be greedily computed in polynomial time).
On the Complexity and Approximability of Bounded Access Lempel Ziv Coding
Cicalese, Ferdinando;
2024-01-01
Abstract
We study the complexity of constructing an optimal parsing of a string under the constraint that given a position p in the original text, and the LZ76 (also known as LZ77 or simply Lempel-Ziv) encoding of T based on , it is possible to identify/decompress the character by performing at most c accesses to the LZ encoding, for a given integer c. We refer to such a parsing as a c-bounded access LZ parsing or c-BLZ parsing of We show that for any constant c the problem of computing the optimal c-BLZ parsing of a string, i.e., the one with the minimum number of phrases, is NP-hard and also APX hard, i.e., no PTAS can exist under the standard complexity assumption We also study the ratio between the sizes of an optimal c-BLZ parsing of a string and an optimal LZ76 parsing of (which can be greedily computed in polynomial time).
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
