对串匹配技术中的Wu-Manber算法的研究

论文摘要

字符串匹配是计算机研究领域中的一个古老、经典而且被广泛研究的课题,是信息检索领域和计算机生物学领域等的关键技术之一。在当今的互联网时代,对匹配算法的需求日新月异,对处理的实时性的需求越来越高。这些都对原有的字符串匹配技术提出了新的挑战,有必要对原字符串匹配技术进行改进和优化。本文主要是对高效的多字符串匹配算法——Wu-Manber算法进行研究。本文针对Wu-Manber算法的散列表HASH的表项:HASH（）链表的不足,提出了基于非空公共子后缀模式的处理算法;而后综合前人对Wu-Manber算法的SHIFT表的改进,提出更加高效的字符串匹配算法;进而提出一种在大规模串匹配时对Wu-Manber算法的改进。本文的研究成果具体如下:1.基于非空公共子后缀的Wu-Manber算法的改进:针对Wu-Manber算法在处理公共子后缀模式情况下的不足,本文提出了一种基于非空公共子后缀模式的处理算法。该算法把同一next链表中有非空公共子后缀的模式汇集在一起,进一步减小了next链表的平均长度。在匹配过程中减少了字符比较的次数,从而提高算法的运行效率。本文对搜狗实验室给出的相关文档进行全文检索实验,并和原Wu-Manber算法、前人提出的改进算法进行比较。实验结果表明,本文提出的改进算法有效地减少了匹配过程中字符比较的次数,从而提高匹配的速度和效率。2.对Wu-Manber算法的综合改进:对1中提出的算法进行了改进,在对next链表进行分类的同时把含有非空公共子后缀的结点提到链表的前部;并整合了前人提出的“精确的不良字符转移和弱化的良好后缀转移的改进”方法。新改进的算法充分利用以上两种算法的优点,使匹配过程中字符比较的次数得到了进一步减少。新改进的Wu-Manber匹配算法在实验中取得了更高的效率,比原算法提高到4.6%以上。3.Wu-Manber算法在大规模模式串下的改进:对1提出的算法进行了改进,把原算法中next链表中结点的SameSubsuffix域分裂成两个子域,使得在大规模模式串的情况下,搜索过程中字符比较的次数进一步减少,新算法的效率比原算法有进一步的提高。实验结果表明,当模式串较少时,新算法效率与原算法相比有一定的损失。而随着模式串的增加,新算法具有更高的效率。因此,新算法比原算法具有更大的适用范围。

论文目录

• 中文摘要
• ABSTRACT
• 第一章 引言
• 1.1 研究字符串匹配技术的目的和意义
• 1.1.1 字符串匹配技术的应用
• 1.1.2 字符串匹配技术面临的挑战
• 1.2 本文的主要内容
• 第二章 精确字符串匹配算法综述
• 2.1 基于前缀搜索的算法
• 2.1.1 KMP算法和AC算法
• 2.1.2 Shift-And/Shift-Or算法
• 2.2 基于后缀搜索的算法
• 2.2.1 BM算法、Horspool算法
• 2.2.2 BM算法、Horspool算法在多模式串下的扩展
• 2.2.3 Wu-Manber算法
• 2.3 基于子串搜索的算法
• 2.3.1 BDM算法
• 2.3.2 SBDM算法
• 2.3.3 BNDM算法
• 2.3.4 BOM算法
• 2.4 近段的进展
• 第三章 Wu-Nanber算法的改进
• 3.1 精确的不良字符转移和弱化的良好后缀转移
• 3.1.1 精确的不良字符转移
• 3.1.2 弱化的良好后缀转移
• 3.1.3 结论
• 3.2 一种基于后缀模式处理的改进算法
• 3.2.1 后缀模式处理的改进思路
• 3.2.2 后缀模式处理的改进代码
• 3.2.3 结论
• 3.3 基于非空公共子后缀的Wu-Manber算法的改进
• 3.3.1 非空公共子后缀的定义
• 3.3.2 基于非空公共子后缀的Wu-Manber算法的改进思路
• 3.3.3 基于非空公共子后缀的Wu-Manber算法的改进代码
• 3.4 对Wu-Manber算法的综合改进
• 3.4.1 Wu-Manber算法的综合改进思路
• 3.4.2 Wu-Manber算法的综合改进代码
• 3.5 Wu-Manber算法在大规模模式串下的改进
• 3.5.1 Wu-Manber算法在大规模模式串下的改进思路
• 3.5.2 Wu-Manber算法在大规模模式串下的改进代码
• 第四章 验证和分析
• 4.1 基于非空公共子后缀的Wu-Manber算法的改进
• 4.1.1 实验环境
• 4.1.2 实验数据及分析
• 4.1.3 结论
• 4.2 对Wu-Manber算法的综合改进
• 4.2.1 实验环境
• 4.2.2 实验数据及分析
• 4.2.3 结论
• 4.3 Wu-Manber算法在大规模模式串下的改进
• 4.3.1 实验环境
• 4.3.2 实验数据及分析
• 4.3.3 结论
• 总结和展望
• 参考文献
• 发表文章目录
• 致谢
• 个人简况及联系方式