Lightweight Data Indexing and Compression in External Memory
Lightweight Data Indexing and Compression in External Memory
复制标题
DOI：
10.1007/s00453-011-9535-0
复制
发表时间：
2012-07-01
期刊：
影响因子：
1.1
通讯作者：
Manzini, Giovanni
中科院分区：
文献类型：
--
作者：
Ferragina, Paolo;Gagie, Travis;Manzini, Giovanni
在本文中，我们描述的算法计算的Burrows-Wheeler变换（BWT）和建设（压缩）索引在外部存储器中。我们的算法的创新特点是，他们是轻量级的意义上说，对于大小为n的输入，他们只使用n位的磁盘上的工作空间，而所有以前的方法使用我类似（nlog n）位。这是通过直接构建bwt而不通过构造后缀数组/树数据结构来实现的。此外，我们的算法只通过顺序扫描访问磁盘数据，因此它们充分利用了现代磁盘功能，使顺序磁盘访问比随机访问快得多。我们还提出了一个基于扫描的反相算法，使用类似于（n）位的工作空间，和一个轻量级的内存算法计算的bwt，这是最快的文献中可用的工作空间是o（n）位时的bwt。最后，我们证明了下界的复杂性计算和反转的BWT通过顺序扫描的经典产品：内部存储器空间x通过磁盘数据的数量，表明我们的算法是在一个O（log n）的最佳因素。
In this paper we describe algorithms for computing the Burrows-Wheeler Transform (bwt) and for building (compressed) indexes in external memory. The innovative feature of our algorithms is that they are lightweight in the sense that, for an input of size n, they use only n bits of working space on disk while all previous approaches use I similar to(nlog n) bits. This is achieved by building the bwt directly without passing through the construction of the Suffix Array/Tree data structure. Moreover, our algorithms access disk data only via sequential scans, thus they take full advantage of modern disk features that make sequential disk accesses much faster than random accesses. We also present a scan-based algorithm for inverting the bwt that uses I similar to(n) bits of working space, and a lightweight internal-memory algorithm for computing the bwt which is the fastest in the literature when the available working space is o(n) bits. Finally, we prove lower bounds on the complexity of computing and inverting the bwt via sequential scans in terms of the classic product: internal-memory space x number of passes over the disk data, showing that our algorithms are within an O(log n) factor of the optimal.