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

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

1、ComputerEngineeringandApplications計算機工程與應用2010，46（21）129隨機模式匹配并行算法在工作站機群上的實現(xiàn)薛淞文，申衛(wèi)昌，剡公孝，喬龍XUESong-wen，SHENWei-chang，YANGong-xiao，QIAOLong西北大學信息科學與技術(shù)學院，西安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摘要：對隨機模式匹配算法進行了改進，并根據(jù)MPICH并行編程環(huán)境中任務間通信的特點，設計了一種基于MPICH的改進的隨機模式匹配并行算法。根據(jù)運行在COW（工作站機群）上的進程數(shù)目將文本串進行重疊劃分，每個進程完成一個文本子串的模式匹配。實驗結(jié)果表明，該改進的隨機模式匹配并行算法有效地加快了模式匹配的速度，提高了工作站機群的資源利用率。關鍵詞：模式匹配；消息傳遞編程標準的一種實現(xiàn)（MPICH）；并行算法；工作站機群DOI：10.3778/j.issn.1002-8331.2010.21.036文章編號：

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

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

8、用

9、Σ

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