A Graphics Processing Unit Based Multi-String Matching Algorithm

摘要

String matching is a fundamental problem in computer science. It plays an important role in search engine, virus detection, sequence alignment and many other applications. Aho-Corasick (AC) algorithm is a widely used multi-string matching algorithm. In this paper, we present a space compacting method for AC automata based on node grouping and implement AC algorithm on GPU platform using CUDA (Computer Unified Device Architecture). In several experiments we conduct, our multi-string algorithm archives at least 10 times of speedup of the algorithm on CPUs.