Space-time tradeoff in the Aho-Corasick string matching algorithm

The Aho-Corasick (AC) string matching algorithm is widely used in intrusion detection systems and anti-virus systems. The basic version consisting of the GOTO and failure functions is very memory efficient, but its processing speed is slow. On the other hand, the version with fully expanded transition rule table is much faster but it requires huge amount of memory space. In this article we study the space-time tradeoff in the AC algorithm. A transition rule table compression scheme based on transition edge elimination and perfect hashing is developed. The proposed method can reduce the size of the fully expanded transition rule table by a factor of 23 to 25, and the processing speed is 5 to 7.7 times the speed of the basic version.