学位论文 > 优秀研究生学位论文题录展示

带可变长度通配符的模式匹配算法研究

作　者: 刘应玲
导　师: 吴信东; 胡学钢
学　校: 合肥工业大学
专　业: 计算机应用技术
关键词: 通配符模式匹配 One-Off条件关键字符分割算法 CluTree
分类号: TP391.1
类　型: 博士论文
年　份: 2014年
下　载: 4次
引　用: 0次
阅　读: 论文下载

内容摘要

随着互联网的飞速发展,网络上的信息量呈现出爆炸式的增长,如何从大量信息中迅速有效地提取出所需信息成为一项重要的研究课题。高效的模式匹配算法能迅速检索出用户需要的重要信息。模式匹配问题是个古老而又经典的问题,模式P的相邻字符之间出现可变长度的通配符使的该问题更加复杂。带有通配符和长度约束的模式匹配问题PMWL (Pattern Matching with Wildcards and Length constraints)不仅具有重要的理论研究价值,而且在生物信息学、网络安全和信息检索中具有重要的实际应用价值。本文对带有可变长度通配符的模式匹配问题展开研究,主要研究内容有三个方面：(1)基于关键字符定位的模式匹配算法研究；(2)提出了一种文本分割算法,并与后缀树相结合,提高模式匹配算法的时间和空间效率；(3)对PMWL问题中匹配解的完备性问题进行研究,提出了一种新颖的数据结构CluTree,以及基于CluTree的检索算法,能进一步提高匹配解的完备性和时间效率。主要研究内容和创新如下：(1)基于关键字符定位的模式匹配算法研究；对于含有通配符和长度限制的模式匹配问题,模式中相邻字符间包含通配符使匹配问题更加复杂。当文本T的长度比较大,字符分布非常复杂时,目前的算法定位误差比较大。由于现有算法没有考虑待检索文本T分布的特点,没有考虑到模式P中子模式及各字符的不同作用,在一些不可能匹配的地方进行检索,消耗了检索时间,降低了检索效率。本文根据模式P中各字符在文本T中出现的差异及在模式P中的分布,提出一种模式P中字符重要性的评价机制,先计算出模式P的频率函数fr(PJ)和自频率函数fp(Pj),根据以上的计算结果找出模式P的KWp(k)函数,由KWP(k)函数找出了模式P的关键字符Pk。关键字符作为定位字符,然后借鉴SAIL的匹配思路,改进扫描表格的方式。当表格成功构建后,算法将得到一个匹配解。文本T扫描完毕后,算法返回所有的匹配解。(2)提出了一种文本分割算法,并与后缀树相结合,提高模式匹配算法的时间和空间效率；对大文本进行分而治之的模式匹配策略,有效地解决了大规模串匹配的性能瓶颈。如何进行正确的分割是该问题的核心部分。本文设计分割算法,从T中找出可以分割,且不影响匹配结果的点。借鉴SAIL的forward过程的思想,利用局部约束确定解的空间,排除所有不满足条件的位置。在具体实现过程中,算法逐个扫描初始分割点附近的点,若发现某个点与周围的点不可能构成一个匹配解时结束循环,返回当前扫描的位置,并将作为正确的分割位置。分割算法对大文本的检索效率有了很大提高。基于分割算法模式匹配算法能加快检索速度,因此也很好的提高了检索的时间。将分割算法与后缀树相结合的多后缀树检索算法能较大提高后缀树算法的空间效率。设计的算法可用于生物信息学领域中,进行DNA序列的匹配和蛋白质序列的识别,可以提高模式匹配的效率。(3)基于CluTree的PMWL问题匹配算法由于通配符的出现,PMWL问题中的检索将更加复杂,在不含通配符的简单模式匹配SPM (simple pattern matching)中不会有解的争议,一个待匹配文本中对于任意给定模式的解是确定的。而在PMWL问题中,一个匹配位置可能作为模式中子模式出现,也可能作为通配符的位置出现,这种匹配位置的多样性导致匹配结果的不确定性,更为复杂的是可能有多个侯选匹配串的位置相互嵌套,如何选择正确的匹配位置以确定最优解一直是个待解决的难题。多个嵌套模式中选定最优匹配位置,目前的算法在处理嵌套区域的纠缠态模式的匹配问题,都采用左优先的left-most策略。当模式比较复杂,这种相互嵌套纠缠的区域是最复杂的匹配区域,简单的左优先无法解决这类问题,必然会丢失匹配串。提出了一种基于CluTree结构的检索算法RBCT,对这样的嵌套区域建立一个多根的红黑树群CluTree,在模式的匹配过程中根据CluTree中各节点的共享度、相关度及混合信息熵来选择匹配的路径,并且运用动态剪枝技术来保证树群CluTree的动态更新和共享节点资源的释放,RBCT算法对CluTree中的节点进行遍历,最终得到优化的解。

全文目录

致谢  8-9
摘要  9-11
Abstract  11-16
插图清单  16-18
表格清单  18-20
第一章绪论  20-28
  1.1 引言  20-24
    1.1.1 串匹配在生物信息学中应用  20-23
    1.1.2 串匹配在信息安全中应用  23-24
  1.2 主要研究内容  24-26
    1.2.1 课题来源  24-25
    1.2.2 课题研究的主要内容  25-26
  1.3 内容组织  26-27
  1.4 本章小结  27-28
第二章模式匹配的相关研究  28-44
  2.1 模式匹配的相关研究  28-37
    2.1.1 精确串匹配  29-33
    2.1.2 近似串匹配  33-35
    2.1.3 其它字符串匹配  35-37
  2.2 PMWL问题研究现状  37-42
  2.3 本章小结  42-44
第三章基于关键字符定位的模式匹配算法  44-60
  3.1 前言  44-45
  3.2 关键字符  45-46
  3.3 Quicksearch算法  46-53
    3.3.1 算法描述  46-48
    3.3.2 正确性证明  48-49
    3.3.3 QuickSearch实验结果  49-53
  3.4 GQS算法  53-58
    3.4.1 GQS算法描述  53-56
    3.4.2 GQS算法实验及分析  56-58
  3.5 本章小结  58-60
第四章 PMWL问题中的分割算法  60-91
  4.1 前言  60-61
  4.2 分割问题  61-64
    4.2.1 算法描述  61-62
    4.2.2 Cut算法证明  62-64
  4.3 PMWC算法  64-68
    4.3.1 算法思想  64-66
    4.3.2 算法复杂性分析  66-67
    4.3.3 一个例子  67-68
  4.4 实验结果及分析  68-77
  4.5 基于多棵后缀树的模式匹配算法PST  77-89
    4.5.1 问题描述  77-84
    4.5.2 多棵后缀树的中子序列的添加和删除  84-85
    4.5.3 PST算法描述  85
    4.5.4 实验结果  85-89
  4.6 本章小结  89-91
第五章基于CLUTREE的PMWL问题匹配算法  91-116
  5.1 前言  91-94
    5.1.1 问题定义  92-94
    5.1.2 left-most策略  94
  5.2 CluTree的相关问题  94-99
    5.2.1 CluTree的结构及性质  95-96
    5.2.2 路径选择及剪枝策略  96-99
  5.3 RBCT算法设计  99-110
    5.3.1 算法描述  99-102
    5.3.2 时空复杂性分析  102
    5.3.3 运行实例  102-105
    5.3.4 算法性能改进  105-110
  5.4 实验结果及分析  110-114
  5.5 本章小结  114-116
第六章总结与展望  116-119
  6.1 主要研究工作  116-117
  6.2 工作展望  117-119
参考文献  119-130
攻读博士学位期间参加研究的课题和发表的论文  130-131

带可变长度通配符的模式匹配算法研究

内容摘要

全文目录

相似论文