黄　宇,　侯整风,　余　虎,　刘春晖

(合肥工业大学 计算机与信息学院,安徽 合肥　230009)



一种基于汉字编码特征的中文多模式匹配算法

黄宇,侯整风,余虎,刘春晖

(合肥工业大学 计算机与信息学院,安徽 合肥230009)

对于大规模中文模式串匹配,由于汉字的散度较高,导致AC算法有限状态自动机中的零状态过长,算法的效率急剧下降。文章提出了一种基于汉字编码特征的改进算法,考虑到汉字的首字节范围比尾字节的小,先查找首字节,再查找尾字节,若失败则直接跳转,降低了查找时间。该算法通过给零状态中字符设置标记,有效避免重复匹配和部分匹配,提高了匹配效率。

AC算法;多模式匹配;汉字编码特征;标记

模式匹配算法是信息领域的重要内容,广泛应用于搜索引擎[1]、网络入侵检查系统[2-3]、DNA序列匹配[4]等领域。单模式匹配中,BM (Brute-Force)算法[5]运用坏字符规则和好后缀规则来计算模式串右移距离,实现了模式串的跳跃式匹配。BMH (Brute-Force-Horspol)算法[6]是对BM算法的改进,该算法仅考虑坏字符规则,简化预处理,提高了匹配效率;AC (Aho-Corasick) 算法[7]是一种经典的多模式匹配算法,该算法基于有限状态自动机,通过状态转移,扫描一遍文本串可匹配多个模式串。AC_BM算法[8]是AC算法的改进,其结合BM算法的模式串的跳跃式移动的思想,可跳跃式匹配,但跳转距离过于保守,平均跳转距离较小。文献[9]利用Tuned BM算法的思想计算平均跳转距离,提出AC_Tuned BM算法;文献[10]提出的IACBM算法利用BMH和QS算法的思想计算平均跳转距离。 上述方法在一定程度上增加了平均跳转距离,但没有考虑到有限状态自动机的存储结构对跳跃式匹配过程的影响。……