期刊
THEORETICAL COMPUTER SCIENCE
卷 387, 期 3, 页码 249-257出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2007.07.018
关键词
Burrows-Wheeler transform; suffix sorting; suffix array; space-efficient algorithms
We present a new space- and time-efficient algorithm for computing the Burrow-Wheeler transform (BWT). For any choice of a parameter upsilon E [3, n(2/3)], the computation of BWT for a text of length n takes O(n log n + vn) worst-case time and O(n log n + root upsilon n) average-case time using O(n log n/root upsilon) bits of space in addition to the text and the BWT. For example, if upsilon = log(2) n, the time is O(n log2 n) in the worst case and O(n log n) on an average with the additional space requirement of O(n) bits. The algorithm is alphabet-independent: it uses only character comparisons, and the complexities do not depend on the alphabet size unless upsilon does. A practical implementation is 2-3 times slower than one of the fastest and most space-efficient previous algorithms while needing only one-third of the main memory. The algorithm is based on suffix arrays, but unlike any other algorithm, it can construct the suffix array a small block at a time without storing the rest of the suffix array anywhere. (c) 2007 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据