中文引用格式： 楊嘉佳，關健，于增明，等. ɑFA:一種基于非信任字符比較的高性能正則表達式匹配算法[J]. 電子技術應用，2024，50(6)：57-60.
英文引用格式： Yang Jiajia，Guan Jian，Yu Zengming，et al. ɑFA: a high-performance regular expression matching algorithm based on untrusted character comparison[J]. Application of Electronic Technique，2024，50(6)：57-60.
引言
正則表達式因擁有強大的表達能力與靈活性，在數據治理、解析提取和深度包檢測方面得到了廣泛應用。比如著名的搜索工具grep、sed以及入侵檢測系統Snort[1]都包含了很多正則表達式規則。
正則表達式匹配方法通常分為基于確定型有限自動機(Deterministic Finite Automata, DFA)和基于非確定型有限自動機(Nondeterministic Finite Automata, NFA)[2]。兩者的區別在于NFA的空間需求較少，但匹配性能較低；DFA則相反，匹配性能較高，但空間需求大。
在真實數據處理環境背景下，正則表達式的匹配性能是最重要的衡量因素之一。以狀態轉移次數計算，DFA匹配單個字符時發生一次狀態轉移，轉移次數固定，性能較高且較為穩定；相反，NFA匹配單個字符時可能會引發若干次狀態轉移，轉移次數較多，性能較低且穩定性較差。因此，現有的高性能匹配研究工作主要集中于如何提升DFA的匹配性能。
截止目前，各式各樣的DFA加速匹配方法已被提出[3]，包括經典的多步長自動機、多核平臺并行匹配加速、基于枚舉方法的SIMD加速、基于推測與枚舉方法相結合的新型并行化匹配方法等。但是，這些算法在加速匹配過程中需多次訪問內存導致較大的時間開銷，因而性能還有進一步提升的空間。
因此，本文專注于DFA的匹配性能問題，提出了一種基于非信任字符比較的高性能正則表達式匹配算法。通過每次判斷連續的若干個字符是否屬于最常被訪問狀態的非信任字符集，獲得無需通過DFA匹配可直接跳過的字符數，從而實現DFA的加速處理。理論分析與實驗結果表明，此算法可達到原始DFA性能加速比的1.05~7.58倍。
本文詳細內容請下載：
http://www.shi-ke.cn/resource/share/2000006031
作者信息：
楊嘉佳，關健，于增明，張雷，姚旺君
（中國電子信息產業集團有限公司第六研究所，北京 100083）
