国际完美世界下载,大主宰之灵路天蚕土豆,女人书籍排行榜

ɑFA：一種基于非信任字符比較的高性能正則表達式匹配算法

電子技術應用

楊嘉佳，關健，于增明，張雷，姚旺君

中國電子信息產業集團有限公司第六研究所

摘要： 正則表達式匹配技術在數據治理、解析提取和深度包檢測方面有著重大應用價值。然而，由于其在通用平臺上的匹配性能較低，無法滿足實際環境下數據實時處理的應用需求，限制了其在高性能數據處理領域的應用范圍。針對當前正則表達式匹配性能較低的問題，提出一種基于非信任字符比較的高性能正則表達式匹配算法，稱之為ɑFA。該算法通過每次判斷連續的若干個字符是否屬于最常被訪問狀態的非信任字符集，獲取無需通過DFA匹配可直接跳過的字符數，減少字符匹配過程中訪問內存DFA狀態轉移表的次數，從而實現字符匹配的加速處理。實驗結果表明，ɑFA算法可獲得相比于原始DFA匹配算法約為1.05~7.58倍的性能加速比。

關鍵詞： 正則表達式匹配確定型有限自動機高性能數據處理

中圖分類號：TP391.1 文獻標志碼：A DOI: 10.16157/j.issn.0258-7998.244911
中文引用格式： 楊嘉佳，關健，于增明，等. ɑ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.

ɑFA： a high-performance regular expression matching algorithm based on untrusted character comparison

Yang Jiajia，Guan Jian，Yu Zengming，Zhang Lei，Yao Wangjun

The Sixth Research Institute of China Electronics Corporation

Abstract： Regular expression matching technology has significant application value in data governance, parsing extraction, and deep packet inspection. However, due to its low matching performance on general-purpose platforms, it cannot meet the application requirements of real-time data processing in practical environments, which limits its application scope in the field of high-performance data processing. In response to the current issue, a high-performance regular expression matching algorithm based on untrusted character comparison is proposed, which is called ɑFA. This algorithm determines whether a sequence of consecutive characters belongs to the untrusted character set of the most frequently accessed state. By doing so, it acquires the number of characters that can be skipped directly without DFA matching, reduces the number of accesses to the DFA state transition table in memory during character matching, and thus achieves accelerated processing of character matching. The experimental results indicate that the ɑFA algorithm can achieve a performance acceleration of approximately 1.05 times to 7.58 times compared to the original DFA matching algorithm.

Key words : regular expression matching；deterministic finite automaton；high-performance data processing

引言

正則表達式因擁有強大的表達能力與靈活性，在數據治理、解析提取和深度包檢測方面得到了廣泛應用。比如著名的搜索工具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.viuna.cn/resource/share/2000006031

作者信息：

楊嘉佳，關健，于增明，張雷，姚旺君

（中國電子信息產業集團有限公司第六研究所，北京 100083）

Magazine.Subscription.jpg

原創聲明：此內容為AET網站原創，未經授權禁止轉載。

相關內容