An Optimized Aho-Corasick Multi-Pattern Matching Algorithm for Fast Pattern Matching
Uday Trivedi · 2020
Multi-pattern search is a critical task in many domains like DPI, NIDS, firewall and big data analytics. Aho-Corasick algorithm (AC) is one of the best multi-pattern search algorithms with linear complexity. Our goal is to optimize AC algorithm to reduce search time for multi-pattern match. Our optimized algorithm constructs AC DFA graph by adding up to K patterns for each input pattern and searches modified AC DFA by using every Kth bytes from input search text and skipping adjoining K-1 bytes. Here K is optimization factor. Our algorithm complexity is in order of n/K with input size n. Our algorithm requires less memory to construct optimized AC DFA compared to original AC DFA graph. Depending on number of patterns added in AC DFA, the evaluation results show 30-45% search performance gain for K = 2. With higher optimization factor, search performance gain close to 40-60% is achieved.