Succinct Suffix Arrays based on Run-Length Encoding
Succinct Suffix Arrays based on Run-Length Encoding
复制标题
基于游程编码的简洁后缀数组
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
G. Navarro
中科院分区：
文献类型：
--
作者：
V. Mäkinen;G. Navarro
succinet 全文自索引是一种建立在文本 T = t1t2...tn 上的数据结构，它占用的空间很小（理想情况下接近压缩文本的空间），允许有效搜索 T 中模式 P = p1p2...pm 的出现，并且能够重现任何文本子字符串，因此自索引取代了文本。近年来，已经开发了几种引人注目的自索引。其中许多占用的空间与 nH0 或 nHk 位成比例，其中 Hk 是 T 的 k 阶经验熵。计算 P 在 T 中出现次数的时间范围从 O(m) 到 O(m log n)。在本文中，我们提出了一种新的自索引，称为“游程长度 FM 索引”的 RLFM 索引，当字母表大小为 σ = O(polylog(n)) 时，它在 O(m) 时间内计算 P 在 T 中出现的次数。对于任何 k ≤ αlogσn 和常数 0 < α < 1，RLFM 索引需要 nHklogσ + O(n) 位空间。以前实现 O(m) 计数时间的索引要么需要超过 nH0 位的空间，要么要求 σ = O(1)。我们还证明了 RLFM 索引可以增强以定位文本中的出现并在与 σ 无关的时间中显示文本子串。此外，我们证明了文本的 k 阶熵与其后缀数组和 T 的 Burrows-Wheeler 变换中显示的一些规律之间存在密切关系。这种关系具有独立的意义，并且允许限制 RLFM 索引以及其他现有压缩索引的空间占用。提出一些实施 RLFM 指数的实际考虑因素。我们根据经验将我们的指数与现有的最佳实现进行比较，并表明它是实用的且具有竞争力。顺便说一句，我们获得了现有理论建议的竞争性实现，可以将其视为简化的 RLFM 索引，并探索其他实用想法，例如霍夫曼形小波树。
A succinet full-text self-index is a data structure built on a text T = t1t2...tn, which takes little space (ideally close to that of the compressed text), permits efficient search for the occurrences of a pattern P = p1p2...pm in T, and is able to reproduce any text substring, so the self-index replaces the text.Several remarkable self-indexes have been developed in recent years. Many of those take space proportional to nH0 or nHk bits, where Hk is the kth order empirical entropy of T. The time to count how many times does P occur in T ranges from O(m) to O(m log n).In this paper we present a new self-index, called RLFM index for "run-length FM-index", that counts the occurrences of P in T in O(m) time when the alphabet size is σ = O(polylog(n)). The RLFM index requires nHklogσ + O(n) bits of space, for any k ≤ αlogσn and constant 0 < α < 1. Previous indexes that achieve O(m) counting time either require more than nH0 bits of space or require that σ = O(1). We also show that the RLFM index can be enhanced to locate occurrences in the text and display text substrings in time independent of σ.In addition, we prove a close relationship between the kth order entropy of the text and some regularities that show up in their suffix arrays and in the Burrows-Wheeler transform of T. This relationship is of independent interest and permits bounding the space occupancy of the RLFM index, as well as that of other existing compressed indexes.Finally, we present some practical considerations in order to implement the RLFM index. We empirically compare our index against the best existing implementations and show that it is practical and competitive against those. In passing, we obtain a competitive implementation of an existing theoretical proposal that can be seen as a simplified RLFM index, and explore other practical ideas such as Huffman-shaped wavelet trees.