摘要：

在分析AC算法及其相关算法的基础上,提出一种改进的多模式匹配算法AC_TE。利用该算法构建1个字符串跳跃表和2个哈希表,字符串表存储模式树中两两相邻字符组成的字符串及其位置,2个哈希表分别存储模式树末层字符串和字符。采用多层跳跃规则依次查找这3个表,在不发生漏检的情况下,使模式树的最大移动距离为最短模式串长度加3。从模式树移动次数、匹配阶段时间、各种跳跃距离的概率3个方面测试算法性能。实验结果表明,与AC算法相比,AC_TE算法具有更大的模式树移动距离,消耗的时间更少。

关键词: 多模式匹配, AC算法, 漏检, 移动距离, 模式树

Abstract:

A time efficient AC algorithm AC_TE is suggested for multiple pattern string matching based on the analysis of AC and related algorithms.The AC_TE algorithm constructs a string shift table and two hash tables.The string shift table stores every adjacent two characters of pattern tree and their positions,while the two hash tables store last two strings and last character of pattern tree respectively.AC_TE uses multiple level skipping rules to check these three constructed tables.As a result,pattern tree’s shift distance can be shortest pattern length pluses 3 without missing matched position.To analyze the performance of the AC_TE algorithm,some experiments are done from three aspects which are pattern tree shift times,matched time and probability of different shift distance.Experimental results show that compared with AC algorithm,AC_TE has longer pattern tree shift distance and better time performance.

Key words: multiple pattern matching, AC algorithm, omission, shift distance, pattern tree

中图分类号: 

• TP301.6