SIMD Implementation of the Aho-Corasick Algorithm using Intel AVX2


Lazhar Ourlis
Djamel Bellala


The Aho-Corasick (AC) algorithm is a multiple pattern exact string-matching algorithm proposed by Alfred V. Aho and Margaret J. Corasick. It is used to locate all occurrences of a finite set of patterns within an input text simultaneously. The AC algorithm is in the heart of many applications including digital forensics such as digital signatures demonstrating the authenticity of a digital message or document, full text search (utility programs such as grep, awk and sed of Unix systems), information retrieval (biological sequence analysis and gene identification), intrusion detection systems (IDS) in computer networks like SNORT, web filtering, spam filters, and antimalware solutions (virus scanner). In this paper we present a vectorized version of the AC algorithm designed with the use of packed instructions based on the Intelīƒ’ streaming SIMD (Single Instruction Multiple Data) extensions AVX2 (Advanced Vector Extensions 2.0) technology. This paper shows that the vectorized AC algorithm reduces significantly the time matching process comparing to the implementation of the original AC algorithm.


Research Reports
Author Biography

Djamel Bellala, University of Batna 2, Algeria

Bellala Djamel is a University Professor "Department of Computer Science" with the University of Batna 2, Algeria, where he taught and conducted research in operation research. His several international articles have special focus on optimization of industrial systems with metaheuristic implementations.