文档介绍：本科生毕业论文
题目名称经典中英文
模式匹配算法比较
学生姓名张宏学号 20114042034
学院信息科学与工程学院
专业年级 2011计科1
指导教师莫礼平职称高级实验师
填写时间 2014年9月28日
吉首大学教务处制
经典中英文模式匹配算法比较
目录
摘要 1
Abstract 1
第一章绪论 2
2
3
第二章模式匹配算法 3
3
—KMP算法 4
第三章常用的单模式匹配算法 5
一种改进的KMP算法 5
BM算法 6
第四章常用的多模式匹配算法 12
AC算法 12
WM算法 19
第五章大规模图数据库上的模式匹配算法 22
22
23
第六章一种适合中文的模式匹配算法 24
完全哈希表和状态矩阵存储方式的不足 24
一种带跳转距离的邻接链表存储方式 25
AC_SC算法描述 27
第七章实验测试及结果分析 30
实验环境 30
实验方案 30
实验结果与分析 31
结语 32
参考文献 34
摘要
模式匹配作为网络信息安全的核心技术之一,其效率直接影响整个系统的性能,一直也是学术界和工业界关注和讨论的热题。在当下,随着互联网的普及,网名数量呈几何增长,大规模数据甚至海量信息给网络信息安全带来了新的挑战,所以研究模式匹配算法具有重要的学术意义以及广阔的应用前景。
本文分析了KMP、BM、AC和WM四种经典模式匹配算法,并提出了KMP算法的一种改进策略。在面临复杂数据难以管理新形势下,本文还介绍了一种大规模图数据库上的模式匹配算法。由于对中文模式匹配的需求日益增加,本文也介绍了一种适合中文环境的模式匹配。
最后,以codeblocks编译器为工具,分析比较了四种经典模式匹配算法的性能。
关键字:模式匹配;单模式匹配;多模式匹配;大规模;中文环境。
Abstract
Pattern matching,as one of the core technologies work information security, has been affecting the performance of the whole system, and has been being the hot topics that the academia and industry pay attention to and discuss. At present, with the popularization of , net population showed a geometric growth, large-scale data and even mass data work have brought new challenges to information security. As a result, the research of pattern matching algorithm has important academic significance and broad application prospects.
In this paper, four classical pattern matching algorithms for KMP, BM, AC and WM are analyzed, and an improved KMP algorithm e up. And under the new situation of plex data been difficult to manage, this paper also describes a large-scale pattern matching algorithm based on the map database. With the increasing demand for Chinese environment pattern matching, this paper actually introduces a pattern matching for this condition.
At last, the performance of four classical pattern matching algorithms is analyzed under the piler.
Key words:pattern match