YJJFA：一种数据驱动的高性能正则表达式匹配算法
电子技术应用
杨嘉佳
中国电子信息产业集团有限公司第六研究所
摘要： 正则表达式匹配技术在人工智能时代背景下扮演着重要角色，尤其在数据清洗与数据抽取领域，可为大语言模型训练所需的高质量数据处理提供技术支撑。然而，传统正则表达式匹配算法存在性能瓶颈，限制了其应用范围。针对此问题，提出一种基于可信区域的高性能正则表达式匹配算法，命名为YJJFA算法。该算法通过对状态转移表划分成最优可信区域与非信任区域，减少需要处理的状态转移表输入字符数量，并借助非内存访问的非信任字符集向量比较以实现信任字符低时间消耗处理。实验结果表明，YJJFA算法在L7filter规则上的吞吐率达17.88~53.81Gb/s，较原始DFA算法性能提升了一个数量级。
中图分类号：TP391.1 文献标志码：A DOI: 10.16157/j.issn.0258-7998.256942
中文引用格式： 杨嘉佳. YJJFA：一种数据驱动的高性能正则表达式匹配算法[J]. 电子技术应用，2026，52(4)：102-107.
英文引用格式： Yang Jiajia. YJJFA: a data-driven high-performance regular expression matching algorithm[J]. Application of Electronic Technique，2026，52(4)：102-107.
中文引用格式： 杨嘉佳. YJJFA：一种数据驱动的高性能正则表达式匹配算法[J]. 电子技术应用，2026，52(4)：102-107.
英文引用格式： Yang Jiajia. YJJFA: a data-driven high-performance regular expression matching algorithm[J]. Application of Electronic Technique，2026，52(4)：102-107.
YJJFA： a data-driven high-performance regular expression matching algorithm
Yang Jiajia
The Sixth Research Institute of China Electronics Corporation
Abstract： Under the background of the artificial intelligence era, regular expression matching technology plays a crucial role, particularly in data cleansing and data extraction domains, where it provides technical support for high-quality data processing required by large language model training. However, traditional regular expression matching algorithms suffer from performance bottlenecks that limit their application scope. To address this challenge, this paper proposes a data-driven high-performance regular expression matching algorithm, denoted as YJJFA algorithm. The algorithm reduces the number of input characters that need to be processed in the state transition table by partitioning it into optimal trusted regions and untrusted regions, while leveraging non-memory-access vector comparisons of the untrusted character set (UBCS) to achieve low-time-cost processing of trusted characters. Experimental results show that the YJJFA algorithm achieves a throughput rate of 17.88~53.81 Gb/s on L7filter rules, representing an order-of-magnitude performance improvement over conventional DFA implementations.
Key words : regular expression matching；trusted zones；high-performance；data cleansing
引言
作为大数据处理的重要技术手段之一，正则表达式（以下简称“正则”）因其强大的描述表达能力，在复杂数据的扫描处理中扮演重要角色。在人工智能时代背景下，正则表达式可以用于数据数据清洗、数据检索等应用场景。此外，较为典型的应用还包括：基于正则表达式实现系统日志的特征提取、入侵检测系统配置正则表达式实现网络流量的深度检测预警，以及利用正则表达式进行基因组序列数据的发现等。
当前，正则表达式的主流实现可分为非确定型有限自动机(Nondeterministic Finite Automata, NFA)[1]和确定型有限自动机(Deterministic Finite Automata, DFA)两种方式[2]。假设模式长度为m，那么NFA的空间复杂度仅为线性级，但最坏情况下的时间复杂度可能为指数级。而DFA通过状态转移保证处理一个字符只消耗一次状态转移，却有可能面临着状态空间爆炸问题。
实际上，在大数据和人工智能时代，一次状态转移只消耗一个字符的性能已远无法满足大规模数据处理的性能需求。因此，如何提高DFA的匹配性能成为了本文研究的重点。为提高DFA的匹配性能，本文提出一种基于可信区域的高性能正则表达式数据加速匹配算法：通过将DFA状态转移表划分出最优信任区域减少非信任列的数量，同时利用输入字符与非信任列在指令层级的比对，最大限度获得可略过的字符数，减少内存访问的次数。
本文详细内容请下载：
https://www.chinaaet.com/resource/share/2000007046
作者信息：
杨嘉佳
（中国电子信息产业集团有限公司第六研究所，北京 100083）
此内容为AET网站原创，未经授权禁止转载。