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

论文摘要

串匹配算法是计算机科学领域中一个重要的基础研究领域。在文本处理、数据压缩、搜索引擎、生物计算,以及网络安全等大量的应用中,都需要进行串匹配。本文主要讨论精确模式串匹配,主要内容包括:首先对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程序得到的各个算法运行时间,方便了用户在随机文本情况下的测试字符串匹配算法过程。

论文目录

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