并行后缀树的构造及查询算法

作者：乔百友; 葛健; 王国仁; 韩东红后缀树并行构造字符串匹配生物序列生物信息学

摘要：针对生物信息领域中传统后缀树构造算法在时间和空间上的限制，从结构并行的角度提出了一种新颖的、适用于生物信息学应用的并行后缀树结构和相应的构造算法，该算法首先将给定字符串分成若干连续的片段，并在各个处理机上分别构造这些片段的后缀树，形成了一种分布于多个处理机上的并行后缀树结构，该并行算法不仅大大缩短了后缀树的构造时间，而且避免了主存大小的限制，经分析，其性能优于现有的任何一种并行算法，在此基础上，提出了二种高效的基于这种并行后缀树的字符串匹配算法，解决了传统后缀树的基本查询问题。

注：因版权方要求，不能公开全文，如需全文，请咨询杂志社