一种正则表达式集合快速搜索算法

正则表达式由于其强描述能力和灵活性,在信息检索,程序设计,数据挖掘,深度分组检测,生物信息处理等领域得到了广泛而深入的应用,然而正则表达式,尤其是正则表达式集合,由于搜索速度慢往往成为系统的性能瓶颈。现有的正则表达式搜索算法性能较好的是多模式过滤类型的算法,此类算法严重依赖于两个因素,从NFA的初始状态到终止状态的最短路径Lmin和正则表达式所表达的语言的前缀集合Pref（RE）的大小,Lmin越长,搜索速度越快,Pref（RE）越大,搜索速度越慢。针对上述问题提出了一种基于Bloom filter的正则表达式集合搜索算法,此方法利用Bloom filter的集合查询时间集合大小无关的特点,使得正则表达式搜索速度不受Pref（RE）大小的影响,如果采用多个Bloom filter并行,还可以间接增大Lmin的长度。分析与测试结果表明,本算法较大的加快了正则表达式的搜索速度,对于正则表达式集合,算法性能改善尤其明显,可以实现大规模正则表达式集合的快速搜索。     

支持多正则表达式匹配的硬件结构

针对多正则表达式匹配已经成为制约网络安全系统性能瓶颈的问题,提出一种硬件四级流水线的多正则表达式匹配结构。该结构对多条正则表达式统一处理,将正则表达式切割成字符串和循环控制,采用字符串匹配结构处理字符串,并设计专用硬件电路处理循环限制。实验表明,该硬件结构在Virtex2和Virtex4 FPGA上分别可以达到1.9和2.1Gb/s的匹配性能,与国外相关研究成果相比,消耗更少的存储空间,并支持更多的正则表达式。     

正则表达式在汉英对照中国文化术语抽取中应用

运用正则表达式的字符串匹配功能对特定数据库中的汉英对照中国文化术语进行了抽取.抽取过程中,由于规则中特殊字符有11个,正则表达式中的一个字符可能要经过11次才能判断与待搜索文本中对应字符是否匹配.为加快抽取速度,根据待搜索文本的实际情况,选择使用了3个元字符,建立了符合特定需要的正则表达式,在保证相同正确率的前提下,抽取速度提高了1倍左右;同时,通过正则表达式生成器,尝试解决了正则表达式应用过程中可读性差、用户使用难度大的问题.     

一种构造正则表达式更小ε-NFA的方法

基于有限自动机的正则表达式匹配技术在网络信息领域得到了广泛应用,提出了一种构造正则表达式的更小NFA的方法——基于闭包的分片构造法GREC.GREC方法基于正则表达式中同态运算的封闭性以及闭包运算的层次特性和递归性进行构造.首先对正则表达式进行分片处理,然后构造每个分片的NFA,最后利用栈对各分片NFA进行重组获得最终的NFA.GREC方法在正则表达式层次结构复杂或包含有大量闭包运算的情况下,能够快速地构造出空间效率比传统的Thompson构造法高得多的NFA.     

基于正则表达式技术的数据验证及应用

本文主要介绍基于正则表达式的模式匹配和数据验证技术,并通过示例说明java正则表达式在数据验证应用中的使用方法及原理。     

面向网络流的自适应正则表达式分组匹配算法

针对当前的多正则表达式匹配算法占用较大的系统资源,且吞吐量较低的问题,在分析典型的正则表达式匹配算法的基础上,提出了一种自适应的多正则表达式分组匹配算法.该算法通过对正则表达式进行高效分组,将相互之间存在交叠且容易引起状态数指数增长的表达式相互隔离;将每个分组构造为一个确定性有限自动机(DFA),按匹配概率大小建立伸展树进行调度.仿真结果表明,该算法不仅大大节省了存储空间,而且吞吐量提高了大约3倍.     

一种基于Bloom Filter的正则表达式集合快速搜索算法

正则表达式搜索算法的性能与从非确定性有限状态自动机(NFA)的初始状态到终止状态的最短路径Lmin成正比,与正则表达式所表达的语言的前缀集合Pref(RE)成反比,而一般情况下Pref(RE)较大,确定Pref(RE)中的元素在目标文本中的出现位置比较困难.文中提出了一种基于Bloom Filter的正则表达式集合搜索算法,此算法利用Bloom Filter集合查询时间与集合大小无关的特点,可以快速准备定位Pref(RE)的出现位置,使得搜索速度不受Pref(RE)的影响,如果采用多个Bloom Filter并行,还可以间接增大Lmin.分析与测试结果表明,该算法较大地加快了正则表达式的搜索速度,对于正则表达式集合,算法性能改善尤其明显,在Lmin较长、Pref(RE)较大时,搜索速度可以提高数倍至数十倍,适合大规模的多正则表达式的快速搜索.     

正则表达式匹配IP地址的实践与研究

正则表达式语言是世界上最流行的字符串匹配语言，它被许多编程语言或工具所支持。运用正则表达式匹配IP地址，比较了一些模式的写法，分析了某些模式在不同正则表达式引擎下的差异，得出了一个精确、通用的模式。     

正则表达式的实现

正则表达式提供了功能强大、灵活而又高效的方法来处理文本。论述了如何用C＋＋语言实现基于正则表达式的查找和替换。     

正则表达式与有穷自动机等价性在Isabelle/HOL中的形式化

针对正则表达式和有穷自动机,在机器辅助定理证明系统Isabelle/HOL中进行了形式化描述。通过对语言、正则表达式、确定和不确定有穷自动机在Isabelle/HOL中建立模型,定义了它们之间的相互转换函数并证明了这些函数的正确性,从而验证了正则表达式和有穷自动机在描述能力上的等价性,即:在同一有限字母表下,对任意正则表达式,都存在一个有穷自动机,使得二者描述的语言相同;反之亦然。通过分析与证明,表明采用机器辅助定理证明系统,对计算理论传统核心领域之一的自动机理论进行分析和证明是可行的。     

一种基于多线程的混合深度包检测方法

为了提高网络入侵检测速度和稳定性,提出了一种基于多线程的混合深度包检测方法.该方法首先采用正则表达式的线性系数来对规则集中的正则表达式进行分组,然后对不同正则表达式组采用不同压缩技术进行状态位压缩,生成不同FA(Finite Automata),最后采用多线程技术对生成的不同FA进行检测.通过实验验证,得出该方法具有较高的压缩和处理性能,同时能有效提高检测的速度和稳定性.     

模糊树语言与模糊树文法的等价性

考虑采用正则表达式,有限自动机和文法来描述,提出了模糊树正则表达式的概念,得到了模糊树正则语言的可识别性,并证明了模糊树语言是正则的充分必要条件,这为进一步讨论模糊树自动机奠定了基础.     

一种新型动态可重构的正则表达式匹配引擎设计

针对大规模数据处理和动态更新规则的网络计算需求,本文提出了一种新型动态可重构的正则表达式匹配(DRR)算法.算法采用参数化一致性表达方法,提高了正则表达式的动态匹配能力;采用专用电路与可重构电路的混合计算框架,设计了正则表达式匹配的并行计算加速引擎.在软硬件协同工作模式下,新型动态可重构的匹配加速引擎不仅可以最大化利用FPGA电路的可编程特性实现表达式匹配规则的动态更新,提高匹配的预处理速度,设计的专用ASIC并行匹配电路更大幅提高了正则表达式的匹配计算速度.本文采用TSMC 28nm CMOS工艺完成芯片的设计和流片,实验结果表明:本文设计实现的动态可重构的匹配加速引擎可以有效地适用于大多数应用场景下的正则表达式匹配,匹配计算的吞吐率达到280Gb/s,相比于同类型基于FPGA的匹配计算引擎实现了5倍以上的匹配速度提升.     

基于正则表达式的数字图书馆检索模型研究

文章就数字图书馆信息检索效率不高的问题,在现有数字图书馆信息检索模型的基础上,提出了一种新型的基于正则表达式的数字图书馆信息检索模型,详细论述了该模型的主要模块及其各自功能.通过采用正则表达式技术,分析了在包含正则表达式规则的传统关键字的信息检索模型,从而为如何突破关键词检索局限于检索词形式的固有缺陷,提高检索效率,减小漏检和误检造成的误差,为数字图书馆向智能化、知识化发展提出一种新的研究方向.     

确定有限自动机到正则表达式转换的并行处理

有限自动机和正则表达式都是描述语言重要方法,二者的转换具有重要意义.针对确定有限自动机模型做了深入的分析,在并行环境,提出了一种确定有限自动机到正则表达式的并行转换算法,并以实例详细描述了算法并行处理过程并验证了其算法的可行性.     

温控系统的时序Petri网建模与验证

基于时序Petri网对温控系统进行建模和性质描述.利用可达图、Büchi自动机和ω-正则表达式理论三者相结合的方法分析得到温控系统时序Petri网模型变迁引发序列集合的ω-正则表达式,进一步分析证明该ω-正则表达式满足温控系统的功能性需求说明,从形式上验证了温控系统时序Petri网模型与需求说明一致.结果表明,时序Petri网可用来描述和验证具有时序关系和因果关系的并发系统模型,是一种并发系统形式化描述和分析的有效工具.     

基于正则表达式的信息抽取系统在国防技术监测中的应用

从应用的角度提出了一种用于半结构化文本的基于正则表达式的信息抽取方法.通过对单个样本Web页面生成DOM(document object model)树生成信息抽取任务的规则.抽取规则采用正则表达式的形式记录目标信息的页面特征,通过规则的执行完成信息的抽取.该方法采用了基于正则表达式的Web页面的预处理(约简)、Web页面DOM树的生成、抽取规则的生成和执行.由于在实际大批量的抽取工作中能够避免多次生成页面DOM树,因此批量信息抽取的速度提高了约10倍.     

正则表达式在控制MARC数据质量中的应用研究

随着网络和信息技术的发展，联机编目得以实现，编目工作的重心也由传统的著录方式向编目规范控制工作转变。本文详细介绍了正则表达式以及用正则表达式的匹配规则来规范MARC数据的方法，为有效控制MARC数据质量、提高审校MARC数据的效率提供了思路。     

基于多GPU的正则表达式匹配技术

针对传统正则匹配性能低下的问题,设计了基于多GPU的正则表达式匹配引擎,并采用折半分组优化算法解决了有限状态自动机在大规模正则集合情况下由于空间爆炸无法使用的问题,并做了相关的优化,提升了数据匹配速度.实验结果表明:基于多GPU的正则表达式匹配性能较CPU提升了61倍,其数据吞吐率远优于其他加速方式.     

基于规则分组的DFA正则表达式匹配算法

模式匹配因误报率低和漏报率低被入侵检测所采用.在使用正则表达式构造DFA时,因状态爆炸导致匹配算法需要较多的存储空间和运行时间,算法效率低下,采用规则分组后,可以在一定程度上抑制状态爆炸问题.根据缓存中的历史记录对正则表达式进行分组,既能利用规则分组减少状态总数,抑制状态爆炸,又能减少因每次重新构建DFA所带来的开销,...