基于后缀数组的分布式串匹配算法.doc

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