1基于后缀数组的分布式串匹配算法摘要：文章提出的 UniformedSoffixArraysAss 谊 n 算法通过采取均匀的后级分配方式，使各个处理器可以独立地构造后缀数组，并提出通过播送最长后缀长度(Maxsuffixlen)来降低处理段间匹配时的通信复杂度。算法在构造后级数组时的平均复杂度为 O(N/P)(109109(N/P)，通信复杂度为 0(1)。通过实验分析得出，在(N/P)M 的情况下，USAA 算法可以在保持计算复杂度的同时大大降低在构造后缀数组过程中的通信消耗。其中 N，M 分别为文本串和模式申的长度，P 为处理器数。关键词：后缀数组分布式存储串匹配 1 引言 键，在分布式环境下加速后缀数组的构造需要充分考虑到通信对算法性能的影响。串匹配问题是计算机科学中研究得最广泛的问题之一，在文字编辑与处理、图像处理、信息检索、分子生物学等领域都有很广泛的应用。本文解决的是分布式存储环境下的精确串匹配问题。在串匹配的许多实际应用中一个确定的文本常常被查询很多次(比如对非常长的基因序列的查询)。针对这种情况，Manber.U 和E.W.Myers 提出建立后缀数组(suffixarrays)1来提高查询的性能，而后缀数组最大的不足是它的构造时间过长。因此一直以来，如何快速有效地构造后缀数组成了提高基于后缀数组的串匹配算法性能的关 2USAA 算法 假设 N，M 为文本串和模式串的长度，P 为处理器数，算法设计思路如下: (1)将长为 N 的文本串 A 均匀划分成互不重盛的 P 段，分布于处理器。(P 一 l)中，且使相邻的文本段分布在相邻的处理器中，显然每个处理器中局部文本段的长度为N/P。 2(2)除了处理器 O 外，其它每个处理器利用 KMP 算法计算分配到自己的文本串的头个字符与模式串，基金项目:国家自然科学基金重点项目(60533020) 的匹配信息。如果存在匹配情况，就向相邻的前一个处理器发送最大匹配后缀长度Maxsuffixlen，否则就发送一个负数。每个处理器可独立地计算和发送该值，所以这一步的计算复杂度为 O(M)，通信复杂度为 O(1)。 (3)处理器 1(P-l)接收前一个处理器的信息。 (4)利用 Manber.U 和 E.W.Myers 在文献1中的算法各处理器并行地构造局部文本段的后缀数组。 (5)利用 Manber.U 和 E.W.Myers 在文献1中的算法各处理器并行地进行模式申的匹配。算法的计算复杂度为 O(N/P(109109(N/P)，通信复杂度为 0(1)，大大降低了通信复杂度。 3 实验结果及分析 我们在基于分布存储的 32 节点 HPRX2600 高性能机群系统上测试了上述算法，比较了 USAA 和目前理论值最好的 MMsortlz算法之间的性能，其计算复杂度为，通信复杂度为。 图 1 给出了当 M 一 16、P2 时，N 的取值对算法执行时间的影响。从图中看出当时，由于 N、P 的取值成了影响算法复杂度的主项，因此在实际应用中 USAA 算法比 MMsort 算法表现要好。 图 2 给出了当 N 变大时，USAA 算法和 MMsort 算法的通信时间比较。可以看出，随着文本串的规模变大，由于处理器间需要进行的通信量增加，MMsort 算法的通信时间有明显的上升，而 USAA 算法的上升幅度要显著小于 MMsort。 4 结论 本文提出的 USAA 算法通过采取均匀的后缀分配方式来降低处理段间匹配时的3通信消耗，在(N/P)M 的情况下使算法在保持计算复杂度的同时大大降低了通信复杂度。通过实验结果可以看到，USAA 算法很好地解决了在分布式存储环境下降低后级数组构造中的通信复杂度的问题。 参考文献 1U.Manber，G.Myers.Suffixarrays:Anewmethodforon-linestringsearehesC. InProeeedingsofthe lstAnnualACM 一 SIAMSymPosiumon 压 sereteAlgorithms.1990:319 一 327. 2Kitajima，J.P.，Navarro，G.Afastdistributedsuffix arraygenerationalgorithmC. StringProeessingand InformationRetrievalSymposium，1999SePt，1999:22-24，97 一 104.