Advertisement
Published in:
2015 | OriginalPaper | Chapter
A Failureless Pipelined Aho-Corasick Algorithm for FPGA-based Parallel String Matching Engine
Author : Hyun Jin Kim
Published in: Information Science and Applications
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper proposes a failureless pipelined Aho-Corasick (FPAC) algorithm that generates the failureless pipelined deterministic-finite automaton (DFA). The failureless pipelined DFA generated by the FPAC algorithm does not store the failure pointers for reducing hardware overhead. Moreover, by sharing common prefixes, the information for storing states can be compressed. Because the pipeline register stores the state in each stage, the failureless pipelined DFA can perform multiple state transitions in parallel. Therefore, throughput can be increased with multiple homogeneous DFAs. In the experiments with cost-effective FPGAs, the implementation of the proposed FPAC algorithm shows high performance and low hardware overhead compared to several FPGA-based string matching engines.