多模式匹配算法的性能分析

多模式匹配算法效率直接影响入侵检测系统的性能和效率.在分析研究经典的AC算法、WM算法和ExB算法的基础上,通过上机实验测试这些算法的模式匹配时间,为改进多模式匹配算法提供有益的借鉴.     

基于AC_QS多模式匹配算法的优化研究

随着互联网的日益强大,互联网上数据急剧增多,如何在海量的数据中快速准确地找到所需信息,就显得尤为重要,这就需要多模式串匹配算法.多模式串匹配算法在越来越多的领域里都有应用,比如:信息安全领域中,入侵检测系统、防火墙等,在医学领域、数据挖掘、信息检索等等领域中均有广泛的应用.AC算法在多模式串匹配算法中是一个能达到线性时间的算法,其算法效率较高,AC QS算法是在AC算法基础上增加坏字符规则,进一步增加了AC算法的匹配效率,但其空间复杂度较高.本文在AC QS算法的基础上,对算法预处理和匹配过程中继续优化,并对字典树存储时进行了优化,使算法在空间和时间复杂度上得到进一步优化,提高了算法性能.实验结果也验证了该算法的高效性.     

多模式匹配及其改进算法在协议识别中的应用

随着网络的高速发展,使得信息安全问题日益严峻,传统的很多协议识别技术已经无法应对不断出现的网络威胁,作为内容过滤和检测的关键技术之一,同时也是传统的字符串算法中被重点研究的对象之一,模式匹配算法成为当今研究热点。首先介绍了多种单模匹配算法及其存在的缺陷,然后在Aho-Corasick多模式匹配算法基础之上进行了改进,并将该算法应用于协议识别中,最后简单分析了协议识别中模式匹配算法未来的研究方向。     

一种基于Aho-Corasick算法改进的多模式匹配算法

目前互联网中以文本存在的数据非常庞大,针对在如此庞大的文本中如何准确、快速地找到多个不同的目标字符串的问题,在介绍常见的模式匹配算法的优点和缺点基础上,结合Trie速多模式匹配算法。根据对比性实验的结果分析得出,改进AC且匹配速度大约是AC算法的5倍,说明改进AC     

基于KR-BM算法的多模式匹配算法改进

网络技术的高速发展对模式匹配算法提出了更高的要求,为提高模式匹配效率,文中首先对常用的单模式和多模式匹配算法进行分析,在此基础之上,提出一种基于KR算法和BM算法的多模式快速匹配算法。最后通过实验结果验证了此算法的可用性和高效性。     

基于特征值的多模式匹配算法

高速网是当今网络发展的必然趋势,采用现行匹配算法的入侵检测系统(IDS)很难在高速网中有效地运行。本文主要从特征值的多模式匹配算法、模式库的组织和逻辑实现这三个方面来大幅度地提高系统检测速率,完全适应于高速网络的入侵检测。     

BM模式匹配算法的研究和改进

模式匹配算法在数字通信、入侵检测等多种领域都有着广泛的应用,BM算法以其高效的匹配过程成为模式匹配算法中应用最为广泛的算法之一。尽管如此,BM算法的效率还是可以再提高的。本文在介绍经典BM算法及其改进的BMH、BMHS算法的基础上,通过整合、改进后,提出了一种新的改进的IBMH算法。在对以上算法进行复杂度分析以后,再通过具体的实验验证。结果表明IBMH算法在比较次数、运行时间、稳定性等方面明显优于BM、BMH以及BMHS等算法。     

基于Q-Gram的数据库模式匹配算法

模式匹配是数据集成的重要步骤之一,而数据库异构、数据量大等特点是匹配的难点所在。在梳理模式匹配概念和研究现状的基础上,提出一种基于Q-Gram数据库模式匹配算法,通过对实例数据进行切分,计算域之间的相似度,得到域的语义匹配度。该算法具有线性的时间复杂度,实验显示其能给出较为精确的匹配结果。     

改进的K步长多模式匹配算法

K步长状态机存在失效函数,一部分存储空间被用来存储失效状态。为了提高K步长状态机的空间性能,该文通过K步长状态机的转移函数和失效函数f构建了新的转移函数,消除了K步长状态机的"失效链"。对改进算法进行性能分析表明,模式串数量和长度越大,改进后算法的空间优化效果越明显。     

基于异构隐式存储的多模式匹配算法

提出了紧缩存储型Aho-Corasick算法变体,以异构的按需隐式存储取代同构的例行显式存储,从横向扇出压缩与纵向路径压缩2个方向入手,围绕着压缩稀疏事件表展开,当字符集大小σ=256时可将存储量缩减为原来的0.69%左右,而σ＝64K时则达0.004%,即空间复杂度降为原来的(1bσ)/σ左右.依据扇出疏密程度的不同,分类采用了4种有针对性的快速事件定位方法,加之优化的失败迁移,使得存储量的大幅缩减不以速度的明显损失为代价,实验也证实了这一点.适用于需承载大型模式集和较长模式串而对时延和抖动都比较敏感的场合(如在线数据流过滤),在宽字符(如UNICODE型亚洲字符)匹配方面拥有显著优势.     

基于相似性度量优化的SIFT图像匹配算法

SIFT算法具有很好的尺度、旋转及光照不变性,因此被广泛应用在计算机视觉的诸多领域.但因其算法复杂、计算时间长,导致实时性不好.在研究SIFT特征描述符生成及匹配过程的基础上,提出一种在匹配过程中降低相似性度量计算时间、提高匹配效率的方法.该方法以棋盘距离和街区距离的线性组合替代欧氏距离来度量特征描述符之间的相似性.实验结果表明:该方法在保证SIFT算法鲁棒性的同时,可以降低匹配时间复杂度.     

志愿选课算法分析与优化研究

本文针对志愿选课算法的不足,分析了该算法中存在因志愿选择不当而易造成所选课程脱选等问题,进一步对该算法进行优化,提出了基于权重的志愿选课算法。该算法分两步实现:首先,学生根据所列举的课程填写选课志愿,并统计每门课程各个志愿的填报人数;然后参考学生自身权重值进行抽签,进而生成最终选课结果表。该算法在选课中不仅结合了学生对课程的偏好和需求,同时参考了学生自身的权重值,从而保证了选课结果更加合理、科学。     

一种新的粒子群优化的图像匹配算法

针对粒子群算法在图像匹配中易陷入局部最优、搜索速度慢以及匹配精度不高的问题,提出一种新的粒子群优化的图像匹配算法。首先,以改进的非线性惯性权重对粒子群算法进行优化,以此来平衡粒子在全局和局部的搜索能力;其次,提出添加动态扰动项对速度进行扰动,避免粒子在算法后期速度停滞为零而陷入局部最优。仿真结果表明,该算法提高了粒子的全局搜索能力和收敛精度,有效防止早熟现象,与基于标准的PSO图像匹配算法相比,所提算法具有收敛速度快、鲁棒性好以及匹配精度高的特点。     

基于Census变换和多扫描线优化的半全局立体匹配算法

为了解决局部匹配算法误匹配率高的问题,提出 一种基于AD-Census变换和多扫描线优化的半全局匹配算 法。首先,通过绝对差AD算法与Census变换相结合作为相似性度量函数计算初始匹配代价, 并构建动态交叉域聚合 匹配代价;然后在代价聚合计算阶段,将一维动态规划的代价聚合推广到多扫描线优化,利 用上下左右四个方向逐 次扫描进行匹配代价聚合的计算,并引入正则化约束以确保匹配代价聚合的一致性,大大减 少初始代价中的匹配异 常点;最后,运用简单高效的胜者为王策略选出像素点在代价聚合最小时对应的视差,并在 视差细化阶段,采用左 右一致性检测和抛物线拟合方法进行后续处理以提高立体匹配的正确率。实验结果证明,该 算法可获得高匹配率的视差图并且耗时较少。     

基于Harris-SIFT特征匹配的图像自动配准算法研究

为解决目前大多图像配准算法存在匹配精度低、实时性差的问题,本文提出了一种基于区域分块提取特征点的自动配准算法。该算法结合了Harris算子与SIFT(Scale-Invariant Feature Transform)算子的优点,先用Harris算子快速提取角点作为图像原始特征点,然后利用SIFT算子的特征描述方法对原始特征点进行描述,获得具有尺度不变性的特征点描述符,最后通过欧氏距离确定匹配点对进行图像配准。实验结果表明,该算法保留了Harris算子和SIFT算子的优点,减少了经典SIF算法提取极值点的时间,并且具有良好的鲁棒性、尺度不变性。本文针对200幅图像进行测验,当发生平移、旋转或缩放变换时,两幅图像间的匹配正确率高达95%。结果表明该算法能高效、高精度的实现图像配准。     

蚁群优化算法的收敛性分析与研究

蚁群算法本身存在收敛速度慢、容易陷入局部最优解的缺陷,针对该缺陷提出一些改进的蚁群优化算法。主要讨论蚁群优化算法的收敛性理论及应用,得出蚁群系统和最大最小蚂蚁系统的性能好于蚂蚁系统,而且最大最小蚂蚁系统的性能最好,蚁群系统和最大最小蚂蚁系统是值收敛的,一种特殊的ACOgs,ρ(θ)算法是解收敛的。     

Linux实时性能优化算法分析与研究

Linux以其内核精悍、功能强大、源代码公开、支持多种硬件平台以及支持丰富的开发工具等特点广泛应用在嵌入式系统领域.作为嵌入式产品的操作系统平台,实时性是一个很重要的目标.基于这个目标提出了一种提高Linux2.6实时性的O（1）算法,该算法设置了新的数据结构及进程调度过程,通过分析Linux 2.6的O（1）算法的时间复杂度,可以得知运用该算法可以极大提高系统的实时性能.