基于BM窗口竞争的高效单模式匹配算法

陈 伟，滕宏舜

（浙江师范大学数理与信息工程学院，浙江 金华321004）

1 概述

字符串模式匹配，即在一个文本T＝t1t2…tn中找出某个特定模式串P＝p1p2…pn首次出现或所有模式串出现的位置，其中，T和P都是有限字符集Z上的字符序列；n和m 为正整数，且n≥m。T中当前和模式P进行匹配的m长子串被称为匹配窗口。

字符串模式匹配算法作为基础算法之一，已被广泛应用于计算机和网络数据搜索方面。它在文档编辑、文献资料检索、海量数据挖掘、DNA序列检测、病毒检测、图像处理、Web搜索、网络入侵检测、内容安全技术及事务管理系统等非数值处理方面有非常广泛的应用。如网络入侵检测系统，约有30%的时间用来进行模式匹配［1］，而在加强网络交互的情况下，则用于模式匹配的时间约占总量的80%［2］。

模式匹配问题可分为单模式匹配和多模式匹配2类。典型的单模式算法主要有KMP算法、SKIP算法、BM算法［3］。其中有大量基于BM的改进算法 BMH［4］，BMHS［5］，BMH2C［6］，BMG［7］更适合中文字符的 BM 改进［8］、N－BMHS［9］。文献［10］分析双字符串在模式串中出现的不同情形和模式串后继字符的关系确定右移量。文献［11］提出基于Sunday算法的改进算法，在匹配前先找到模式串中的特征字符（出现概率最小的字符），再进行特征字符与尾字符双重匹配，增大了首次不匹配的可能性。文献［12］提出Sunday改进算法，利用Unicode中文双字节编码的内部关联性，优化原Sunday算法的跳转值，补偿Sunday算法因降低空间消耗而造成的时间效能损耗，提升在中文Unicode编码环境下的匹配性能。Y＿BMHS算法［13］利用辅助的二维数组，文本串中间隔的2位字符和模式串首字符的唯一性，使得模式串以最大位移m＋3进行右移的概率提高。……