FACA: A Multiple Pattern Matching Algorithm Based on AC Automata
Chen Xin-chi, Han Jian-min, Jiong Jia · Jisuanji gongcheng · 2012
Aho-Corasick automata algorithm has to backtrack for multiple times to shift to the effective subsequence state when it fails in one pattern matching.In order to solve this problem,this paper proposes a fast multiple patterns matching algorithm based on Aho-Corasick automata.The improved algorithm builds the subsequence pointers for each state.On failing matching,it can shift to the effective subsequence state through the subsequence pointers efficiently,which can reduce backtracking times in Aho-Corasick automata.Furthermore,the proposed algorithm achieves information such as matching length,matching times etc for each state during building automata by dynamic programming methods.Based on this information,the algorithm can calculate the repeated times of pattern strings,earliest position of pattern strings.Experimental results show that the algorithm has advantages of matching accuracy,efficiency,and supporting on-line operation.