《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 模拟设计 > 设计应用 > ɑFA：一种基于非信任字符比较的高性能正则表达式匹配算法
ɑFA：一种基于非信任字符比较的高性能正则表达式匹配算法
电子技术应用
杨嘉佳，关健，于增明，张雷，姚旺君
中国电子信息产业集团有限公司第六研究所
摘要： 正则表达式匹配技术在数据治理、解析提取和深度包检测方面有着重大应用价值。然而，由于其在通用平台上的匹配性能较低，无法满足实际环境下数据实时处理的应用需求，限制了其在高性能数据处理领域的应用范围。针对当前正则表达式匹配性能较低的问题，提出一种基于非信任字符比较的高性能正则表达式匹配算法，称之为ɑFA。该算法通过每次判断连续的若干个字符是否属于最常被访问状态的非信任字符集，获取无需通过DFA匹配可直接跳过的字符数，减少字符匹配过程中访问内存DFA状态转移表的次数，从而实现字符匹配的加速处理。实验结果表明，ɑFA算法可获得相比于原始DFA匹配算法约为1.05~7.58倍的性能加速比。
中圖分類(lèi)號(hào)：TP391.1 文獻(xiàn)標(biāo)志碼：A DOI: 10.16157/j.issn.0258-7998.244911
中文引用格式： 楊嘉佳，關(guān)健，于增明，等. ɑFA:一種基于非信任字符比較的高性能正則表達(dá)式匹配算法[J]. 電子技術(shù)應(yīng)用，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

引言

正則表達(dá)式因擁有強(qiáng)大的表達(dá)能力與靈活性，在數(shù)據(jù)治理、解析提取和深度包檢測(cè)方面得到了廣泛應(yīng)用。比如著名的搜索工具grep、sed以及入侵檢測(cè)系統(tǒng)Snort[1]都包含了很多正則表達(dá)式規(guī)則。

正則表達(dá)式匹配方法通常分為基于確定型有限自動(dòng)機(jī)(Deterministic Finite Automata, DFA)和基于非確定型有限自動(dòng)機(jī)(Nondeterministic Finite Automata, NFA)[2]。兩者的區(qū)別在于NFA的空間需求較少，但匹配性能較低；DFA則相反，匹配性能較高，但空間需求大。

在真實(shí)數(shù)據(jù)處理環(huán)境背景下，正則表達(dá)式的匹配性能是最重要的衡量因素之一。以狀態(tài)轉(zhuǎn)移次數(shù)計(jì)算，DFA匹配單個(gè)字符時(shí)發(fā)生一次狀態(tài)轉(zhuǎn)移，轉(zhuǎn)移次數(shù)固定，性能較高且較為穩(wěn)定；相反，NFA匹配單個(gè)字符時(shí)可能會(huì)引發(fā)若干次狀態(tài)轉(zhuǎn)移，轉(zhuǎn)移次數(shù)較多，性能較低且穩(wěn)定性較差。因此，現(xiàn)有的高性能匹配研究工作主要集中于如何提升DFA的匹配性能。

截止目前，各式各樣的DFA加速匹配方法已被提出[3]，包括經(jīng)典的多步長(zhǎng)自動(dòng)機(jī)、多核平臺(tái)并行匹配加速、基于枚舉方法的SIMD加速、基于推測(cè)與枚舉方法相結(jié)合的新型并行化匹配方法等。但是，這些算法在加速匹配過(guò)程中需多次訪問(wèn)內(nèi)存導(dǎo)致較大的時(shí)間開(kāi)銷(xiāo)，因而性能還有進(jìn)一步提升的空間。

因此，本文專(zhuān)注于DFA的匹配性能問(wèn)題，提出了一種基于非信任字符比較的高性能正則表達(dá)式匹配算法。通過(guò)每次判斷連續(xù)的若干個(gè)字符是否屬于最常被訪問(wèn)狀態(tài)的非信任字符集，獲得無(wú)需通過(guò)DFA匹配可直接跳過(guò)的字符數(shù)，從而實(shí)現(xiàn)DFA的加速處理。理論分析與實(shí)驗(yàn)結(jié)果表明，此算法可達(dá)到原始DFA性能加速比的1.05~7.58倍。


本文詳細(xì)內(nèi)容請(qǐng)下載：

http://ihrv.cn/resource/share/2000006031


作者信息：

楊嘉佳，關(guān)健，于增明，張雷，姚旺君

（中國(guó)電子信息產(chǎn)業(yè)集團(tuán)有限公司第六研究所，北京 100083）


Magazine.Subscription.jpg

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。

相關(guān)內(nèi)容