At the roots of dictionary compression: string attractors
At the roots of dictionary compression: string attractors
复制标题
字典压缩的根源：字符串吸引子
DOI：
10.1145/3188745.3188814
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
N. Prezza
中科院分区：
文献类型：
--
作者：
Dominik Kempa;N. Prezza
无损文本压缩领域的一个众所周知的事实是，当输入包含长重复时，高阶熵是一个弱模型。受这一事实的推动，数十年的研究已经产生了无数所谓的字典压缩器：能够通过利用文本的重复性来减小文本大小的算法。 Lempel-Ziv 77 是此类工具中最成功和最著名的工具之一，其次是直线程序、游程 Burrows-Wheeler 变换、宏方案、拼贴系统和紧凑有向无环字图。在本文中，我们展示了这些技术是针对相同的、优雅的组合问题的不同解决方案：找到捕获所有不同文本子字符串的一小组位置。我们将这样的集合称为弦吸引子。我们首先展示字典压缩器和字符串吸引子之间的减少。这给出了字典压缩器相对于最小字符串吸引子的近似比率，并允许我们发现不同字典压缩器的输出大小之间的新渐近关系。然后，我们证明 k 吸引子问题（决定文本是否具有捕获长度最多为 k 的所有子串的大小为 t 的位置集）对于 k≥ 3 而言是 NP 完全的。这尤其包括完整字符串吸引子问题。我们提供了几种最小 k 吸引子的逼近技术，表明该问题对于常数 k 是 APX 完全的，并给出了很强的不可逼近性结果。总之，我们为字符串吸引子的随机访问问题提供了匹配的下限和上限。通过显示支持最佳时间查询的数据结构来证明上限。我们的数据结构是通用的：通过减少字符串吸引子，它支持任何字典压缩方案的随机访问。特别是，它也匹配 LZ77、直线程序、拼贴系统和宏方案的下界，因此基本上（立即）解决了所有这些压缩器的随机访问问题。
A well-known fact in the field of lossless text compression is that high-order entropy is a weak model when the input contains long repetitions. Motivated by this fact, decades of research have generated myriads of so-called dictionary compressors: algorithms able to reduce the text’s size by exploiting its repetitiveness. Lempel-Ziv 77 is one of the most successful and well-known tools of this kind, followed by straight-line programs, run-length Burrows-Wheeler transform, macro schemes, collage systems, and the compact directed acyclic word graph. In this paper, we show that these techniques are different solutions to the same, elegant, combinatorial problem: to find a small set of positions capturing all distinct text’s substrings. We call such a set a string attractor. We first show reductions between dictionary compressors and string attractors. This gives the approximation ratios of dictionary compressors with respect to the smallest string attractor and allows us to uncover new asymptotic relations between the output sizes of different dictionary compressors. We then show that the k-attractor problem — deciding whether a text has a size-t set of positions capturing all substrings of length at most k — is NP-complete for k≥ 3. This, in particular, includes the full string attractor problem. We provide several approximation techniques for the smallest k-attractor, show that the problem is APX-complete for constant k, and give strong inapproximability results. To conclude, we provide matching lower and upper bounds for the random access problem on string attractors. The upper bound is proved by showing a data structure supporting queries in optimal time. Our data structure is universal: by our reductions to string attractors, it supports random access on any dictionary-compression scheme. In particular, it matches the lower bound also on LZ77, straight-line programs, collage systems, and macro schemes, and therefore essentially closes (at once) the random access problem for all these compressors.