基于字符频率的字符串模式匹配算法的研究

发布时间：2018-07-13 17:37

【摘要】：本文分析了经典的BM算法和Sunday算法,根据字符频率的特点提出了一种新的模式匹配算法CFPM。CFPM算法确定模式串中字符频率最低的关键字符后,扫描文本串中该关键字符的位置并存储,最后根据这些位置信息进行快速地匹配,匹配方式是以关键字符为始点先匹配左部分再匹配右部分。为了验证CFPM算法的性能,在相同的文本串和模式串情况下,从匹配移动次数和匹配的字符个数两方面对CFPM算法进行实验。实验结果证明,由于CFPM算法能够很大限度地跳过坏字符,大大减少了匹配次数和字符比较个数,有效地加快了匹配速度,其效率优于BM、Sunday等算法。
[Abstract]:In this paper, the classical BM algorithm and Sunday algorithm are analyzed, and a new pattern matching algorithm, CFPM. CFPM, is proposed to determine the key characters with the lowest character frequency in the pattern string according to the characteristics of the character frequency. The position of the key character in the text string is scanned and stored. Finally, according to the position information, the matching method is to match the left part first and then the right part with the key character as the starting point. In order to verify the performance of CFPM algorithm, the experiment of CFPM algorithm is carried out in the case of the same text string and pattern string, from two aspects: the number of matching moves and the number of characters matched. The experimental results show that the CFPM algorithm can greatly skip the bad characters, greatly reduce the number of matches and the number of characters compared, effectively accelerate the matching speed, and its efficiency is better than that of BMU Sunday algorithm.
【作者单位】： 嘉应学院计算机学院;广东工业大学计算机学院;
【基金】：国家十二五科技支撑计划项目(2012BAH27F05) 广东省自然科学基金项目(S2012020011071) 广东省战略性新兴产业核心技术攻关项目(2012A010701004)
【分类号】：TP393.08

【参考文献】

中国期刊全文数据库 前5条

1 陈论;魏海平;王福威;;一种面向入侵检测的模式匹配算法[J];辽宁石油化工大学学报;2009年01期

2 邓一贵;;基于字符频率及分治法的字符串模式匹配算法[J];计算机科学;2008年06期

3 王成;刘金刚;;一种改进的字符串匹配算法[J];计算机工程;2006年02期

4 万晓榆;杨波;樊自甫;;改进的Sunday模式匹配算法[J];计算机工程;2009年07期

5 洪涛;侯整风;;基于字频的模式匹配算法[J];微计算机信息;2010年33期

【共引文献】

中国期刊全文数据库 前10条

1 苏珉;;基于入侵检测的BMHS模式匹配算法改进[J];四川兵工学报;2011年02期

2 田宏;李君秋;;一种改进的模式匹配算法[J];大连交通大学学报;2010年04期

3 杨振宇;;中英文混合字符串切分技术[J];电脑知识与技术;2011年14期

4 李志清;;面向入侵检测的改进BM模式匹配算法[J];计算机安全;2011年05期

5 程克勤;邓林;王继波;朱跃农;;基于应用层的Windows个人防火墙的设计与实现[J];合肥工业大学学报(自然科学版);2011年05期

6 李必鹏;肖书成;李洋;;一种BM模式匹配的改进算法[J];后勤工程学院学报;2008年01期

7 纪福全;朱战立;;一种可做特殊用途的字符串匹配算法[J];计算机与信息技术;2006年08期

8 徐珊;袁小坊;王东;谢高岗;;Sunday字符串匹配算法的效率改进[J];计算机工程与应用;2011年29期

9 万晓榆;杨波;樊自甫;;改进的Sunday模式匹配算法[J];计算机工程;2009年07期

10 单懿慧;蒋玉明;田诗源;;面向入侵检测的改进BMHS模式匹配算法[J];计算机工程;2009年24期

中国重要会议论文全文数据库 前1条

1 卢佳佳;肖桂荣;;基于地理空间信息元数据的标准符合性测试方案设计[A];2011年全国电子信息技术与应用学术会议论文集[C];2011年

中国博士学位论文全文数据库 前2条

1 魏景芝;超宽带无线网络若干安全问题研究[D];北京邮电大学;2008年

2 郭磊;面向高速网络管控的多业务识别关键技术研究[D];解放军信息工程大学;2012年

中国硕士学位论文全文数据库 前10条

1 朱俊;多模式匹配算法研究[D];合肥工业大学;2010年

2 刘小明;入侵检测系统中模式匹配算法的研究[D];江西理工大学;2010年

3 程舰;基于内容的Internet Web中文信息过滤[D];北京交通大学;2011年

4 郑永伯;手机软件包敏感信息扫描系统的设计与实现[D];北京邮电大学;2011年

5 段智宏;入侵检测系统中单模式匹配算法的研究[D];江西理工大学;2011年

6 于秀;近似字符串匹配在基于内容的视频检索中的应用[D];山东大学;2011年

7 周志平;基于半监督聚类的入侵检测防火墙研究[D];广西师范大学;2011年

8 周东旭;Ares协议分析与流量检测机制研究[D];南京邮电大学;2012年

9 王军博;基于模式匹配算法的文件类型识别技术的研究[D];解放军信息工程大学;2011年

10 饶平峰;基于Android平台的物品分享系统的设计与实现[D];大连海事大学;2012年

【二级参考文献】

中国期刊全文数据库 前10条

1 张雪松;田宏;;面向入侵检测的Aho-Corasick算法内存消耗研究[J];辽宁石油化工大学学报;2008年01期

2 王永成,沈州,许一震;改进的多模式匹配算法[J];计算机研究与发展;2002年01期

3 赵一瑾;一个改进的BM串匹配算法[J];计算机研究与发展;1998年01期

4 王成;刘金刚;;一种改进的字符串匹配算法[J];计算机工程;2006年02期

5 张鑫,谭建龙,程学旗;一种改进的Wu-Manber多关键词匹配算法[J];计算机应用;2003年07期

6 高朝勤;陈元琰;李梅;;一种面向入侵检测的快速多模式匹配算法[J];计算机应用;2008年01期

7 曾慧惠;袁世忠;胡鹏;;入侵检测系统中高效模式匹配算法的研究[J];计算机应用与软件;2008年04期

8 周延森;汪永好;;网络入侵检测系统模式匹配算法研究[J];计算机工程与设计;2008年07期

9 殷超;李大兴;;基于改进BM算法的确定型有穷自动机的设计[J];微计算机信息;2008年07期

10 钱屹,侯义斌;一种快速的字符串匹配算法[J];小型微型计算机系统;2004年03期

【相似文献】

中国期刊全文数据库 前10条

1 徐成;孙伟;戴争辉;喻飞;;一种面向入侵检测的BM模式匹配改进算法[J];计算机应用研究;2006年11期

2 申晋祥;杨秋翔;;模式匹配算法的研究与改进[J];电脑开发与应用;2007年07期

3 闵联营;赵婷婷;;BM算法的研究与改进[J];武汉理工大学学报(交通科学与工程版);2006年03期

4 闵联营;赵婷婷;;模式匹配算法的研究与改进[J];计算机与现代化;2006年08期

5 曾慧惠;袁世忠;胡鹏;;入侵检测系统中高效模式匹配算法的研究[J];计算机应用与软件;2008年04期

6 张丽霞;陈莉;;一种改进的模式匹配算法[J];微计算机信息;2008年30期

7 朱勇强;;IDS中的BM算法及改进[J];科技资讯;2007年27期

8 孙克雷;;IDS中一种快速模式匹配算法[J];安徽理工大学学报(自然科学版);2006年03期

9 任丛美;阮冬茹;郭彦颖;;入侵检测模式匹配算法的研究与改进[J];中国新技术新产品;2008年16期

10 陈小冬;程克非;周科;;信息过滤系统中字符串匹配算法的研究[J];微计算机信息;2008年24期

中国重要会议论文全文数据库 前6条

1 侯整风;张谷原;;一种基于中文的多模式匹配算法[A];2011中国仪器仪表与测控技术大会论文集[C];2011年

2 王艳秋;兰巨龙;;基于Wu-Manber的快速跳跃多模式匹配算法[A];第四届中国软件工程大会论文集[C];2007年

3 阮卫挺;马兆丰;;高速网络下的恶意流量检测研究[A];2010年全国通信安全学术会议论文集[C];2010年

4 房友园;齐璇;;Web服务互操作标准符合性测试框架设计与实现[A];全国第20届计算机技术与应用学术会议(CACIS·2009)暨全国第1届安全关键技术与应用学术会议论文集（下册）[C];2009年

5 蒋昱城;周健;;基于d-Left Counter Bloom Filter的深度包检测[A];全国第20届计算机技术与应用学术会议（CACIS·2009）暨全国第1届安全关键技术与应用学术会议论文集（上册）[C];2009年

6 张少波;刘明;贾晓静;朱卫东;;数据包分类算法研究与设计[A];教育部中南地区高等学校电子电气基础课教学研究会第二十届学术年会会议论文集（下册）[C];2010年

中国博士学位论文全文数据库 前3条

1 杨宏宇;网络入侵检测技术的研究[D];天津大学;2003年

2 张宝军;网络入侵检测若干技术研究[D];浙江大学;2010年

3 王洁;基于FPGA的硬件防火墙内容过滤技术研究[D];哈尔滨工业大学;2009年

中国硕士学位论文全文数据库 前10条

1 孙会儒;网络入侵检测系统中模式匹配算法的研究[D];西安电子科技大学;2011年

2 郭协潮;网络入侵检测系统中模式匹配算法的研究[D];西北大学;2010年

3 陈正虎;40Gbps业务识别系统中模式匹配算法研究[D];解放军信息工程大学;2011年

4 苏晓博;基于K步长的多模式匹配算法及硬件实现研究[D];杭州电子科技大学;2012年

5 刘鑫;网络入侵检测系统中模式匹配算法的应用研究[D];大连海事大学;2013年

6 洪涛;基于字频的模式匹配算法研究[D];合肥工业大学;2010年

7 周燕;基于有序二叉树的多模式匹配算法的研究[D];合肥工业大学;2010年

8 AHMED ABDO FARHAN SAIF;多模式匹配算法[D];吉林大学;2012年

9 朱姣姣;多模式匹配算法在移动互联网协议识别中的研究[D];武汉邮电科学研究院;2012年

10 张谷原;基于中文的多模式匹配算法及其应用研究[D];合肥工业大学;2012年

，

本文编号：2120201