基于有限状态自动机的中文多模式匹配算法研究

摘要

模式匹配是计算机应用领域重要的研究方向之一,广泛应用于入侵检测、信息检索、生物科学等方面。随着计算机网络技术的飞速发展,信息量呈爆炸式增长,如何提高模式匹配算法的性能成为了信息检索、内容过滤等领域研究的热门课题。
　　本文介绍了几种重要的模式匹配算法,包括单模式匹配和多模式匹配算法,如BF算法、BM算法、QS算法和AC算法、AC_BM算法、WM算法等,分析了它们的时间性能,并比较了各自的优缺点。
　　随着中文模式串数目的增加,基于有限状态自动机的多模式匹配算法的存储空间会快速膨胀,goto函数以及查询跳转距离的计算量大,从而导致算法的时空性能急剧下降。针对该问题,本文提出了带跳转距离的邻接链表存储方式,为每一状态建立一个单链表,所有单链表与顶点表构成邻接链表,并与跳转距离表融为一体,可同时完成状态与跳转距离的查询,提高了算法的时空效率。基于带跳转距离的邻接链表存储方式,设计了一种适合中文的多模式匹配算法—AC_SC算法,并分析了AC_SC算法的时空性能。
　　最后,对有限状态自动机不同存储方式的时空性能和不同跳跃式匹配算法的时间性能进行了测试。实验结果表明,本文提出的带跳转距离的邻接链表存储方式,其空间性能远优于完全Hash表和状态矩阵存储方式,时间性能优于状态矩阵存储方式,略低于完全Hash表存储方式。AC_SC算法的平均跳转距离和时间性能优于AC_TunedBM算法、AC_WM算法及IACBM算法,适合大规模中文模式匹配。

目录

封面

声明

中文摘要

英文摘要

致谢

目录

插 图 清 单

表 格 清 单

第一章 绪论

1.1 概述

1.2 本文研究内容

1.3 论文的组织结构

第二章 模式匹配算法

2.1 模式匹配的定义

2.2 单模式匹配算法

2.3 多模式匹配算法

2.4 本章小结

第三章 基于有限状态自动机的多模式匹配算法研究

3.1 有限状态自动机的存储方式

3.2 跳跃式多模式匹配算法

3.3 本章小结

第四章 适合中文的多模式匹配算法

4.1完全 Hash表和状态矩阵存储方式的缺陷

4.2带跳转距离的邻接链表存储方式

4.3 AC_SC算法

4.3 本章小结

第五章 实验与分析

5.1 实验环境

5.2 实验方案

5.3 实验结果与分析

5.4 本章小结

第六章 总结与展望

6.1 总结

6.2 展望

参考文献

攻读硕士学位期间发表的论文

攻读硕士学位期间参与的科研项目