BM串匹配算法与改进算法的研究.pdf

2010年第 7期 福 建 电 脑 BM 串匹配算法与改进算法的研究 王 锋 (苏州大学 电子信息学院 江苏 苏州 215021) 【摘 要】：串匹配算法在数字通信等方面应用广泛，BM算法是主要的串匹配算法之一。文章在分析 了BM算法过程和 一 些现有的改进算法 ，对这些算法进行 了比较 ，并结合 BMG算法 ，提 出了一个新 的改进算法。该算法考虑 了模式匹配时出现 重复字符 时 ，比较 的前一个字符的出现情况以及模式 串首字符 的特性 ，提高 了模式 串移动 m+l位 的概率 ，提高 了匹配速度 。 【关键词】：BM算法；模式串；改进算法；模式匹配 O、引言 t 2 3 4 5 6 7 8 9 10 111213】4l5l6】7l8l92O21222j2425262 28 串匹配是字符串的一个基本运算 ．对于给 出的长度为 n的 Tp gh h h h th db p p h d 正文字符 T=T，…… 和长度为 m 的模式串P=PI……P (n lp h d m)．要找 出模式 P在正文T中的首次出现 ，一旦模式 P在正文 2 p h (I 中找到．则匹配成功 ．否则匹配失败 。字符 串匹配应用广泛 ．在数 3 p h d 字通信 、文本编辑 、图像处理 、数据压缩 、模式识别等应用 中，都 4 p h d 需要进行 串匹配 近年来对于一维字符串的匹配问题研究较多 5 P h d 1970年 ．S_A．Cook从理论上证明了一维模式匹配 问题可以在 O 6 P h d (m+n)时 问内解决 ．为串匹配算法 的进一步发展奠定 了坚实 的 p h d 理论基础 ，其 中n、m 分别为 文和模式 的长度 ；D．E．Knuth，V．R． Pratt和 T．H．M0 s仿 照 Cook的证 明构造 了 KMP算法fll：R．S． 表 1BM 模式匹配过程 Bover和J．SMOOre设计 了BM算法2[1；Karp和 Rabin给出了RK 下面我们对表 1中的BM模式匹配过程作一简单分析 ： 算法和随机算法 ．这些算法都是精确 的串匹配算法 。本文主要介 (1)第一次匹配是模式串的P与文本 中的T首字符对齐 ．然 绍 BM算法及其改进算法。 后从模式串的最后一个字符开始从右向左 比较 ，即先将 P9『1与 T 1、现有模式匹配算法的分析 9『1进行 比较 ，匹配失败 ，因此模式 串向右移动 ，同时 T9『1位置 的 目前关于模式匹配的算法很多 ．其 中最著名的两个是 KMP 字符…e。在模式串P中仅出现 1次．模式串移动 1个字符 ．即P 算法…和 BM算法2[1两个算法在最坏情况下均具有线性的有哪些信誉好的足球投注网站 8『1与 Tf9]对齐 ，从而完成第二次匹配 。 时间。