《電子技術(shù)應(yīng)用》
您所在的位置：首頁 > 模擬設(shè)計(jì) > 設(shè)計(jì)應(yīng)用 > ɑFA：一種基于非信任字符比較的高性能正則表達(dá)式匹配算法
ɑFA：一種基于非信任字符比較的高性能正則表達(dá)式匹配算法
電子技術(shù)應(yīng)用
楊嘉佳，關(guān)健，于增明，張雷，姚旺君
中國電子信息產(chǎn)業(yè)集團(tuán)有限公司第六研究所
摘要： 正則表達(dá)式匹配技術(shù)在數(shù)據(jù)治理、解析提取和深度包檢測方面有著重大應(yīng)用價(jià)值。然而，由于其在通用平臺上的匹配性能較低，無法滿足實(shí)際環(huán)境下數(shù)據(jù)實(shí)時(shí)處理的應(yīng)用需求，限制了其在高性能數(shù)據(jù)處理領(lǐng)域的應(yīng)用范圍。針對當(dāng)前正則表達(dá)式匹配性能較低的問題，提出一種基于非信任字符比較的高性能正則表達(dá)式匹配算法，稱之為ɑFA。該算法通過每次判斷連續(xù)的若干個(gè)字符是否屬于最常被訪問狀態(tài)的非信任字符集，獲取無需通過DFA匹配可直接跳過的字符數(shù)，減少字符匹配過程中訪問內(nèi)存DFA狀態(tài)轉(zhuǎn)移表的次數(shù)，從而實(shí)現(xiàn)字符匹配的加速處理。實(shí)驗(yàn)結(jié)果表明，ɑFA算法可獲得相比于原始DFA匹配算法約為1.05~7.58倍的性能加速比。
中圖分類號：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ù)治理、解析提取和深度包檢測方面得到了廣泛應(yīng)用。比如著名的搜索工具grep、sed以及入侵檢測系統(tǒng)Snort[1]都包含了很多正則表達(dá)式規(guī)則。

正則表達(dá)式匹配方法通常分為基于確定型有限自動機(jī)(Deterministic Finite Automata, DFA)和基于非確定型有限自動機(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í)可能會引發(fā)若干次狀態(tài)轉(zhuǎn)移，轉(zhuǎn)移次數(shù)較多，性能較低且穩(wěn)定性較差。因此，現(xiàn)有的高性能匹配研究工作主要集中于如何提升DFA的匹配性能。

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

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


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

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


作者信息：

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

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


Magazine.Subscription.jpg

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