Constructing Compressed Suffix Arrays with Large Alphabets
Constructing Compressed Suffix Arrays with Large Alphabets
复制标题
DOI：
10.1007/978-3-540-24587-2_26
复制
发表时间：
2003-12
期刊：
影响因子：
--
通讯作者：
W. Hon;T. Lam;K. Sadakane;W. Sung
中科院分区：
文献类型：
--
作者：
W. Hon;T. Lam;K. Sadakane;W. Sung
最近对压缩后缀数组的研究已经产生了两种突破性的索引数据结构，即压缩后缀数组（CSA）[7]和FM索引[5]。它们中的任何一种都可以在主存中存储全文索引，即使是具有几十亿字符的文本数据（如人类DNA）。然而，用有限的工作存储器（即，而不构造后缀数组）并不是一个简单的任务。本文针对这一问题。目前，只有CSA承认空间有效的构造算法[15]。对于一个长度超过一个字母表的文本T，该算法需要O（|Σ| nlogn）时间和（2 H 0 + 1+ε）nbits的工作空间，其中H 0是T的0阶经验熵，ε是任意非零常数。这个算法是足够好的，当字母表的大小| Σ|很小。本文的主要贡献是提出了一个新的算法，它可以在O（nlogn）时间内用（H_0 + 2+ε）nbits的工作空间构造CSA。请注意，我们的算法的运行时间与字母表大小无关，并且空间需求较小，因为很可能H 0> 1。本文还对FM索引的空间有效构造做出了贡献。我们证明了FM-指数确实可以直接从CSA构造在O（n）时间。
Recent research in compressing suffix arrays has resulted in two breakthrough indexing data structures, namely, compressed suffix arrays (CSA) [7] and FM-index [5]. Either of them makes it feasible to store a full-text index in the main memory even for a piece of text data with a few billion characters (such as human DNA). However, constructing such indexing data structures with limited working memory (i.e., without constructing suffix arrays) is not a trivial task. This paper addresses this problem. Currently, only CSA admits a space-efficient construction algorithm [15]. For a textTof lengthnover an alphabet Σ, this algorithm requiresO(|Σ|nlogn) time and (2H0+ 1+ε)nbits of working space, whereH0is the 0-th order empirical entropy ofTandεis any non-zero constant. This algorithm is good enough when the alphabet size | Σ| is small. It is not practical for text data containing protein, Chinese or Japanese, where the alphabet may include up to a few thousand characters.The main contribution of this paper is a new algorithm which can construct CSA inO(nlogn) time using (H0+ 2+ε)nbits of working space. Note that the running time of our algorithm is independent of the alphabet size and the space requirement is smaller as it is likely thatH0> 1. This paper also makes contribution to the space-efficient construction of FM-index. We show that FM-index can indeed be constructed from CSA directly inO(n) time.