Name
Title | ||
|---|---|---|
An efficient multicharacter transition string-matching engine based on the aho-corasick algorithm |
Abstract | ||
|---|---|---|
A string-matching engine capable of inspecting multiple characters in parallel can multiply the throughput. However, the space required for implementing a matching engine that can process multiple characters in parallel generally grows exponentially with respect to the characters to be processed in parallel. Based on the Aho-Corasick algorithm (AC-algorithm), this work presents a novel multicharacter transition Nondeterministic Finite Automaton (NFA) approach, called multicharacter AC-NFA, to allow for the inspection of multiple characters in parallel. This approach first converts an AC-trie to an AC-NFA by allowing for the simultaneous activation of multiple states and then converts the AC-NFA to a k-character AC-NFA by an algorithm with concatenation operations and assistant transitions. Additionally, the alignment problem, which occurs while multiple characters are being inspected in parallel, is solved using assistant transitions. Moreover, a corresponding output is provided for each inspected character by introducing priority multiplexers to determine the final matching outputs during implementation of the multicharacter AC-NFA. Consequently, the number of derived k-character transitions grows linearly with respect to the number k. Furthermore, the derived multicharacter AC-NFA is implemented on FPGAs for evaluation. The resulting throughput grows approximately 14 times and the hardware cost grows about 18 times for 16-character AC-NFA implementation, as compared with that for 1-character AC-NFA implementation. The achievable throughput is 21.4Gbps for the 16-character AC-NFA implementation operating at a 167.36MHz clock. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2541228.2541232 | TACO |
Keywords | Field | DocType |
efficient multicharacter transition,multicharacter ac-nfa,k-character ac-nfa,1-character ac-nfa implementation,16-character ac-nfa implementation,achievable throughput,multiple state,aho-corasick algorithm,novel multicharacter transition nondeterministic,16-character ac-nfa implementation operating,assistant transition,multiple character,string matching,intrusion detection system | String searching algorithm,Nondeterministic finite automaton,Computer science,Parallel computing,Field-programmable gate array,Algorithm,Multiplexer,Concatenation,Throughput,Intrusion detection system,Exponential growth | Journal |
Volume | Issue | ISSN |
10 | 4 | 1544-3566 |
Citations | PageRank | References |
7 | 0.46 | 25 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chien-Chi Chen | 1 | 21 | 3.33 |
| Sheng-De Wang | 2 | 720 | 68.13 |