面向網絡流的自適應正則表達式分組匹配算法

杜文超　陳庶樵　胡宇翔

摘要：針對當前的多正則表達式匹配算法占用較大的系統資源，且吞吐量較低的問題，在分析典型的正則表達式匹配算法的基礎上，提出了一種自適應的多正則表達式分組匹配算法，該算法通過對正則表達式進行高效分組，將相互之間存在交疊且容易引起狀態數指數增長的表達式相互隔離；將每個分組構造為一個確定性有限自動機（DFA），按匹配概率大小建立伸展樹進行調度，仿真結果表明，該算法不僅大大節省了存儲空間，而且吞吐量提高了大約3倍。