Automaton Compact Representation Technology in String Matching Algorithm
Li Guo · Jisuanji gongcheng · 2009
Automaton is one kind of data structure often being used in string matching algorithms. By realizing compact representation of automaton,the algorithm space can be decreased. This paper summarizes several frequently used compact representations of automaton,analyzes their principles,time efficiencies,space efficiencies,merits and demerits,and gives relationships between above methods and sparsity character. It implements the basic AC algorithm with compact representation method. Experimental results of random and real data demonstrate the efficiency of this algorithm.