分块法模式匹配算法研究.pdf

26 4 ( ) Vol． 26 No． 4 第 卷第 期 重庆邮电大学学报 自然科学版 2014 8 Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition) Aug． 2014 年 月 doi :10． 3979 /j． issn． 1673-825X． 2014． 04． 022 分块法的模式匹配算法的研究 巫喜红 ( ， 514015) 嘉应学院计算机学院 广东梅州 : ， Byoer-Moore Sunday ， ， 摘 要 为提 高模式 匹配算法性能 介绍 经典的模式 匹配算法 和 分析 它们 改进后 的效率 根据 ， ( block pattern matching ，BPM) 。BPM 分块法的特点 提 出一种新的分块模式 匹配 算法 算法在预处理阶段先确定模 ， ， 式 串的首字符在文本 串的位置 再确定此字符后 长度等于模 式 串长度 的字符是否等于模 式 串的尾 字符 若符合条 ， ， ， 。 ，BPM 件 采用单链表存储结构进行存储 在 匹配阶段 利用单链表信 息进行双 向 匹配 实验 结果表明 算法 大大减 ， 。 少了匹配次数和字符 比较个数 从 而提 高匹配效率 : ; ; ( BPM) ; BM ; Sunday 关键词 分块法 模式 匹配 分块模式 匹配 算法 算法 算法 中图分类号:TP393 文献标识码:A 文章编号:1673-825X( 2014) 04-0551-05 Pattern matching algorithm based on block method WU Xihong (Department of Computer Science and Technology ，Jiaying University ，Meizhou 514015 ，P． Ｒ． China) Abstract :In order to improve the performance of pattern matching algorithms ，the paper analyses the classic BM and Sun- day algorithm and their improved efficiency ，then it poses a new pattern matching algorithm :block-pattern-matching (BPM) algorithm according to the c