后缀树的并行构造算法

Parallel Construction of Suffix Trees

后缀树是一种非常重要的数据结构,它在与字符串处理相关的各种领域里有着非常广泛的应用。构造后缀树是应用后缀树解决问题的前提和关键。虽然很多现有的后缀树构造算法都是线性时间和空间的,但是,当被索引的字符串的长度很长时,构造其后缀树所消耗的时间和空间仍将非常巨大,这极大地限制了后缀树的实际应用。而并行技术是解决这一问题的很好途径,因此人们提出了后缀树的并行构造算法。本文对后缀树的三种并行构造算法进行了综述,通过系统的比较和分析,总结出当前存在的问题,并指明了下一步的研究方向。

The suffix tree is a very important data structure, which finds a wide variety of applications in many areas related to string processing. While using suffix trees, how to construct the suffix trees efficiently is the key problem. The serial suffix tree construction algorithms available now can run in linear time and space, however, when the string is too long, the time and space consumption is still unendurable, which greatly restricts the employability of suffix trees. While, parallelism seems to be a good way to solve the problem, so some researchers present parallel construction algorithms of suffix trees. In this paper, we survey three kinds of parallel construction algorithms of suffix trees and give them a detailed comparison. Also, we point out the remaining problems and research directions in this area.