Indexing compressed text
Indexing compressed text
复制标题
DOI：
10.1145/1082036.1082039
复制
发表时间：
2005-07-01
影响因子：
2.5
通讯作者：
Manzini, G
中科院分区：
文献类型：
--
作者：
Ferragina, P;Manzini, G
我们设计了两种压缩数据结构来解决全文索引问题，它们支持高效的子串搜索，使用的空间大致相当于以压缩形式存储文本所需的空间。我们的第一种压缩数据结构在0（p + occ log（1+ n）n）时间内检索文本T [1，n]中模式P [ 1，p]的occ出现次数，对于任何选择的n <0 < E < 1。该数据结构使用至多5 nH（k）（T）+ o（n）位的存储，其中H-k（T）是T的k阶经验熵。在最坏的情况下，空间使用是6（n）位，对于可压缩文本，空间使用是O（n）位。这种数据结构利用了后缀数组和Burrows-Wheeler变换之间的关系，可以看作是一种压缩的后缀数组，对于任意的E，我们的第二种压缩数据结构使用O（nH（k）（T）log（k）n）+ o（n）位的存储空间实现了O（p + occ）的查询时间，0 < E < 1。因此，它在最坏的情况下使用O（n log n）位提供了最佳的输出敏感查询时间。第二种数据结构建立在第一种数据结构的基础上，并利用了两种压缩器之间的相互作用：Burrows-Wheeler变换和LZ 78算法。
We design two compressed data structures for the full-text indexing problem that support efficient substring searches using roughly the space required for storing the text in compressed form.Our first compressed data structure retrieves the occ occurrences of a pattern P [ 1, p] within a text T [1, n] in 0 (p + occ log(1+epsilon) n) time for any chosen epsilon 0 < E < 1. This data structure uses at most 5nH(k)(T) + o(n) bits of storage, where H-k(T) is the kth order empirical entropy of T. The space usage is 6(n) bits in the worst case and o(n) bits for compressible texts. This data structure exploits the relationship between suffix arrays and the Burrows-Wheeler Transform, and can be regarded as a compressed suffix array.Our second compressed data structure achieves O(p + occ) query time using O(nH(k)(T) log(epsilon) n) + o(n) bits of storage for any chosen E, 0 < E < 1. Therefore, it provides optimal output-sensitive query time using o(n log n) bits in the worst case. This second data structure builds upon the first one and exploits the interplay between two compressors: the Burrows-Wheeler Transform and the LZ78 algorithm.