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

中国科学技术人学博十学位论文 中国科学技术人学博十学位论文 串匹配与序列南找并行算法研究 摘 要 串匹配是计算机科学中一个基本、重要的研究问题，它在Internet网络信，E- 有哪些信誉好的足球投注网站、生物信息学、网络入侵检测、网络远程教育、电子商务等领域具有广泛的 应用。本文围绕精确串匹配、多模式串匹配、近似串匹配、近似词典匹配和扩展 的最长公共子序列问题开展研究，主要内容、贡献和创新包括： (1)基于孙子定理和Karp-Rabin模式匹配思想的确定性串匹配算法及其 并行化 利用著名的孙子定理将长度为m的模式和正丈子串分别映射成惟一的一对 整数值，基于Karp—Rabin模式匹配思想，设计一个最坏时间复杂度仍维持为 00+棚)的精确串匹配算法，该算法既保持Karp-Rabin串匹配随机算法直观、简 明和高效的优点，又使得模式匹配结果是确定的而不只是高概率的。我们也讨论 了基于分割模式的长模式串匹配顺序和并行处理，并且将基于孙子定理和 Karp．Rabin模式匹配思想设计的串匹配算法在超立方机器上并行化。 (2)基于映射和Hashing的多模式串匹配及其并行算法 基于映射和Hashing方法研究多模式串匹配，在CREWPRAM模型上设计一 个线性加速且正丈匹配检查时间与模式个数无关的多模式串匹配并行算法。利用 可重构光计算模型ORM的完全路由和动态重构网络拓扑结构的技术，给出一个 基于ORM模型的常数时间的多模式串匹配并行算法．我们提出的基于映射和 Hashing的多模式串匹配方法比基于有限自动机理论和后缀树的多模式串匹配方 法简明、直观和易于并行化． (3)PRAM模型上代价最优的允许“差别的近似串匹配并行算法和 LARPBS模型上常数时间的允许七．误配的近似串匹配并行算法 采取波前式并行推进以及水平和斜向双并行直接计算编辑距离矩阵D的方 法，在CREW PRAM模型上，设计两个在线的代价最优、线性加速的允许缸差 别的近似串匹配动态规划并行算法．通过灵活拆分总线和合并子总线的方法动态 重构光总线系统，并巧妙利用光总线的消息播送技术以及并行计算前缀和方法， 设计了据我们所知是LARPBS模型上第一个常数时间复杂度的允许“误配的近 似串匹配并行算法。 (4)允许“差别的可变长模式串近似词典匹配及其在PRAM和BSR模 型上的并行处理 以往的文献主要考虑汉明距离等于1的允许如误配的近似词典匹配顺序算 法，本文则研究更一般的允许七-差别的可变长模式串近似词典匹配问题．基于 CREW PRAM模型，在设计Multisets排序最优并行算法的基础上，提出一个允 许“差别的可变长模式串近似词典匹配并行算法，该算法在预处理词典和查询匹 茎生竖坚燮丛生望翌±堂焦堕塞 茎生竖坚燮丛生望翌±堂焦堕塞 皇垦里兰壁型变丛垫堑茎鲨塑壅 配阶段分剐获得线性和对数以上的加速。我们在BSR模型上也设计一个允许“ 差别的可变长模式串近似词典匹配并行算法，该算法所需的时间独立于词典规 模、在预处理词典和查询匹配阶段分别获得线性和对数以上的加速． (5)基于SMP Clusters的扩展最长公共子序列问题的并行计算 从给定的髟个目标串中查找与在线输入的查询串最相似的I∞)个目标串的 问题称为(丘1)一LCS问题((丘p—LCS问题)。基于二分竞赛树和并行女一选择方 法，我们在SMP Clusters系统上开发求解(墨1)．LCS问题的并行算法，Dawn，,2000 并行机器上的实验结果表明此算法获得线性加速并具有很好的可扩放性。在设计 并行局部外排序算法的基础上，我们通过应用k-k路由和k-k内排序方法提出了 基于Ⅳ结点．v磁盘SMPCIusters模型的(K∞一LCS并行算法。提出在SMPCIusters 模型上研究(K，1)．LCS和(K，∞．LCS问题的并行计算充分挖掘了细粒度并行性和 粗粒度并行性相结合的优势． 关键词：串匹配，多模式匹配，近似串匹配，近似词典匹配，最长公共子序列 顺序算法，并行算法，并行计算模型。 Il AbstractThe Abstract The string matching is one ofthe basic and important research problems in computer science． It has been widely applying to many areas such as Intemet information searching，bioinformatics， network intrusion detection，network remote instruction and E-commerce，etc．This pa