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

来源期刊：东北大学学报(自然科学版)2004年第3期

论文作者：乔百友 葛健 王国仁 韩东红

文章页码：231 - 234

关键词：后缀树;并行构造;字符串匹配;生物序列;生物信息学;

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