A variation of Aho-Corasick algorithm via compact storage was presented,which replaced homogeneous routine explicit storage with heterogeneous requirement oriented implicit one,first started from two aspects of widthwise fan-out compression and lengthwise path compression,then expanded around the compression of sparse event table,thus reduced memory usage to about 0.69% of original one when alphabet size σ=256,0.004% when σ=64K,and space complexity approximate (lbσ)/σ of origin.According to different degrees of fan-out,four kinds of specific fast event location methods were adopted,plus optimized failure transitions,led to the fact that the dramatic reduction of memory usage isn’t at the cost of obvious loss of speed,which was also proved by experiments.It’s suitable to be applied in the cases that need holding mass set of longer patterns and are sensitive to delay and jitter(for example,online data stream filtering),and presents distinguished superiority in wide-character(such as Asian character of UNICODE type) matching.
