具多字元狀態轉移之高效字串比對引擎

Abstract

由 Aho 和 Corasick 所提出的演算法 (簡稱 AC 演算法) 可以很有效率地在一段文字中搜尋多個關鍵字所在的位置，因而被廣泛地使用於完全字串比對。然而，AC 演算法在運作時，只能一次處理一個字元，因而其效能受限於運作時脈。本論文依據 AC 演算法，提出新穎的具有多字元狀態轉移之字串比對架構，可以平行檢視多個字元，藉以加倍提升字串比對的效能。首先，說明實作 AC 演算法的三種有限自動機（finite automaton，簡稱 FA）的作法，包括確定性有限自動機 (Deterministic Finite Automaton，簡稱 DFA)、非確定有限自動機 (Nondeterministic Finite Automaton，簡稱 NFA)、以及複合有限自動機 (Hybrid Finite Automaton，簡稱 hybrid FA) 的作法。接著，提出一種推導演算法，藉以將前述 FA 推導為多字元的 FA，使其能夠平行檢視多個字元。同時，因為平行檢視多個字元所引起的對齊問題 (alignment problem)，也藉由輔助轉移函式 (assistant transition) 來解決。所推導的多字元 FA 使用可程式元件來評估，所得到的評估結果顯示其能有效地加倍提升字串比對的效能。其中所得到的最佳結果為 16字元 AC-NFA 的實作，其可運作於 167.36MHz 的時脈，換算得到的字串比對效能為 21.4Gbps。

The algorithm of Aho and Corasick (AC-algorithm) can locate multiple keywords in a text efficiently; and thus it is widely used in the exact string matching. However, the AC-algorithm processes the text character by character with a performance limited by the processing clock. This thesis proposes novel string-matching architectures with multiple-character state transitions based on the AC-algorithm, which can inspect multiple characters in parallel to multiply the throughput. At first, three finite automaton (FA) approaches including Deterministic Finite Automaton (DFA), Nondeterministic Finite Automaton (NFA), and hybrid FA approaches are presented to implement the AC-algorithm. Subsequently, a derivation algorithm is proposed to derive these FAs to multi-character FAs to allow for the inspection of multiple characters in parallel. Additionally, the alignment problem, which occurs while multiple characters are being inspected in parallel, is solved by using assistant transitions. The derived multi-character FAs are evaluated on programmable devices and the evaluation results indicate that the throughput can be multiplied effectively. The achievable throughput of the best result is 21.4Gbps obtained by a 16-character AC-NFA implementation operating at a 167.36MHz clock.