用位并行法进行过滤的中文近似串匹配算法

摘要

字符串的匹配问题被视为计算机科学的基本问题之一。早期的研究多集中于精确匹配领域，提出了许多单模式匹配算法和多模式匹配算法。 然而人们逐渐发现在实际应用中有时更需要进行近似字符串匹配。它在信号处理、文本检索、计算生物学、病毒检测、模式识别、OCR纠错等领域均有重要的应用价值。因此，研究(设计)高效的近似字符串匹配算法具有重要的理论价值和实际意义。 应该说，近似匹配是精确匹配的变种和发展，也就是按照一定的近似标准在文本串中找出与模式串相匹配的子串。对应的，多模式近似匹配则是按照一定的近似标准在文本串中找出与模式串集合相匹配的子串。 尽管对近似字符串匹配问题的研究历史已不短，相应的文献资料也不少，不过其中绝大多数的研究对象(字符集)都是针对英文等中等大小字符集或者针对DNA等微小字符集，而针对汉字及亚洲语言等大字符集的研究却很少。其次，对多模式近似字符串匹配问题的研究也还不成熟，不管是针对中小字符集还是大字符集，均没有特别成功的解决方法。 基于上述原因，论文主要完成了如下工作：本文的第一、二章，我们简要介绍了论文的研究背景、研究目的、主要内容和组织结构。同时还对近似字符串匹配问题进行了综述，介绍了相关的理论及主要研究方法，并分别对动态规划、自动机、位并行、过滤等主要方法进行了介绍和分析。 第三章对BPM等部分重要算法进行了较详细的分析。 第四、五章是本文的核心，提出了在汉字等大字符集环境下基于过滤的位并行方法，具体包括基于汉字的单模式近似字符串匹配算法IBPM-BM和多模式近似字符串匹配算法MBPM-BM，称为基于汉字的主要原因是这两个算法在汉字等大字符集环境下的表现特别优异。算法在理论上和实践中均有较好的表现，论文还给出了复杂性分析和实验结果。需要说明的是，这两个算法的最重要特点就是在过滤阶段充分运用了位并行技术，用以充分挖掘计算机物理字长的潜力。 在第六章中，对本文进行总结，对应用前景进行了展望，并给出了未来可能的研究方向。

目录

文摘

英文文摘

第1章绪论

1.1研究背景和动机

1.2字符串匹配问题概述

1.3研究历史及现状

1.4论文的主要工作

1.5论文的组织

第2章近似字符串匹配综述

2.1相关理论

2.1.1符号和定义

2.1.2主要研究方法及其进展

2.2动态规划方法

2.2.1计算编辑距离

2.2.2用于文本近似匹配

2.2.3动态规划方法的发展及其复杂性分析

2.3自动机方法

2.3.1用于精确字符串匹配

2.3.2用于近似字符串匹配

2.3.3自动机方法的发展

2.4位并行方法

2.4.1用于精确字符串匹配

2.4.2用于近似字符串匹配

2.4.3位并行方法的发展

2.5基于过滤的方法

2.5.1基本思想

2.5.2发展状况

2.6多模式匹配及其发展过程

2.7本章小结

第3章相关的重要算法介绍和分析

3.1 BPM算法

3.2 MBPM算法

3.3 CountFilter算法及其多模式扩展

3.4 BPM-BM算法

3.5本章小结

第4章基于汉字的单模式近似字符串匹配

4.1研究目标

4.2 IBPM-BM算法思想

4.3算法思想的描述

4.3.1算法的粗略描述

4.3.2算法的细化描述

4.4算法的位运算改进

4.5计算编辑距离

4.6 IBPM-BM算法伪代码

4.7复杂性分析

4.8实验结果与分析

4.9小结

第5章基于汉字的多模式近似字符串匹配

5.1研究目标

5.2多模式跳跃引理

5.3 MBPM-BM算法的主要思想

5.3.1初步的设想

5.3.2并行记录多个bads值

5.3.3更新Mlast值

5.3.4应用MBPM

5.3.4算法的描述

5.4算法的一个具体示例

5.5 MBPM-BM算法伪代码

5.6 MBPM-BM复杂性分析

5.7试验结果与分析

5.8小结

附图

第6章结束语

6.1总结

6.2进一步的工作

参考文献

攻读硕士学位期间公开发表(录用)的论文

致谢