Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
复制标题
在确定性线性时间内节省空间地构建压缩索引
DOI：
10.1137/1.9781611974782.26
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Yakov Nekrich
中科院分区：
文献类型：
--
作者：
J. Munro;G. Navarro;Yakov Nekrich
我们证明了一个字符串$T$的压缩后缀数组和压缩后缀树可以在$O（n）$确定性时间内使用$O（n\log\sigma）$位空间构建，其中$n$是字符串长度，$\sigma$是字母表大小。前面描述的确定性算法要么运行时间取决于字母表的大小，要么需要$\omega（n\log \sigma）$位的工作空间。我们的结果有直接应用到其他问题，如产生第一个线性时间LZ 77和LZ 78解析算法，使用$O（n \log\sigma）$位。
We show that the compressed suffix array and the compressed suffix tree of a string $T$ can be built in $O(n)$ deterministic time using $O(n\log\sigma)$ bits of space, where $n$ is the string length and $\sigma$ is the alphabet size. Previously described deterministic algorithms either run in time that depends on the alphabet size or need $\omega(n\log \sigma)$ bits of working space. Our result has immediate applications to other problems, such as yielding the first linear-time LZ77 and LZ78 parsing algorithms that use $O(n \log\sigma)$ bits.
影响因子：
2.5
作者：
MCCREIGHT, EM
通讯作者：
MCCREIGHT, EM
影响因子：
1.3
作者：
Navarro, Gonzalo;Sadakane, Kunihiko
通讯作者：
Sadakane, Kunihiko