引言
作为大数据处理的重要技术手段之一，正则表达式（以下简称“正则”）因其强大的描述表达能力，在复杂数据的扫描处理中扮演重要角色。在人工智能时代背景下，正则表达式可以用于数据数据清洗、数据检索等应用场景。此外，较为典型的应用还包括：基于正则表达式实现系统日志的特征提取、入侵检测系统配置正则表达式实现网络流量的深度检测预警，以及利用正则表达式进行基因组序列数据的发现等。
当前，正则表达式的主流实现可分为非确定型有限自动机(Nondeterministic Finite Automata, NFA)[1]和确定型有限自动机(Deterministic Finite Automata, DFA)两种方式[2]。假设模式长度为m，那么NFA的空间复杂度仅为线性级，但最坏情况下的时间复杂度可能为指数级。而DFA通过状态转移保证处理一个字符只消耗一次状态转移，却有可能面临着状态空间爆炸问题。
实际上，在大数据和人工智能时代，一次状态转移只消耗一个字符的性能已远无法满足大规模数据处理的性能需求。因此，如何提高DFA的匹配性能成为了本文研究的重点。为提高DFA的匹配性能，本文提出一种基于可信区域的高性能正则表达式数据加速匹配算法：通过将DFA状态转移表划分出最优信任区域减少非信任列的数量，同时利用输入字符与非信任列在指令层级的比对，最大限度获得可略过的字符数，减少内存访问的次数。
本文详细内容请下载：
https://www.chinaaet.com/resource/share/2000007046
作者信息：
杨嘉佳
（中国电子信息产业集团有限公司第六研究所，北京 100083）
