Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies
Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies
复制标题
后缀树拓扑简洁表示的空间高效并行构建
DOI：
10.1145/3035540
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
E. Ohlebusch
中科院分区：
文献类型：
--
作者：
U. Baier;T. Beller;E. Ohlebusch
压缩后缀树通常由三个部分组成：压缩后缀数组、压缩LCP数组和后缀树拓扑的简洁表示。有并行算法构造后缀数组和LCP数组，但没有第三个组件。在这篇文章中，我们提出了并行算法的共享内存架构，构建的平衡括号序列（BPS），一个明确的简洁表示的后缀树拓扑结构，以及增强的平衡括号表示（eBPR），一个隐含的简洁表示的后缀树拓扑结构。对于这两种表示，本文提出了一个顺序的建设算法（一个新的BPS），线性的工作和O（logn）时间的并行建设算法，和启发式并行建设算法，在实践中工作得很好。实验结果表明，我们的方法是非常适合现实世界的应用。
A compressed suffix tree usually consists of three components: a compressed suffix array, a compressed LCP-array, and a succinct representation of the suffix tree topology. There are parallel algorithms that construct the suffix array and the LCP-array, but none for the third component. In this article, we present parallel algorithms on shared memory architectures that construct the balanced parentheses sequence (BPS), an explicit succinct representation of the suffix tree topology, as well as the enhanced balanced parentheses representation (eBPR), an implicit succinct representation of the suffix tree topology. For both representations, this article presents a sequential construction algorithm (a new one for the BPS), a linear work andO(logn) time parallel construction algorithm, and a heuristic parallel construction algorithm that works very well in practice. The experimental results show that our methods are well suited for real-world applications.
登录
查看更多内容
使用 O(sort(n))（或更少）I/O 构建 LCP 数组
影响因子：
0.5
作者：
Juha Kärkkäinen;Dominik Kempa
通讯作者：
Dominik Kempa
影响因子：
5.8
作者：
Baier, Uwe;Beller, Timo;Ohlebusch, Enno
通讯作者：
Ohlebusch, Enno
GPU 的并行后缀数组和最不常见前缀
DOI：
--
发表时间：
2013
期刊：
ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming
影响因子：
--
作者：
Mrinal Deo;S. Keely
通讯作者：
S. Keely
一种支持快速字符串匹配的压缩增强后缀数组
DOI：
10.1007/978-3-642-03784-9_6
发表时间：
2009
期刊：
Sigplan Notices
影响因子：
--
作者：
Enno Ohlebusch;Simon Gog
通讯作者：
Simon Gog
范围最小查询的最佳简洁性
DOI：
10.1007/978-3-642-12200-2_16
发表时间：
2008
期刊：
J. Discrete Algorithms
影响因子：
--
作者：
J. Fischer
通讯作者：
J. Fischer