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

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

基于集合覆盖和禁忌搜索算法的WCDMA基站布局

分析和比较了集合覆盖和禁忌搜索两种高效布局算法的优化性能和计算时间.在此基础上提出了一种新的WCDMA基站布局算法,该算法使用集合覆盖进行整体布局,使用禁忌搜索进行局部优化.由于综合利用了集合覆盖算法的快速性和禁忌搜索算法的精确性,实际场景仿真结果显示,新算法仅用禁忌搜索算法8.8%的计算时间,就搜索到比禁忌搜索算法优化性能更好的布局配置.     

Bloom Filter和Weighted Bloom Filter的比较与研究

Bloom filter是一个简单的空间效率极高的数据结构,用于判别一个元素是否属于某个集合.Weighted Bloom filter和Bloom filter已经被建议作为共享Web cache信息的一种方式.利用Bloom filter表示共享信息的内容,大大降低了用于存储索引的空间消耗,减少了访问延迟.因为在代理之间只需传输Bloom filter而不是完整的cache目录表.分别从理论和实践方面比较了Bloom filter和Weighted Bloom filter,结果证明Bloom filter比Weighted Bloom filter更好.     

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

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

多路平衡型矩阵Bloom Filter

海量数据的高效表示和查找成为目前存储系统面临的重要挑战.针对存储系统中大规模动态数据集的表示和查找效率问题,提出一种多路平衡型矩阵Bloom Filter结构(M-BMBF)及其插入和查询算法.M-BMBF根据数据集合大小建立一个r×m矩阵型Bloom Filter,设计多个定位哈希函数将该矩阵Bloom Filter分为多组(多路)以实现平衡插入和高效查询操作.为减缓Bloom Filter中比特的消耗速度,使用一种"最长位匹配"填充算法,新元素的插入将从多路备选Bloom Filter中选择新置为1比特个数最少的Bloom Filter中进行.实验结果表明,相较典型拆分Bloom Filter,M-BMBF能在维持算法消耗时间为常量的基础上,有效节省存储空间,降低误判率.     

货郎问题求解算法分析

介绍了求解货郎问题的4个算法：贪心算法、MST近似算法、MM近似算法和回溯搜索算法。分别使用各个算法对一个货郎问题的具体实例进行求解，并对各个算法的性能进行了分析比较。贪心算法的运行速度较快，但在大多数情况下该算法找到的是次优解而非最优解。MST和MM近似算法用以求解满足三角不等式的货郎问题，其近似性能比（即精确度）分别为：RMST（I）＜2，RMM（I）＜3／2。回溯搜索算法可以求出货郎问题的最优解，随着城市数目的增加，其搜索效率会下降。     

基于混沌理论的涡流搜索算法

基于混沌变量遍历性、随机性和规律性的特点,提出一种混沌涡流搜索算法。混沌涡流搜索算法应用混沌映射机制更新涡流搜索算法的备选解,增加了种群多样性,增强了算法的搜索能力,提高了算法的收敛速度。为了验证混沌涡流搜索算法的性能,采用9个著名的测试函数进行测试,并与粒子群算法、人工蜂群算法和萤火虫算法对比,实验结果表明混沌涡流搜索算法具有良好的收敛精度、收敛速度和搜索能力。     

基于最优树联配的正则表达式学习算法

由于正则表达式（RE）被广泛用于信息抽取、模式学习和生物序列分析等领域,因此开发能够从正样例集学习RE的算法很有实际意义.为克服现有RE学习算法在所学RE类型、样例数目和样例类型等方面存在的限制,基于最优树联配原理提出了一种基于树结构的RE学习算法.该算法的特点包括：采用自适应方法自动选择最优代价阈值;对所学RE类型、...     

复杂系统可靠性优化的混合万有引力搜索算法求解

复杂系统可靠性优化问题是一类有约束限制且目标函数具有多个局部极值的非线性优化问题.为求解该类问题,提出了一种混合万有引力搜索算法的求解方法.算法利用基于万有引力定律的寻优机制指导群体进行全局搜索,并采用序列二次规划算法进行局部搜索,避免基本万有引力搜索算法陷入局部最优,改善优化性能,加快寻优速度.通过实例计算,并与蚁群优化算法、微粒群算法、蜂群算法和基本万有引力搜索算法等进行比较,验证了算法的可行性和有效性.     

提高图像块运动估计搜索速度的改进算法及其性能

运动估计是视频压缩中帧间预测编码的关键技术之一.由于运动估计具有较大的运算量,因此对压缩性能有重要影响.在研究分析了影响视频编码性能的传统搜索算法基础上,提出了一种基于六边形搜索算法的改进算法.该算法初始步骤使用十字形搜索模式,然后采用六边形搜索模式中的小钻石搜索模式,进行快速块运动估计.并进行了计算机仿真实验证明了改进算法在压缩处理运算量及信号质量方面的优越性.结果表明,改进算法比新三步搜索算法和传统六边形搜索算法有着更快的搜索速度和更小的失真.     

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

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

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

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

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

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

块匹配运动估计算法的速度优化

在视频压缩系统进行帧间编码时 ,很多运动估计块匹配算法利用搜索样式的设计来节约计算资源 ,搜索速度尚有提高的空间·利用运动矢量主要分布在搜索区中心 3× 3范围内的中心偏置特性来优化块匹配算法 ,并同时采用起始搜索点位置预测来提高搜索命中率· 仿真试验表明 ,优化算法在保证原算法精度的基础上明显提高了搜索速度     

基于混合策略的单模式匹配算法

结合后缀有限自动机和正向有限自动机的优点,提出了两个单模式匹配算法.算法中,无论是后缀自动机还是正向有限自动机,只要扫描到的模式前缀长度R>0或者超过模式长度的1/2时,使用正向有限自动机继续向右进行扫描;否则都滑动m-R个字符,使用后缀自动机反向扫描模式串的前缀.两个算法的最差、最好时间复杂度分别为O(n)和O(n/m).结果表明,在短模式的情况下,两个算法的平均时间复杂度均好于RF和LDM,在小字符集长模式或大字符集短模式的情况下它们的平均性能好于BM.     

Γ-半群的(∈，∈∨q)-模糊双理想

将半群中的几种(∈,∈∨q)-模糊子集的概念推广到Γ-半群中,在Γ-半群中引入(∈,∈∨q)-模糊Γ-子半群、(∈,∈∨q)-模糊双理想、(∈,∈∨q)-模糊广义双理想的概念, 用有关模糊集的理论讨论了它们的刻画。证明了(∈,∈∨q)-模糊双理想的交、并仍为(∈,∈∨q)-模糊双理想,正则Γ-半群的每个(∈,∈∨q)-模糊广义双理想为(∈,∈∨q)-模糊双理想。     

多输入多输出系统中基于多级维纳滤波的均衡算法

基于多级维纳滤波器,提出了一种多输入多输出系统中的降秩自适应均衡算法.该算法利用多级维纳滤波器得到一组子空间基向量,通过子空间投影,把均衡器输出限定在低维子空间内,从而降低了自适应均衡的迭代复杂度,加快了收敛速度.理论分析和仿真表明,降秩均衡算法有效地提高了均衡器的收敛速度,降低了计算复杂度,并在多级维纳滤波器的级数不超过 10 的情况下,就能达到近似满秩均方误差性能.     

基于布鲁姆过滤器的RFID中间件数据过滤算法设计

RFID（Radio Frequency Identification,RFID）中间件在RFID系统中起着承上启下的作用,数据过滤作为RFID中间件的核心功能,对其算法的研究一直是RFID领域研究的热点与重点。通过对现有过滤算法的分析,提出基于布鲁姆过滤器的数据过滤算法,鲁姆过滤器在空间和时间上有着更低的复杂度,并通过对布鲁姆过滤器算法的分析和仿真,选择了最优的布鲁姆参数,降低了算法的假阳性误判率。     

一种网络内容快速动态检测方法

高速网络内容检测与过滤依赖于快速多模式匹配算法按预先定义的模式集对分组的任意位置内容进行匹配。模式集往往有成千上万条,长短不一且十分复杂。多模式匹配算法对存贮器的访问速度很敏感,算法的好坏往往成为系统的性能瓶颈。另外,新的攻击层出不穷导致模式内容不断变化,如何在检测的同时有效地更新模式集合对网络安全设备在不停机检测条件下实现规则的升级与更新尤其重要。针对上述问题,提出了一种松散耦合的双通道线速动态内容检测方法,快速通道利用可动态查询的并行Counting Bloom filter引擎过滤网络分组。过滤出的嫌疑分组送慢速通道利用高效动态模式匹配算法一步准确鉴别和分析,从而避免对正常分组的阻碍达到线速检测。基于程序局部性原理,采用了额定长度前缀的方法实现了对长模式的可扩展性。分析与模拟试验表明,检测方法具有较高的吞吐性能,可以实现线速动态深度分组检测,同时减少了硬件资源开销,提高了可扩展性。     

基于不规则区域分割的快速分形压缩算法

首先基于序列块和主块之间最小象差的方差信息,提出了一方差排序搜索算法,该算法可产生与满搜索一致的分形编码.该算法能较大程度上减少对每个序列块进行搜索和匹配主块数与相应编码时间.并通过采用不规则区域变换,提出了一种不规则区域的图像分割算法,实际结果表明比传统的基于块的分割有更大的压缩比,并能减少编码时间.图4,表2,参10.