一種基于狀態預測的多線程數據過濾算法
電子技術應用
楊嘉佳，李正，鄭兒，姚旺君，趙靜，關健
中國電子信息產業集團有限公司第六研究所
摘要： 數據過濾算法在大數據處理領域有著重要的作用。基于正則表達式匹配技術的數據過濾算法憑借強大的特征表達能力適合于處理大規模復雜數據。然而，傳統的正則表達式匹配過程為串行匹配，造成性能低，無法滿足現代數據處理的需求。針對傳統正則表達式匹配性能低的問題，提出一種基于多線程和狀態預測的正則表達式加速匹配算法，稱之為μFA：基于向量指令執行字符值比較，獲取可直接跳過的信任字符數。同時，基于多線程加速和狀態猜測技術，實現字符串的分段匹配處理，通過圈定字符危險區域，研判各分段最終匹配結果的正確性。實驗結果表明，μFA算法的吞吐率是原始DFA算法的10.12~91.36倍、ßFA算法的1.08~2.97倍。
中圖分類號：TP391.1 文獻標志碼：A DOI: 10.16157/j.issn.0258-7998.245321
中文引用格式： 楊嘉佳，李正，鄭兒，等. 一種基于狀態預測的多線程數據過濾算法[J]. 電子技術應用，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.
中文引用格式： 楊嘉佳，李正，鄭兒，等. 一種基于狀態預測的多線程數據過濾算法[J]. 電子技術應用，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
Yang Jiajia，Li Zheng，Zheng Er，Yao Wangjun，Zhao Jing，Guan Jian
The Sixth Research Institute of China Electronics Corporation
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
引言
在人工智能時代[1]，正則表達式匹配技術有助于數據的預處理過濾，可為業務應用提供更高質量的數據。例如，正則表達式規則由于其展現出強大的表征能力，可從大規模數據中過濾出復雜且符合深度學習模型要求的數據，提升模型的推理精度。
數據預處理吞吐率是衡量過濾算法的重要性能因素之一，反映出在特定環境下算法可以運行的性能極限，決定其是否適用于高性能大數據預處理領域。因此，本文重點研究如何提高基于正則表達式匹配的數據過濾性能。
當前，已涌現出許多優秀的基于正則表達式技術的數據過濾算法[2]，包括基于非確定型有限自動機(Nondeterministic Finite Automata, NFA)、基于確定型有限自動機(Deterministic Finite Automata, DFA)和基于混合自動機(Hybrid Finite Automata, Hybrid-FA)等實現方式。其中，因DFA的數據過濾性能較為穩定，備受研究人員和開發人員的青睞。
然而，現有的正則表達式過濾算法性能較低，無法滿足大數據背景下的高性能過濾需求。因此，本文提出一種基于狀態預測的多線程數據過濾算法：通過向量指令字符值比較、多線程加速、狀態猜測等技術，實現字符串的分段匹配處理，從而提高算法的吞吐率。
本文詳細內容請下載：
http://www.rjjo.cn/resource/share/2000006254
作者信息：
楊嘉佳，李正，鄭兒，姚旺君，趙靜，關健
（中國電子信息產業集團有限公司第六研究所，北京 100083）
此內容為AET網站原創，未經授權禁止轉載。