引言
数据匹配技术可应用于数据的清洗和治理，如基于正则表达式的数据匹配技术在基础数据的过滤方面发挥重要作用，通过数据匹配可将无关数据剔除过滤，减少噪声数据的干扰。正则表达式因具有强大的表征能力，适合用于匹配过滤真实环境下的复杂噪声数据。例如，开源入侵检测系统Bro IDS、Snort[1]等都使用了基于正则表达式的数据匹配功能。
基于正则表达式的数据匹配实现方式通常可分成两种：基于非确定型有限自动机(NFA)和确定型有限自动机(DFA)。前者空间复杂度比较低，与正则表达式的长度呈线性关系，但因处理一个字符需激活多个状态，造成匹配时间复杂性较大和匹配性能不稳定。相比而言，DFA的时间复杂性比较低，处理一个字符只需一次激活单个状态，然而却因规则的复杂性易导致状态转移空间膨胀甚至“爆炸”，造成巨大的空间开销。
在大数据匹配环境中，DFA更多地被选择与应用。DFA的匹配性能和空间消耗是基于正则表达式数据匹配技术的重要衡量因素。截至目前，DFA的空间消耗已有很多可行的算法被提出[2]，因而不是本文研究重点。尽管已有若干算法对DFA的匹配性能进行研究，但性能低依旧是制约其广泛应用的瓶颈因素。
针对此问题，本文基于单指令多数据流(Single Instruction Multiple Data)向量指令连续从内存中读入若干字符段，然后分别与最常被访问状态（行）对应的非信任字符集进行字符并行比较操作，通过位置定位函数累加定位出首个非信任字符位置，获取直接略过的总字符数，减少访存次数，提高算法吞吐率。
本文详细内容请下载：
https://www.chinaaet.com/resource/share/2000006330
作者信息：
杨嘉佳，李正，郑儿，赵静，燕玮，刘金
（中国电子信息产业集团有限公司第六研究所，北京 100083）
