An Improved AC Multiple Pattern Matching Algorithm
Liu Chunhu · Jisuanji gongcheng · 2015
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.