王天聪, 侯整风, 何 玲
(1.合肥工业大学计算机与信息学院,安徽合肥 230009;2.深圳金山信息安全技术有限公司,广东深圳 518057)
模式匹配是计算机领域的一个重要研究方向,在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)。该算法充分利用已匹配的后缀和字符串后一位字符的信息,以期在每一次跳跃中跳跃尽量大的距离。……