随机模式匹配并行算法在工作站机群上的实现

《随机模式匹配并行算法在工作站机群上的实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、ComputerEngineeringandApplications计算机工程与应用2010，46（21）129随机模式匹配并行算法在工作站机群上的实现薛淞文，申卫昌，剡公孝，乔龙XUESong-wen，SHENWei-chang，YANGong-xiao，QIAOLong西北大学信息科学与技术学院，西安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摘要：对随机模式匹配算法进行了改进，并根据MPICH并行编程环境中任务间通信的特点，设计了一种基于MPICH的改进的随机模式匹配并行算法。根据运行在COW（工作站机群）上的进程数目将文本串进行重叠划分，每个进程完成一个文本子串的模式匹配。实验结果表明，该改进的随机模式匹配并行算法有效地加快了模式匹配的速度，提高了工作站机群的资源利用率。关键词：模式匹配；消息传递编程标准的一种实现（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）技术的思想，它能域有着广泛的应用。在许多实际应用中，正文串的规模很大，利提供对数级的时间复杂度[1]。其基本思想是：运用散列方法和用快速的串行模式匹配算法也很耗时。因此，研究并设计快速素数理论，首先将模式串通过散列函数数值化，然后将文本串的

7、模式匹配并行算法具有重要的理论价值和实际意义。中每个长度为m的子串用相同的函数数值化。匹配过程不是直接比较模式串与文本子串本身，而是比较转化后的数值。1随机模式匹配算法简析显然只有那些与模式串具有相同数值的文本子串才有可能与1.1基本概念该模式串匹配，而没有必要考虑文本中所有长度为m的子串，经典的模式匹配（patternmatching）即字符串子串定位，从而大大提高了匹配算法的效率，但必须保证散列函数使两是一种重要的字符串运算。设模式串X和文本串Y中的字符个不同的串映射到同一整数上的概率非常小。来自有限字符集Σ，字符表大小为σ，

8、用

9、Σ

10、=σ表示。模式串X表为了使串的数值化结果能够体现出串的特征，串中的每示为X=x1x2xm，且xjÎΣ；文本串Y表示为Y=y1y2yn，yiÎ个字符都应该能影响到该串所对应的数值。记串s的数值化Σ，其中1≤j≤m，1≤i≤n，m≤n。并记