一种高效的多模式字符串匹配算法.pdf

《一种高效的多模式字符串匹配算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第卷第期计算机工程年月开发研究与工程应用文章编得文献识中■分集婦■一种高效的多模式字符串匹配算法许家供李东金鍵马中国互联网络信息中心，北京中国科学院计算机网络信息中心，北京中国科学院大学，北京东北师范大学理想信息技术研究院，长春一瘺要：在多棋式字符串匹配算法基础上，结合算法和算法的优点，提出种高一效的多模式字符串匹配算法，方面増加模式树根节点失配的概率，。该算法能够充分利用本次匹失败和部分匹配成功的信息一匹配时的连续跳转提离匹配过程中失配时的跳跃距离。另方面进免不必要的状态转移，实现不。分析指出，在最

2、好情况和平均一情况下，时间复杂度均优于算法和算法。实验结果表明，般情况下该算法的査找时间仅为算法的算法的算法的左右。，算法的左右关键谓：宇符串匹多棋式匹配；有限自动状态机；算法复杂度；网络安全；信息检索，，，【】【】算法。其中利用已匹配信息实现，算法，了无回溯的比较时间复杂度为和分别为文本、、、模式匹配算法在文本挖掘信息检索模式识别图—串和模式串的长度。算法是种经典的跳跃式匹配算像处理以及网络安全等领域中被普遍采用。随着互联网的法，平均情况下比更快，最好情况下时间复杂度为迅猛发展’巨大的流量承栽着各种

3、信息充斥着网络，如何。算法是对算法的简化实现。算法则髙效地实现针对信息内容的检測过滤，成为网络安全领域在算法細上进行改进，最好情况下时间复杂度为一个关键问题一的，模式匹配算法正是内容检測的项关键技术。一多模式匹配是从文本串？中次查找多个模式串、经典的单模匹配算法主要包括難…凡所有模式串构成集合巧。其中，为們中模算法、算法以及式串的数目；为所有模式串长度之和；讲为模式串兄的“”基金項目。：国家自然科学基金资助项目多棋态作弊间的统计机器学习方法研究（一：：许家铭男硕士研究生，主研方向网络安全，下，研究员，

4、高作者介代互联网技术；李晓东；金键级工程师；。马盈，播士研究生收稿日■修日■316计算机工程年月日长度；为最短模式串的长度；为最长模式串当文本字符集很小时，好后缀规则起主要加速作用，坏字的长度；字符集；是字符集大小。多模匹配的经典算符规则优化效果并不明显；随着文本字符集的增大，坏字【法主要包括：算法、符规，算法则加速效果明显提高，好后缀规则加速效果则明显下【以及算法算法。其中，算法通过预处理，将降。因此，算法仅使用坏字符规则，在发生失配时，多个模式串转换为树型有限自动状态机对文本串并不考虑文本中造成失

5、配的字符仅由文本中与模式最一扫描次就可完成所有模式串匹配，匹配时间复杂度为右端对齐的字符汗叫决定右移量。，就获得了很好的效果一算法融合了算法和算法思想，并在算法则在此基础上进步改进，在发生失配时，首先考开源入侵检测系统上实现平均情况下效率优于虑文本中的下一个字符，使得最大右移距离达到箅法，最好情况下时间复杂度为算法在模式较短和字符集较大时优化效果明显叫。将算法与结合并改进，平均情况下效率优于地定义如下：算法。，最好情况下时间复杂度为算法则将算法与结合并改进最好情况下时间复⑷而未出杂度为，其他情况（虽然

6、算法、算法和算法在实际应用中表现优异，但仍未能充分利用匹配不成功的信息，导致跳算法跃距离有限。，并对算法进行，匹配效率受模式串数目影响较大本文在算法将算法与结合、算法的基础上。首先根据們构造反向构建树型、，汲取算法和算法思想，并提出进扩展和改进一比和函数，然后构造坏字符表和好后缀表。在步的改进，充分利用匹配失败的信息，跳过更多无需较的字符，将文本中，，避免无用的状态转移。构造好后缀表时导致失配的字符也考虑在内增加了跳跃距离。从中厂和说’可定义如下’相关算法其中：，为失配时所处状态算法的基本思想是从右向

7、左进行逆向匹配。在预处本⑷未出现理时构造坏字符表和好后缀表；在时利用坏字符和好，⑷麯情况伽‘和砷后缀启发性规则尽量多的字符：。算法基本流程如下，跳过—开始（首先从，将文本串的第个字符与模式串的左斓对齐，。然后从与的最右端字符开始匹配匹配柳，荐一则向左依次匹配下字符。，直到匹配成功或发生失配发。生失配时，根据情况将尸向右移动，若失配发生在的最右靖字符，则使用坏字符表跳转，使字符吓与其在「。中出现的下一位置对齐；若已匹配部分子串并在和处失配，赚用好后缀表跳转，使已匹配子串与其在尸中【】在匹配时采用改进的启

8、发规则：，匹配算法描述如下出现的下位置对齐。餓多模配算法：坏字符表记录字符在中出现的最靠右位置，定义为输入文本串叩对娜灿声，咖和函数输出模式串在文本中匹配的位置在冲未出现‘⑴其他情况好后缀表记录各后缀在中重复出现的最靠右位置，°丁丨定义如下：？本‘丁⑴’■服算法和算法算法基于以下研究发现对算法进行了简化：一：第卷第期许家铭，李晓东，金键，等种高效的多模式字符串匹配算法「““丨“、“！被丨；錐釤一”甩■■改进的快速多模匹配算法—模式屯数目坏字符规则的改进图