串匹配与序列查找并行算法分析

《串匹配与序列查找并行算法分析》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中国科学技术人学博十学位论文串匹配与序列南找并行算法研究摘要串匹配是计算机科学中一个基本、重要的研究问题，它在Internet网络信，E-搜索、生物信息学、网络入侵检测、网络远程教育、电子商务等领域具有广泛的应用。本文围绕精确串匹配、多模式串匹配、近似串匹配、近似词典匹配和扩展的最长公共子序列问题开展研究，主要内容、贡献和创新包括：(1)基于孙子定理和Karp-Rabin模式匹配思想的确定性串匹配算法及其并行化利用著名的孙子定理将长度为m的模式和正丈子串分别映射成惟一的一对整数值，基于Karp—Rabin模式匹配思想，设计一个最坏时间复杂

2、度仍维持为00+棚)的精确串匹配算法，该算法既保持Karp-Rabin串匹配随机算法直观、简明和高效的优点，又使得模式匹配结果是确定的而不只是高概率的。我们也讨论了基于分割模式的长模式串匹配顺序和并行处理，并且将基于孙子定理和Karp．Rabin模式匹配思想设计的串匹配算法在超立方机器上并行化。(2)基于映射和Hashing的多模式串匹配及其并行算法基于映射和Hashing方法研究多模式串匹配，在CREWPRAM模型上设计一个线性加速且正丈匹配检查时间与模式个数无关的多模式串匹配并行算法。利用可重构光计算模型ORM的完全路由和动态重构网络

3、拓扑结构的技术，给出一个基于ORM模型的常数时间的多模式串匹配并行算法．我们提出的基于映射和Hashing的多模式串匹配方法比基于有限自动机理论和后缀树的多模式串匹配方法简明、直观和易于并行化．(3)PRAM模型上代价最优的允许“差别的近似串匹配并行算法和LARPBS模型上常数时间的允许七．误配的近似串匹配并行算法采取波前式并行推进以及水平和斜向双并行直接计算编辑距离矩阵D的方法，在CREWPRAM模型上，设计两个在线的代价最优、线性加速的允许缸差别的近似串匹配动态规划并行算法．通过灵活拆分总线和合并子总线的方法动态重构光总线系统，并巧妙

4、利用光总线的消息播送技术以及并行计算前缀和方法，设计了据我们所知是LARPBS模型上第一个常数时间复杂度的允许“误配的近似串匹配并行算法。(4)允许“差别的可变长模式串近似词典匹配及其在PRAM和BSR模型上的并行处理以往的文献主要考虑汉明距离等于1的允许如误配的近似词典匹配顺序算法，本文则研究更一般的允许七-差别的可变长模式串近似词典匹配问题．基于CREWPRAM模型，在设计Multisets排序最优并行算法的基础上，提出一个允许“差别的可变长模式串近似词典匹配并行算法，该算法在预处理词典和查询匹茎生竖坚燮丛生望翌±堂焦堕塞皇垦里兰壁型

5、变丛垫堑茎鲨塑壅配阶段分剐获得线性和对数以上的加速。我们在BSR模型上也设计一个允许“差别的可变长模式串近似词典匹配并行算法，该算法所需的时间独立于词典规模、在预处理词典和查询匹配阶段分别获得线性和对数以上的加速．(5)基于SMPClusters的扩展最长公共子序列问题的并行计算从给定的髟个目标串中查找与在线输入的查询串最相似的I∞)个目标串的问题称为(丘1)一LCS问题((丘p—LCS问题)。基于二分竞赛树和并行女一选择方法，我们在SMPClusters系统上开发求解(墨1)．LCS问题的并行算法，Dawn，,2000并行机器上的实验结

6、果表明此算法获得线性加速并具有很好的可扩放性。在设计并行局部外排序算法的基础上，我们通过应用k-k路由和k-k内排序方法提出了基于Ⅳ结点．v磁盘SMPCIusters模型的(K∞一LCS并行算法。提出在SMPCIusters模型上研究(K，1)．LCS和(K，∞．LCS问题的并行计算充分挖掘了细粒度并行性和粗粒度并行性相结合的优势．关键词：串匹配，多模式匹配，近似串匹配，近似词典匹配，最长公共子序列顺序算法，并行算法，并行计算模型。IlAbstractThestringmatchingisoneofthebasicandimportant

7、researchproblemsincomputerscience．IthasbeenwidelyapplyingtomanyareassuchasIntemetinformationsearching，bioinformatics，networkintrusiondetection，networkremoteinstructionandE-commerce，etc．Thispaperstudiestheexactstringmatching，multiplepatternmatching，approximatestringmatchin

8、g，approximatedictionarymatchingandtheextendedlongestCOITllllOnsubsequenceproblems．Themaincontent