Practical Rank/Select Queries over Arbitrary Sequences
Practical Rank/Select Queries over Arbitrary Sequences
复制标题
对任意序列的实用排序/选择查询
DOI：
10.1007/978-3-540-89097-3_18
复制
发表时间：
2008
影响因子：
0.5
通讯作者：
G. Navarro
中科院分区：
文献类型：
--
作者：
Francisco Claude;G. Navarro
我们提出了一个实用的研究支持排名，选择和访问查询的序列的紧凑表示。虽然有几个理论解决方案的问题，只有少数已经尝试过，并有很少的想法，如何其他将执行，特别是在序列的情况下，非常大的字母。我们首先提出了一个新的实际实现的压缩表示位序列提出的拉曼，拉曼，饶[SODA 2002]，这是竞争与现有的序列时，不是太可压缩。它也有很好的局部压缩特性，我们表明，这使得它成为一个很好的工具，结合Burrows-Wheeler变换压缩文本索引。这表明了最近的理论建议的实用性[Makinen和Navarro，SPIRE 2007]，实现了以前从未见过的空间。其次，对于一般序列，我们调整小波树的情况下，非常大的字母表，通过删除它们的指针信息。我们表明，这给出了一个很好的解决方案，表示零阶熵空间内的序列，在大字母表的情况下，典型的编码方法构成了严重的挑战。我们还提出了Golynski等人的第一个实现。的表示[SODA 2006]，它提供了另一个有趣的时间/空间权衡。
We present a practical study on the compact representation of sequences supporting rank , select , and access queries. While there are several theoretical solutions to the problem, only a few have been tried out, and there is little idea on how the others would perform, especially in the case of sequences with very large alphabets. We first present a new practical implementation of the compressed representation for bit sequences proposed by Raman, Raman, and Rao [SODA 2002], that is competitive with the existing ones when the sequences are not too compressible. It also has nice local compression properties, and we show that this makes it an excellent tool for compressed text indexing in combination with the Burrows-Wheeler transform. This shows the practicality of a recent theoretical proposal [Makinen and Navarro, SPIRE 2007], achieving spaces never seen before. Second, for general sequences, we tune wavelet trees for the case of very large alphabets, by removing their pointer information. We show that this gives an excellent solution for representing a sequence within zero-order entropy space, in cases where the large alphabet poses a serious challenge to typical encoding methods. We also present the first implementation of Golynski et al.'s representation [SODA 2006], which offers another interesting time/space trade-off.