隨機(jī)模式匹配并行算法在工作站機(jī)群上的實(shí)現(xiàn)

《隨機(jī)模式匹配并行算法在工作站機(jī)群上的實(shí)現(xiàn)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、ComputerEngineeringandApplications計(jì)算機(jī)工程與應(yīng)用2010，46（21）129隨機(jī)模式匹配并行算法在工作站機(jī)群上的實(shí)現(xiàn)薛淞文，申衛(wèi)昌，剡公孝，喬龍XUESong-wen，SHENWei-chang，YANGong-xiao，QIAOLong西北大學(xué)信息科學(xué)與技術(shù)學(xué)院，西安710127SchoolofInformationScienceandTechnology，NorthwestUniversity，Xi’an710127，ChinaE-mail：xue_song_wen@163.comXUESo

2、ng-wen，SHENWei-chang，YANGong-xiao，etal.Implementationofparallelalgorithmsforrandomizedpatternmatchingonclusterofworkstations.ComputerEngineeringandApplications，2010，46（21）：129-131.Abstract：Anewlyimprovedpatternmatchingalgorithmisdesignedbyanalyzingrandomizedalgorithmf

3、orpatternmatch-ingandaneffectiveparallelalgorithmforpatternmatchingbasedonMPICHisdesignedaccordingtothefeaturesoftaskcommunicationonMPICHparallelprogrammingenvironment.Textstringisdividedintooverlappedsub-stringaccordingtothequantityofprocessinCOW（ClusterofWorkstation

4、s），andeachprocessexecutespatternmatchingparallelly.Theexperi-mentalresultsshowthatthepatternmatchingspeedisacceleratedandtheutilizationofresourcesinCOWisalsoimproved.Keywords：patternmatching；animplementationoftheMessagePassingInterface（MPICH）；parallelalgorithm；cluster

5、ofworkstations摘要：對(duì)隨機(jī)模式匹配算法進(jìn)行了改進(jìn)，并根據(jù)MPICH并行編程環(huán)境中任務(wù)間通信的特點(diǎn)，設(shè)計(jì)了一種基于MPICH的改進(jìn)的隨機(jī)模式匹配并行算法。根據(jù)運(yùn)行在COW（工作站機(jī)群）上的進(jìn)程數(shù)目將文本串進(jìn)行重疊劃分，每個(gè)進(jìn)程完成一個(gè)文本子串的模式匹配。實(shí)驗(yàn)結(jié)果表明，該改進(jìn)的隨機(jī)模式匹配并行算法有效地加快了模式匹配的速度，提高了工作站機(jī)群的資源利用率。關(guān)鍵詞：模式匹配；消息傳遞編程標(biāo)準(zhǔn)的一種實(shí)現(xiàn)（MPICH）；并行算法；工作站機(jī)群DOI：10.3778/j.issn.1002-8331.2010.21.036文章編號(hào)：

6、1002-8331（2010）21-0129-03文獻(xiàn)標(biāo)識(shí)碼：Ａ中圖分類號(hào)：TP311.1模式匹配是計(jì)算機(jī)科學(xué)中研究得最廣泛的問題之一，它在度為m的n-m+1個(gè)子串分別與模式串X逐個(gè)字符進(jìn)行比較，而入侵檢測、圖像處理、文獻(xiàn)檢索、信息檢索以及分子生物學(xué)等領(lǐng)隨機(jī)模式匹配算法主要采用了散列（Hash）技術(shù)的思想，它能域有著廣泛的應(yīng)用。在許多實(shí)際應(yīng)用中，正文串的規(guī)模很大，利提供對(duì)數(shù)級(jí)的時(shí)間復(fù)雜度[1]。其基本思想是：運(yùn)用散列方法和用快速的串行模式匹配算法也很耗時(shí)。因此，研究并設(shè)計(jì)快速素?cái)?shù)理論，首先將模式串通過散列函數(shù)數(shù)值化，然后將文本串的

7、模式匹配并行算法具有重要的理論價(jià)值和實(shí)際意義。中每個(gè)長度為m的子串用相同的函數(shù)數(shù)值化。匹配過程不是直接比較模式串與文本子串本身，而是比較轉(zhuǎn)化后的數(shù)值。1隨機(jī)模式匹配算法簡析顯然只有那些與模式串具有相同數(shù)值的文本子串才有可能與1.1基本概念該模式串匹配，而沒有必要考慮文本中所有長度為m的子串，經(jīng)典的模式匹配（patternmatching）即字符串子串定位，從而大大提高了匹配算法的效率，但必須保證散列函數(shù)使兩是一種重要的字符串運(yùn)算。設(shè)模式串X和文本串Y中的字符個(gè)不同的串映射到同一整數(shù)上的概率非常小。來自有限字符集Σ，字符表大小為σ，

8、用

9、Σ

10、=σ表示。模式串X表為了使串的數(shù)值化結(jié)果能夠體現(xiàn)出串的特征，串中的每示為X=x1x2xm，且xj?Σ；文本串Y表示為Y=y1y2yn，yi?個(gè)字符都應(yīng)該能影響到該串所對(duì)應(yīng)的數(shù)值。記串s的數(shù)值化Σ，其中1≤j≤m，1≤i≤n，m≤n。并記