中圖分類號：TP391.1 文獻(xiàn)標(biāo)志碼：A DOI: 10.16157/j.issn.0258-7998.245321
中文引用格式： 楊嘉佳，李正，鄭兒，等. 一種基于狀態(tài)預(yù)測的多線程數(shù)據(jù)過濾算法[J]. 電子技術(shù)應(yīng)用，2024，50(12)：87-91.
英文引用格式： Yang Jiajia，Li Zheng，Zheng Er，et al. An accelerated regular expression matching algorithm based on multi-threading and state prediction[J]. Application of Electronic Technique，2024，50(12)：87-91.

An accelerated regular expression matching algorithm based on multi-threading and state prediction

Abstract： Data filtering algorithms play a crucial role in the field of big data processing. Data filtering algorithms based on regular expression matching technology are suitable for processing large-scale complex data due to their powerful feature expression capabilities. However, the traditional regular expression matching process is serial matching, resulting in low performance that cannot meet the needs of modern data processing. To address the issue of low performance in traditional regular expression matching, an accelerated regular expression matching algorithm based on multithreading and state prediction is proposed, named μFA. This algorithm performs character value comparison based on vector instructions to obtain the number of trusted characters that can be skipped directly. Simultaneously, it utilizes multithreading acceleration and state prediction techniques to achieve segmented matching processing of strings. By delimiting dangerous character regions, it determines the correctness of the final matching results for each segment. Experimental results show that the throughput is 10.12 to 91.36 times higher than the original DFA algorithm and 1.08 to 2.97 times higher than the ßFA algorithm.

Key words : regular expression matching；state prediction；data filtering