中圖分類號：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

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