分块法的模式匹配算法的研究

• 作者: 巫喜红
• 来源期刊: 重庆邮电大学学报（自然科学版）
• 学科: 工学
• 关键词: 分块法 模式匹配 分块模式匹配(BPM)算法 BM算法 Sunday算法
• 年，卷（期）: 2014,（4）
• 所属期刊栏目: 计算机与自动化
• 页码范围: 551-555
• 页数: 5页
• 分类号: TP393
• 字数: 4814字
• 语种: 中文
• DOI: 10.3979/j.issn.1673-825X.2014.04.022

摘要

为提高模式匹配算法性能,介绍经典的模式匹配算法Byoer-Moore和Sunday,分析它们改进后的效率,根据分块法的特点,提出一种新的分块模式匹配(block pattern matching,BPM)算法.BPM算法在预处理阶段先确定模式串的首字符在文本串的位置,再确定此字符后长度等于模式串长度的字符是否等于模式串的尾字符,若符合条件,采用单链表存储结构进行存储,在匹配阶段,利用单链表信息进行双向匹配.实验结果表明,BPM算法大大减少了匹配次数和字符比较个数,从而提高匹配效率.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	巫喜红	嘉应学院计算机学院	34	144	6.0	11.0