基于汉字编码特征的中文多模式匹配算法研究

摘要

近年来网络的高速发展，信息呈爆炸式增长，模式匹配是内容过滤和信息检索的核心技术，成为计算机应用和信息安全领域中的重要研究方向。对大规模中文模式匹配，已有模式匹配算法的时间和空间性能都难以满足需求。因此，提高中文模式匹配算法的时间效率，对于提高计算机应用系统的性能有重要意义。　　本文介绍了几种经典模式匹配算法，包括BF算法、BM算法以及Sunday算法等，深入研究了AC、AC_BM以及WM等多模式匹配算法，详细描述了各算法的匹配过程，分析了它们的优缺点以及时间性能。　　AC及其改进算法基于有限状态自动机，对于大规模中文模式串匹配，由于汉字的散度较高，导致有限状态自动机中的零状态过长，在查找零状态字符时耗时较多，算法的效率急剧下降。针对此问题，本文提出了一种基于汉字编码特征混合存储结构，并提出了相应的中文多模式匹配算法，该算法有如下特点:　　(1)考虑到汉字编码的首字节范围比尾字节范围小，因此，先查找首字节，再查找尾字节，由于首字节查找失败后直接跳转，一定程度上避免了查找尾字节，降低了查找时间。　　(2)对状态字符设置匹配标记，当字符的匹配标记为0时，不再匹配模式串后继字符，有效避免重复匹配以及部分匹配，节省了匹配时间。　　(3)将跳转距离存储在状态链表和匹配桶中，在确定下一跳转距离时同时查找跳转距离，避免了重复查找跳转距离，提高了算法的匹配效率。　　最后，对有限状态自动机的不同存储方式和不同跳跃式匹配算法的时间性能进行测试。实验结果表明，本文混合存储结构的时间性能好于状态矩阵和邻接邻接链表存储方式。本文算法的时间性能优于AC_Tuned BM算法、AC_WM算法及IACBM算法，适用于大规模中文模式匹配。

目录

声明

致谢

摘要

第一章 绪论

1．1 概述

1．1．1 研究背景以及意义

1．1．2 模式匹配技术发展与研究现状

1．2 本文研究内容

1．3 本文的结构安排

第二章 模式匹配算法

2．1 模式匹配概述

2．1．1 模式匹配的定义及相关概念

2．1．2 模式匹配算法的分类

2．1．3 模式匹配应用领域

2．2 单模式匹配

2．2．1 BF算法

2．2．2 KMP算法

2．2．3 BM算法

2．2．4 BMH算法

2．2．5 Sunday算法

2．3 多模式匹配

2．3．1 AC算法

2．3．2 AC_BM算法

2．3．3 WM算法

2．4 本章小结

第三章 基于汉字编码特征的中文多模式匹配算法

3．1 常用存储结构

3．2 基于汉字编码特征的混合存储结构

3．2．1 汉字编码特征

3．2．2 混合存储结构

3．2．3 首字节桶和匹配桶

3．2．4 匹配标记

3．2．5 跳转标记

3．2．6 带跳转标记的状态链表

3．3 中文的多模式匹配算法

3．3．1 算法描述

3．3．2 算法分析

第四章 实验与分析

4．1 实验环境

4．2 实验方案

4．3 实验结果与分析

4．4 本章小结

第五章 总结与展望

5．1 总结

5．2 展望

参考文献

攻读硕士学位期间的学术活动及成果情况