基于后綴數組的分布式串匹配算法

　　摘要：文章提出的UniformedSoffixArraysAss誼n算法通過(guò)采取均勻的后級分配方式，使各個(gè)處理器可以獨立地構造后綴數組，并提出通過(guò)播送最長(cháng)后綴長(cháng)度(Maxsuffixlen)來(lái)降低處理段間匹配時(shí)的通信復雜度。算法在構造后級數組時(shí)的平均復雜度為O((N/P)(109109(N/P)))，通信復雜度為0(1)。通過(guò)實(shí)驗分析得出，在(N/P)M的情況下，USAA算法可以在保持計算復雜度的同時(shí)大大降低在構造后綴數組過(guò)程中的通信消耗。其中N，M分別為文本串和模式申的長(cháng)度，P為處理器數。

　　關(guān)鍵詞：后綴數組分布式存儲串匹配

　　1、引言

　　鍵，在分布式環(huán)境下加速后綴數組的構造需要充分考慮到通信對算法性能的影響。串匹配問(wèn)題是計算機科學(xué)中研究得最廣泛的問(wèn)題之一，在文字編輯與處理、圖像處理、信息檢索、分子生物學(xué)等領(lǐng)域都有很廣泛的應用。本文解決的是分布式存儲環(huán)境下的精確串匹配問(wèn)題。在串匹配的許多實(shí)際應用中一個(gè)確定的文本常常被查詢(xún)很多次(比如對非常長(cháng)的基因序列的查詢(xún))。針對這種情況，Manber.U和E.W.Myers提出建立后綴數組(suffixarrays)〔1〕來(lái)提高查詢(xún)的性能，而后綴數組最大的不足是它的構造時(shí)間過(guò)長(cháng)。因此一直以來(lái)，如何快速有效地構造后綴數組成了提高基于后綴數組的串匹配算法性能的關(guān)

　　2、USAA算法

　　假設N，M為文本串和模式串的長(cháng)度，P為處理器數，算法設計思路如下:

　　(1)將長(cháng)為N的文本串A均勻劃分成互不重盛的P段，分布于處理器。~(P一l)中，且使相鄰的文本段分布在相鄰的處理器中，顯然每個(gè)處理器中局部文本段的長(cháng)度為〔N/P〕。

　　(2)除了處理器O外，其它每個(gè)處理器利用KMP算法計算分配到自己的文本串的頭個(gè)字符與模式串，基金項目:國家自然科學(xué)基金重點(diǎn)項目(60533020) 的匹配信息。如果存在匹配情況，就向相鄰的前一個(gè)處理器發(fā)送最大匹配后綴長(cháng)度Maxsuffixlen，否則就發(fā)送一個(gè)負數。每個(gè)處理器可獨立地計算和發(fā)送該值，所以這一步的計算復雜度為O(M)，通信復雜度為O(1)。

　　(3)處理器1~(P-l)接收前一個(gè)處理器的信息。

　　(4)利用Manber.U和E.W.Myers在文獻〔〔1〕中的算法各處理器并行地構造局部文本段的后綴數組。

　　(5)利用Manber.U和E.W.Myers在文獻〔1〕中的算法各處理器并行地進(jìn)行模式申的匹配。算法的計算復雜度為O((N/P(109109(N/P)))，通信復雜度為0(1)，大大降低了通信復雜度。

　　3、實(shí)驗結果及分析

　　我們在基于分布存儲的32節點(diǎn)HPRX2600高性能機群系統上測試了上述算法，比較了USAA和目前理論值最好的MMsortlz〕算法之間的性能，其計算復雜度為，通信復雜度為。

　　圖1給出了當M一16、P~2時(shí)，N的取值對算法執行時(shí)間的影響。從圖中看出當時(shí)，由于N、P的取值成了影響算法復雜度的主項，因此在實(shí)際應用中USAA算法比MMsort算法表現要好。

　　圖2給出了當N變大時(shí)，USAA算法和MMsort算法的通信時(shí)間比較�？梢钥闯�，隨著(zhù)文本串的規模變大，由于處理器間需要進(jìn)行的通信量增加，MMsort算法的通信時(shí)間有明顯的上升，而USAA算法的上升幅度要顯著(zhù)小于MMsort。

　　4、結論

　　本文提出的USAA算法通過(guò)采取均勻的后綴分配方式來(lái)降低處理段間匹配時(shí)的通信消耗，在(N/P)M的情況下使算法在保持計算復雜度的同時(shí)大大降低了通信復雜度。通過(guò)實(shí)驗結果可以看到，USAA算法很好地解決了在分布式存儲環(huán)境下降低后級數組構造中的通信復雜度的問(wèn)題。

　　參考文獻

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

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

　　[2]Kitajima，J.P.，Navarro，G.Afastdistributedsuffix arraygenerationalgorithm〔C」.StringProeessingand InformationRetrievalSymposium，1999SePt，1999:22-24，97一104.

【基于后綴數組的分布式串匹配算法】相關(guān)文章：

動(dòng)背景下基于模板匹配的快速跟蹤算法03-07

一種基于蟻群優(yōu)化的分布式動(dòng)態(tài)路由算法03-07

基于分布式算法和FPGA實(shí)現基帶信號成形的研究03-18

基于虛擬現實(shí)技術(shù)的分布式船舶運動(dòng)控制算法測試系統03-07

基于FPGA流水線(xiàn)分布式算法的FIR濾波器的實(shí)現03-18

入侵檢測模式匹配算法的研究與改進(jìn)03-29

用于無(wú)線(xiàn)傳感器網(wǎng)絡(luò )的基于自適應信號處理的分布式編碼算法03-07

基于DSP的信道譯碼算法優(yōu)化03-19

基于階梯細化的圖像放大算法03-07