2023年7月20日发(作者：)

维普资讯

第２７卷第２期　大庆师范学院学报　ＪＯＵＲＮＡＬ　ＯＦ　ＤＡＱＩＮＧ　ＮＯＲＭＡＬ　ＵＮＩＶＥＲＳｎＴＹ　Ｖ０１．２７　Ｎｏ．２　Ａｐｉｌ１．２Ｏｏ７　２００７年４月　几种模式匹配算法的效率分析　巫喜红　（嘉应学院计算机科学与技术系，广东梅州５１４０１５）　摘要：分析几种模式匹配算法如ＫＭＰ、ＢＭ、ＲＫ、ＳＯ。通过上机实验对这些算法的匹配时间进行测试，结果表明在　这些模式匹配算法中ＢＭ算法是速度最快效率最高的算法。　关键词：模式匹配；ＫＭＰ算法；ＢＭ算法；ＲＫ算法；ＳＯ算法　作者简介：巫喜红（１９７５一），女，广东丰顺人，嘉应学院计算机科学与技术系讲师。　中图分类号：ＴＰ３０１．６文献标识码：Ａ文章编号：１００６－２１６５（２００７）０２－００５０－０３收稿日期：２００６—１２—３０　０引言　模式匹配算法一直是研究焦点之一，它应用非常广泛，如拼写检查、语言翻译、数据压缩、搜索引擎、网　络入侵检测、计算机病毒特征码匹配等。　ｌ模式匹配算法　字符串的的定位操作通常称作串的模式匹配，是一种重要的串运算　。模式匹配的定义为：对于给定　的正文主串Ｔ＝Ｔ　……Ｔ　（长度为ｎ）和模式串Ｐ＝Ｐ　……Ｐ　（长度为ｍ），（ｎ＞＞ｍ），要求在主串Ｔ中寻找　等于模式串Ｐ的子串，如果在Ｔ中找到等于Ｐ的子串，则称匹配成功，函数值返回为Ｐ中第一个字符相等　的字符在主串Ｔ中的序号，否则称为匹配失败，函数值返回为０。　在研究各算法前，作如下一些相关定义：　字符集：Ｃ＝｛ＣＩ　Ｃ在正文中出现｝　正文串Ｔ：Ｔｌ　Ｔ２……Ｔ。…Ｔｉ＋　一．…Ｔ　模式串Ｐ：Ｐｌ…Ｐｉ…Ｐ　１．１　ＫＭＰ算法　ＫＭＰ算法的思想是：若某趟匹配过程中Ｔ［ｉ］和Ｐ［Ｊ］不匹配，而前Ｊ一１个字符已经匹配，此时只需右　移Ｐ，Ｔ不动，即指针ｉ不回溯，让Ｐ［ｋ］与Ｔ［ｉ］继续比较。移动后重新开始比较的位置ｋ仅与模式串有关，　因此ｋ可以事先确定。若定义函数ｎｅｘｔ（Ｊ）＝ｋ，则ｎｅｘｔ函数的定义为：　ｎｅｘｔ（ｊ）＝ｍａｘ｛ｋ　Ｉ　Ｐ［１．．ｋ一１］＝Ｐ［Ｊ—ｋ＋１．．ｊ一１］｝　ＫＭＰ算法将模式串向右滑动可以提高匹配算法的效率，但相对比较复杂，时间复杂度为Ｏ（ｍ＋ｓ），空　间复杂度为Ｏ（ｓ）。　１．２　ＢＭ算法　Ｊ　受ＫＭＰ算法的启发，Ｂｏｙｅｒ和Ｍｏｏｒｅ提出了一种新的字符串快速匹配算法——ＢＭ算法。它是从另外　一个角度出发，提出一种比较新颖的方法来求解模式匹配问题。其基本思想是从右向左的把模式同文本　做比较。开始时仍是Ｐ的最左边与Ｔ的最左边对齐，当某趟比较中出现不匹配时，ＢＭ算法采用两条启发　性规则计算模式串右移的距离，即坏字符启发规则和好后缀启发规则；当与最右的模式符号做比较的文本　符号在模式中根本就没有出现，则模式可以在这个文本符号之后移位ｍ个位置。　ＢＭ算法的关键是，对模式串Ｐ定义一个从字母到正整数的映射函数ｄｉｓｔｌ，　ｄｉｓｔｌ：ｃ一＞｛１，２，…，ｎｌ｝　ｄｉｓｔｌ也称为滑动距离函数，给出了可能出现的任意字符ｃ在模式串中的位置。ｄｉｓｔｌ函数定义：具体　５０