国产精品美女久久久久av福利 ,欧美亚洲国产精品,国产精品亚洲二区在线观看

ɑ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.tom3567.com/resource/share/2000006031

作者信息：

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

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

Magazine.Subscription.jpg

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

相關內容