基于后綴數(shù)組的分布式串匹配算法

基于后綴數(shù)組的分布式串匹配算法

摘要：文章提出的UniformedSoffixArraysAss誼n算法通過(guò)采取均勻的后級(jí)分配方式，使各個(gè)處理器可以獨(dú)立地構(gòu)造后綴數(shù)組，并提出通過(guò)播送最長(zhǎng)后綴長(zhǎng)度(Maxsuffixlen)來(lái)降低處理段間匹配時(shí)的通信復(fù)雜度。算法在構(gòu)造后級(jí)數(shù)組時(shí)的平均復(fù)雜度為O((N/P)(109109(N/P)))，通信復(fù)雜度為0(1)。通過(guò)實(shí)驗(yàn)分析得出，在(N/P)M的情況下，USAA算法可以在保持計(jì)算復(fù)雜度的同時(shí)大大降低在構(gòu)造后綴數(shù)組過(guò)程中的通信消耗。其中N，M分別為文本串和模式申的長(zhǎng)度，P為處理器數(shù)。關(guān)鍵詞：后綴數(shù)組分布式存儲(chǔ)串匹配1引言鍵，在分布式環(huán)境下加速后綴數(shù)組的構(gòu)造需要充分考慮到通信對(duì)算法性能的影響。串匹配問(wèn)題是計(jì)算機(jī)科學(xué)中研究得最廣泛的問(wèn)題之一，在文字編輯與處理、圖像處理、信息檢索、分子生物學(xué)等領(lǐng)域都有很廣泛的應(yīng)用。本文解決的是分布式存儲(chǔ)環(huán)境下的精確串匹配問(wèn)題。在串匹配的許多實(shí)際應(yīng)用中一個(gè)確定的文本常常被查詢(xún)很多次(比如對(duì)非常長(zhǎng)的基因序列的查詢(xún))。針對(duì)這種情況，Manber.U和E.W.Myers提出建立后綴數(shù)組(suffixarrays)〔1〕來(lái)提高查詢(xún)的性能，而后綴數(shù)組最大的不足是它的構(gòu)造時(shí)間過(guò)長(zhǎng)。因此一直以來(lái)，如何快速有效地構(gòu)造后綴數(shù)組成了提高基于后綴數(shù)組的串匹配算法性能的關(guān)2USAA算法假設(shè)N，M為文本串和模式串的長(zhǎng)度，P為處理器數(shù)，算法設(shè)計(jì)思路如下:(1)將長(zhǎng)為N的文本串A均勻劃分成互不重盛的P段，分布于處理器。~(P一l)中，且使相鄰的文本段分布在相鄰的處理器中，顯然每個(gè)處理器中局部文本段的長(zhǎng)度為〔N/P〕。(2)除了處理器O外，其它每個(gè)處理器利用KMP算法計(jì)算分配到自己的文本串的頭個(gè)字符與模式串，基金項(xiàng)目:國(guó)家自然科學(xué)基金重點(diǎn)項(xiàng)目(60533020)的匹配信息。如果存在匹配情況，就向相鄰的前一個(gè)處理器發(fā)送最大匹配后綴長(zhǎng)度Maxsuffixlen，否則就發(fā)送一個(gè)負(fù)數(shù)。每個(gè)處理器可獨(dú)立地計(jì)算和發(fā)送該值，所以這一步的計(jì)算復(fù)雜度為O(M)，通信復(fù)雜度為O(1)。(3)處理器1~(P-l)接收前一個(gè)處理器的信息。(4)利用Manber.U和E.W.Myers在文獻(xiàn)〔〔1〕中的算法各處理器并行地構(gòu)造局部文本段的后綴數(shù)組。(5)利用Manber.U和E.W.Myers在文獻(xiàn)〔1〕中的算法各處理器并行地進(jìn)行模式申的匹配。算法的計(jì)算復(fù)雜度為O((N/P(109109(N/P)))，通信復(fù)雜度為0(1)，大大降低了通信復(fù)雜度。3實(shí)驗(yàn)結(jié)果及分析我們?cè)诨诜植即鎯?chǔ)的32節(jié)點(diǎn)HPRX2600高性能機(jī)群系統(tǒng)上測(cè)試了上述算法，比較了USAA和目前理論值最好的MMsortlz〕算法之間的性能，其計(jì)算復(fù)雜度為，通信復(fù)雜度為。圖1給出了當(dāng)M一16、P~2時(shí)，N的取值對(duì)算法執(zhí)行時(shí)間的影響。從圖中看出當(dāng)時(shí)，由于N、P的取值成了影響算法復(fù)雜度的主項(xiàng)，因此在實(shí)際應(yīng)用中USAA算法比MMsort算法表現(xiàn)要好。圖2給出了當(dāng)N變大時(shí)，USAA算法和MMsort算法的通信時(shí)間比較。可以看出，隨著文本串的規(guī)模變大，由于處理器間需要進(jìn)行的通信量增加，MMsort算法的通信時(shí)間有明顯的上升，而USAA算法的上升幅度要顯著小于MMsort。4結(jié)論本文提出的USAA算法通過(guò)采取均勻的后綴分配方式來(lái)降低處理段間匹配時(shí)的通信消耗，在(N/P)M的情況下使算