A Parallel Aho-Corasick Algorithm with Non-deterministic Finite Automaton Based on OpenMP
Jiaxing Qu, Guoyin Zhang, Zhou Fang, Jiahui Liu, Xinyu Liu, Fangzhou Li · 2015
Existing typical algorithms of string matching are too difficult for taking advantage of multicore platforms. OpenMP (Open Multi-Processing) supports multiprocessing application programming interface with shared memory. We introduce a parallel Aho-Corasick algorithm based on OpenMP for shared memory, which exploits the non-deterministic finite automaton with space efficient for larger patterns. The experimental results show that the throughput can be achieved up to 7.5 Gbps on the average with 10000 patterns. The parallel algorithm would be successfully applied to data-intensive applications.