论基于后缀数组匹配算法

摘要：文章提出的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)除了处理器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、P~2时，N的取值对算法执行时间的影响。从图中看出当时，由于N、P的取值成了影响算法复杂度的主项，因此在实际应用中USAA算法比MMsort算法表现要好。

图2给出了当N变大时，USAA算法和MMsort算法的通信时间比较。可以看出，随着文本串的规模变大，由于处理器间需要进行的通信量增加，MMsort算法的通信时间有明显的上升，而USAA算法的上升幅度要显著小于MMsort。

4结论

本文提出的USAA算法通过采取均匀的后缀分配方式来降低处理段间匹配时的通信消耗，在(N/P)M的情况下使算法在保持计算复杂度的同时大大降低了通信复杂度。通过实验结果可以看到，USAA算法很好地解决了在分布式存储环境下降低后级数组构造中的通信复杂度的问题。

参考文献

[1]U.Manber，G.Myers.Suffixarrays:Anewmethodforon-linestringsearehes[C〕.InProeeedingsofthe

lstAnnualACM一SIAMSymPosiumon压sereteAlgorithms.1990:319一327.

[2]Kitajima，J.P.，Navarro，G.Afastdistributedsuffixarraygenerationalgorithm〔C」.StringProeessingandInformationRetrievalSymposium，1999SePt，1999:22-24，97一104.