Lookup table generation for Pipelined Aho-Corasick String-Matching Algorithm

Abstract

String matching algorithm is used to locate one or several certain strings or patterns in given texts, long strings or pattern sets. String matching algorithms are widely used in many areas, such as search engine and virus scanning. The Aho-Corasick (AC) algorithm [1] is a classical string matching algorithm. An advantage of the AC algorithm is that the matching time is linearly depended on the length of the input stream. A major limitation of AC algorithm is that the cost of physical memory used to store the transition rule tables is very high. Pipelined Aho-Corasick (P-AC) architecture [2] is a memory-efficient way to improve the AC algorithm and reduce the memory cost using a pipelined approach. The major task for the project is to develop the supporting software (C program) to generate the lookup tables of the system and finally apply the P-AC architecture into the QSV method [4] which is a memory efficient hardware string searching engine for anti-virus applications.