av在线免费一区,日韩一区二区久久久,精品亚洲第一

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

電子技術(shù)應(yīng)用

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

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

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

關(guān)鍵詞： 正則表達(dá)式匹配確定型有限自動(dòng)機(jī) 高性能數(shù)據(jù)處理

中圖分類號(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)銷，因而性能還有進(jì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://www.jysgc.com/resource/share/2000006031

作者信息：

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

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

Magazine.Subscription.jpg

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

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