引言
数据处理能力是大数据时代的核心要素之一，决定了真实数据环境下是否满足数据线速处理的要求。正则表达式匹配技术可作为数据清洗、提取解析和数据检测等数据处理任务的有效解决手段之一。例如，基于Linux系统的Awk、Vim、Perl工具以及开源网络入侵检测系统Bro IDS[1]等都使用了正则表达式的匹配功能。
正则表达式匹配的有效手段通常分为确定型有限自动机(Deterministic Finite Automata, DFA)和基于非确定型有限自动机(Nondeterministic Finite Automata, NFA)[2]。两者各有其特点，NFA空间复杂性较低，但因为一次字符输入可能会引发数目不定的多个状态转移，造成匹配时间复杂性较大。相反，原始DFA的时间复杂性低且为O(1)，但存在空间开销大的问题。
在大数据处理背景下，正则表达式的匹配性能是最重要的衡量因素，因此DFA成为解决匹配性能方案的首选。针对DFA空间开销大的问题，现已存在很多优秀的研究成果[3]。然而，DFA匹配过程中存在数据强依赖关系，造成其不能很好地适用于高性能数据处理环境。
因此，针对DFA匹配性能较低的问题，本文利用Intel的向量指令集对DFA匹配进行加速。通过一次性读入若干连续字符，然后并行判断其是否属于最常被访问状态的非信任字符集，获取无需访问内存状态转移表即可直接跳过的字符数，从而减少匹配时间的消耗以达到性能加速目的。
本文详细内容请下载：
https://www.chinaaet.com/resource/share/2000006215
作者信息：
杨嘉佳，关健，李正，于增明，姚旺君
（中国电子信息产业集团有限公司第六研究所，北京 100083）
