基于多维有限自动机的DFA改进算法

多个正则表达式规则编译成一个DFA(deter minister finite automata)时,会产生状态爆炸、存储急剧增加的现象。针对最严重的状态爆炸问题,从信息论的角度给出了解释,并提出多维数学模型,将冗余状态分为0维状态和1维状态,通过前者按照维度压缩,后者动态构建的方法将空间复杂度降到理论下界,并在此基础上提出多维有限自动机(MFA, multi-dimensional finite automata)。实验表明,MFA构造时间比XFA略少,比DFA、STT冗余压缩算法和Hybrid-FA降低了2~3个数量级;存储空间比XFA略高,比DFA、STT冗余压缩算法、mDFA、Hybrid-FA降低了1~2个数量级;匹配时间比DFA、Hybrid-FA略多,但是比XFA略少,比STT冗余压缩算法和mDFA降低了1~2个数量级。     

基于两级存储的正则表达式匹配技术

为解决正则表达式匹配中内存需求与检测性能的矛盾,首次提出两级存储的匹配方案。将马尔可夫链理论应用于自动机,通过求解稳态向量,得到各状态被随机访问的概率。将高概率的状态表项配置在FPGA嵌入存储器中,低概率的状态表项配置在SRAM中。使用L7-filter规则集进行实验,吞吐量达到33Gbit/s,匹配性能比将状态表完全存储在SRAM中提高了50倍。     

基于Cppcheck的嵌入式静态代码扫描工具应用和规则扩充

嵌入式软件开发过程中代码规范非常重要,为加速研发效率,提前发现代码问题,合理使用嵌入式静态代码扫描工具十分重要。首先阐述嵌入式静态代码扫描的相关概念和特点;其次详细介绍了Cppcheck嵌入式静态代码扫描工具的使用和结果分析,并对比其他同类工具;然后详细说明Cppcheck缺陷扫描规则和扩充实践;最后结合Jenkins进行自动化代码扫描和分析。使用Cppcheck并自定义缺陷规则到结合自动化工具,从而使嵌入式代码静态扫描工作能够高效快捷地完成。     

正则语言推断综述

正则语言推断研究从语言的有限信息出发,通过归纳和推理得出正则语言模型.该技术在信息抽取、软件工程、模式识别等领域应用广泛.本文首先阐明了语言的可学习性概念和推断结果的评价准则.然后从推理策略、数据结构、算法复杂性等方面,对被动、主动和基于神经网络的学习算法进行分类归纳与对比,梳理各流派的技术发展脉络.接着分析推断产生的三种泛化效应.最后指出当前研究中不足,对未来研究方向进行展望.     

基于硬件的快速正则表达式匹配方法

网络应用中基于正则表达式特殊模式识别技术是比较新颖的一门学科。基于NFA的方法速率较慢，而基于DFA的执行算法会耗费大量的存储空间。文中提出一种分组模式处理方法，将序列庞大的正则表达式编译为少量的DFA，然后利用多核处理器来并行地处理分组模式，在不明显增加内存耗费的情形之下增加了正则表达式的匹配速率。     

正则表达式在Oracle中的应用与实现

首先介绍Oracle 10g中增加的新功能及正则表达式的发展,给出了正则表达式的定义以及其用途,分析了Oracle中各个字符元的含义,并结合具体的查询实例详细说明了正则表达式在Oracle中的应用。     

基于正则表达式的话务报告处理软件的实现

介绍了本地交换网管话务报告处理软件系统国内外应用现状，重点阐述了基于正则表达式的交换网管话务报告处理软件的实现过程。     

Fuzzy正则表达式与Fuzzy有限态自动机的关系

首先给出了Fuzzy正则表达式的定义,接着通过研究Fuzzy正则表达式与Fuzzy有限态自动机的关系,得到了两个重要性质,即：每一个Fuzzy正则表达式,都有一个非确定性的Fuzzy有限态自动机接受其代表的语言;每一个被确定性的Fuzzy有限态自动机接受的语言,都能被一个Fuzzy正则表达式表示．     

一种基于FPGA压缩DFA的高速正则表达式匹配算法

正则表达式匹配技术在网络应用中面临两方面的制约,一方面,复杂或大规模规则导致DFA存储空间急剧膨胀,现有的内存容量难以支撑;另一方面,传统计算机架构的DFA处理能力有限,很难满足高速网络流的线速处理需求。因此,提出一种基于FPGA使用改进游程编码压缩DFA的高速正则表达式匹配算法。实现了基于改进游程编码的DFA引擎架构、分组存储与多路并行比较器技术。该算法不仅具有游程编码的压缩效果,而且压缩后的DFA实现一次状态转移只需2个时钟周期。     

新颖的正则NFA引擎构造方法

提出了一种新颖的正则NFA引擎构造方法——PFA构造法。PFA构造法包括3个主要算法：预处理算法、解析树编码算法和基于编码树的NFA构造算法。采用PFA构造法能够构造出只含有一个开始状态和一个终止状态的规模更小的NFA,称其为NFAp。NFAp的规模与正则表达式组的长度线性相关,较Thompson自动机、后跟自动机、位置自动机以及部分派生自动机的规模都要小,是Thompson NFA的1/3,比已经接近最优的后跟自动机构造法所获得的NFA还要小。