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

高效精确字符串匹配算法的研究与实现

作　者: 周江涛
导　师: 方滨兴
学　校: 哈尔滨工业大学
专　业: 计算机科学与技术
关键词: 串匹配 TextSearch Bit-Parallelism 自动机
分类号: TP391.41
类　型: 硕士论文
年　份: 2008年
下　载: 129次
引　用: 0次
阅　读: 论文下载

内容摘要

串匹配算法是计算机科学领域中一个重要的基础研究领域。在文本处理、数据压缩、搜索引擎、生物计算,以及网络安全等大量的应用中,都需要进行串匹配。本文主要讨论精确模式串匹配,主要内容包括:首先对Linux内核中的TextSearch库进行了分析和研究,并且针对其缺陷和不足进行了改进,将TextSearch从内核中提取出来,形成了串匹配算法库LibTextSearch,并作为独立第三方开源库发布,该库运行于用户空间,同时向LibTextSearch库中添加了多种高效的串匹配算法,并简单介绍了这些算法的应用特点和使用场合,大大丰富了用户的选择范围。基于BNDM算法提出了LNDM算法,该算法使用交互重叠的宽窗口来扫描正文的思想,在窗口中先从中间位置往前扫描模式串的前缀,然后在右窗口中从前往后扫描模式串的后缀,最大化的挖掘出当前窗口中的有用正文信息,使得窗口在移动时损失的信息尽量小,提高了算法的效率,使得最差时间复杂度、最优时间复杂度和平均时间复杂度分别达到了理论最优结果O(n)、O(n/m)以及O(n logσ(m)/m)。性能测试实验也验证了他们的平均时间复杂度最优的结果,在查找短模式时,LNDM算法在大字母表情况下是最快的。本文还将BMA算法与Bit-Parallelism思想进行结合,提出了NBMA(Nondeterministic Boyer-Moore Automaton)算法,BMA算法使用BM自动机来进行字符串匹配,但是该自动机使用的状态数是模式串的指数函数,而NBMA使用Bit-Parallelism技术来模拟非确定的BMA,避免了BMA状态数大的问题,最后给出了实验结果。最后本文提出了一个字符串匹配算法的自动化测试平台,该平台采用一系列的自动化脚本来生成随机文本测试实验中用到的随机正文和随机模式信息,并可根据运行参数来自动化的进行模式匹配算法的测试实验,最后给出使用gprof程序得到的各个算法运行时间,方便了用户在随机文本情况下的测试字符串匹配算法过程。

全文目录

摘要  4-5
Abstract  5-9
第1章绪论  9-13
  1.1 课题背景及研究意义  9-10
  1.2 国内外在该方向上的研究综述  10-11
    1.2.1 串匹配算法理论的研究现状  10-11
    1.2.2 国内对串匹配算法的研究现状  11
  1.3 本课题的研究内容  11
  1.4 论文组织结构  11-13
第2章 LibTextSearch算法库  13-30
  2.1 Linux内核中的TextSearch模块  13-16
    2.1.1 TextSearch模块简介  13
    2.1.2 TextSearch模块的体系结构  13
    2.1.3 TextSearch模块的使用过程及示例  13-15
    2.1.4 TextSearch模块的缺点和限制  15-16
  2.2 LibTextSearch库概述  16-17
    2.2.1 LibTextSearch库的来源  16-17
    2.2.2 LibTextSearch库的体系结构  17
  2.3 LibTextSearch库中包含的算法  17-28
    2.3.1 Knuth-Morris-Pratt算法  18-19
    2.3.2 Boyer-Moore算法  19-22
    2.3.3 Boyer-Moore Horspool算法  22-23
    2.3.4 Shift-Or算法  23-24
    2.3.5 Reverse Factor算法  24-26
    2.3.6 Quick Search算法  26
    2.3.7 Backward Nondeterministic Dawg Matching 算法  26-27
    2.3.8 Linear Nondeterministic Dawg Matching 算法  27
    2.3.9 Nondeterministic Boyer-Moore Auotmaton 算法  27
    2.3.10 LibTextSearch库中算法小结  27-28
  2.4 LibTextSearch库的使用示例  28-29
  2.5 本章小结  29-30
第3章 LNDM算法的研究和实现  30-49
  3.1 引言  30
  3.2 BNDM算法简介  30-34
    3.2.1 BDM算法简介  30-31
    3.2.2 BNDM算法简介  31-33
    3.2.3 BNDM算法搜索实例  33-34
  3.3 LNDM算法  34-39
    3.3.1 Bit-Parallelism思想  34-35
    3.3.2 LDM（Linear Dawg Matching）串匹配算法  35-37
    3.3.3 LNDM算法思想  37-39
    3.3.4 LNDM算法搜索实例  39
  3.4 理论分析  39-43
    3.4.1 正确性验证  39-41
    3.4.2 复杂度分析  41-43
  3.5 实验结果  43-44
    3.5.1 实验环境  43-44
    3.5.2 随机文本实验结果  44
  3.6 本章小节  44-49
第4章 NBMA算法的研究和实现  49-69
  4.1 引言  49
  4.2 BMA算法简介  49-58
    4.2.1 BMA算法思想  49-50
    4.2.2 一个BMA的示例  50-52
    4.2.3 构造BMA  52-54
    4.2.4 BMA的状态数  54-58
  4.3 NBMA算法思想  58-61
  4.4 匹配窗口滑动距离  61-63
    4.4.1 LOG2 对数法  62-63
    4.4.2 查表法  63
    4.4.3 算法性能比较  63
  4.5 实验结果  63-64
    4.5.1 实验环境  63
    4.5.2 随机文本实验结果  63-64
  4.6 本章小结  64-69
第5章串匹配算法自动化测试平台  69-74
  5.1 串匹配算法性能测试  69
  5.2 随机文本测试  69-71
  5.3 GPROF 实用程序  71-72
  5.4 收集运行结果  72-73
  5.5 本章小结  73-74
结论  74-75
参考文献  75-79
攻读学位期间发表的学术论文  79-81
致谢  81

高效精确字符串匹配算法的研究与实现

内容摘要

全文目录

相似论文