An Upper Bound and Linear-Space Queries on the LZ-End Parsing
An Upper Bound and Linear-Space Queries on the LZ-End Parsing
复制标题
LZ端解析的上界和线性空间查询
DOI：
10.1137/1.9781611977073.111
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
and Saha, Barna
中科院分区：
文献类型：
--
作者：
Kempa, Dominik;and Saha, Barna
Lempel-Ziv (LZ77) 压缩是最常用的无损压缩算法。基本思想是贪婪地将输入字符串分成块（称为“短语”），每次将较早出现的未处理部分的最长前缀形成为短语。 2010 年，Kreft 和 Navarro 引入了 LZ77 的一个变体，称为 LZ-End，它还要求之前出现的每个短语在已存在短语的边界处结束。由于其作为压缩算法和压缩索引的出色实用性能，他们推测它实现了可证明 LZ77 大小上限的压缩。尽管最近在理解其他压缩算法（例如游程编码的 Burrows–Wheeler 变换）的这种关系方面取得了进展，但 LZ-End 还没有这样的结果。我们证明，对于任何长度为 n 的字符串，LZ-End 解析中的短语数满足 ，其中 z 是 LZ77 解析中的短语数。这使得 LZ-End 跻身最强大的字典压缩器之列，并解决了 Kreft 和 Navarro 长达十年之久的开放问题。使用我们的技术，我们还得出 LZ-End 的其他变体以及其他压缩措施的界限。我们的第二个贡献是一个数据结构，它实现了在空间和时间上对文本的随机访问查询。这是 LZ-End 上第一个有效实现此类查询的线性大小结构。所有以前的数据结构要么在空间中产生对数惩罚，要么查询速度慢。我们还展示了如何扩展这些技术以支持最长公共扩展 (LCE) 查询。
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”), every time forming as a phrase the longest prefix of the unprocessed part that has an earlier occurrence. In 2010, Kreft and Navarro introduced a variant of LZ77 called LZ-End, that additionally requires the previous occurrence of each phrase to end at the boundary of an already existing phrase. Due to its excellent practical performance as a compression algorithm and a compressed index, they conjectured that it achieves a compression that can be provably upper-bounded in terms of the LZ77 size. Despite the recent progress in understanding such relation for other compression algorithms (e.g., the run-length encoded Burrows–Wheeler transform), no such result is known for LZ-End.We prove that for any string of lengthn, the numberzeof phrases in the LZ-End parsing satisfies , wherezis the number of phrases in the LZ77 parsing. This puts LZ-End among the strongest dictionary compressors and solves a decade-old open problem of Kreft and Navarro. Using our techniques we also derive bounds for other variants of LZ-End and with respect to other compression measures. Our second contribution is a data structure that implements random access queries to the text in space and time. This is the first linear-size structure on LZ-End that efficiently implements such queries. All previous data structures either incur a logarithmic penalty in the space or have slow queries. We also show how to extend these techniques to support longest-common-extension (LCE) queries.