An Upper Bound and Linear-Space Queries on the LZ-End Parsing.

Area of Science:

• Data Compression
• String Algorithms
• Information Theory

Background:

• Lempel-Ziv (LZ77) is a widely used lossless compression algorithm based on phrase matching.
• LZ-End, a variant of LZ77, imposes stricter conditions on phrase occurrences, showing practical promise.
• A theoretical upper bound relating LZ-End compression size to LZ77 size was previously unknown.

Purpose of the Study:

• To establish a provable upper bound for LZ-End compression in terms of LZ77 compression.
• To develop efficient data structures for querying LZ-End compressed data.
• To explore bounds for LZ-End variants and other compression measures.

Main Methods:

• Mathematical proof to derive the relationship between the number of phrases in LZ-End and LZ77 parsings.
• Development of a novel data structure for random access and longest-common-extension (LCE) queries.
• Analysis of LZ-End variants and alternative compression metrics.

Main Results:

• A non-trivial upper bound is proven: the number of LZ-End phrases is upper-bounded by the number of LZ77 phrases.
• A linear-size data structure is introduced, supporting random access queries in time.
• The techniques enable efficient LCE queries on LZ-End compressed data.

Conclusions:

• LZ-End is positioned among the strongest dictionary compressors due to the established theoretical bound.
• The new data structure offers efficient querying capabilities for LZ-End compressed texts, overcoming previous limitations.
• The findings advance the understanding of LZ-End compression and its applications in compressed data structures.