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