基于BM的模式匹配改进算法

2011-03-15 14:30:40王天聪侯整风
合肥工业大学学报(自然科学版) 2011年3期
关键词:文本

王天聪, 侯整风, 何 玲

(1.合肥工业大学计算机与信息学院,安徽合肥 230009;2.深圳金山信息安全技术有限公司,广东深圳 518057)

0 引 言

模式匹配是计算机领域的一个重要研究方向,在WWW搜索引擎、内容过滤防火墙、入侵检测系统、信息压缩乃至计算机理论等领域都有很重要的理论研究和应用价值。

经典的模式匹配算法有BF算法、KM P算法、BM算法、Tuned BM算法、BMH算法及BMHS算法[1-6]。在实际应用中,BMHS算法的效率比BM算法要高。BM采用从右到左的比较方式,并利用当前已匹配后缀和匹配失败的字符,查找预处理过的好后缀跳跃表和坏字符跳跃表,使匹配跳跃式进行,最大的可能跳跃距离为模式串长度。BMHS算法只使用文本串中位于当前窗口的下一个字符查找坏字符跳跃表,有效减少了字符比较次数。文献[7]提出了BMG算法,该算法结合了BMH算法和BMHS算法的优点,同时考虑了字符串后一位字母的唯一性,有效加快了匹配速度;文献[8]提出的BMH2C算法在BM算法及其改进算法的基础上,利用当前窗口的末字符和下一个字符组成字符串来计算右移量并保存在二维数组里,使得算法的效率得到很大提高;文献[9]提出的BMN算法通过利用2个连续字符计算模式串移动距离,提高了模式串移动最大距离的概率。

本文在对BM和BMHS算法进行简要介绍和分析的基础上综合两者之长,提出了一种更加快速的单模式匹配算法(FSBM)。该算法充分利用已匹配的后缀和字符串后一位字符的信息,以期在每一次跳跃中跳跃尽量大的距离。……

登录APP查看全文

猜你喜欢
文本
重点:论述类文本阅读
重点:实用类文本阅读
初中群文阅读的文本选择及组织
甘肃教育(2020年8期)2020-06-11 06:10:02
作为“文本链”的元电影
艺术评论(2020年3期)2020-02-06 06:29:22
在808DA上文本显示的改善
“文化传承与理解”离不开对具体文本的解读与把握
基于doc2vec和TF-IDF的相似文本识别
电子制作(2018年18期)2018-11-14 01:48:06
文本之中·文本之外·文本之上——童话故事《坐井观天》的教学隐喻
从背景出发还是从文本出发
语文知识(2015年11期)2015-02-28 22:01:59
如何快速走进文本
语文知识(2014年1期)2014-02-28 21:59:13