带可变长度空位和一次性条件的模式匹配

带可变长度空位和一次性条件的模式匹配是一种带通配符长度约束的模式匹配问题,主要目标是寻找模式在序列中的最多出现,要求序列中任何位置只能被使用一次。提出了一种基于网树在线的启发式算法,该算法首先通过模式中子模式的出现位置构建网树;然后,从网树上选择使用次数最小的节点作为出现的位置;最后,对网树进行修剪,以达到满足一次性条件和加快搜索效率的目的。通过理论分析,该算法有更好的时间复杂度和空间复杂度。通过真实生物数据进行实验,实验结果表明,该算法与其他在线算法进行对比,可以获得更多的出现次数和更好的时间性能。     

IDS中一种新的模式匹配算法及其并行化

基于字符串匹配的检测方法是入侵检测系统(IDS)中一类很重要的分析方法,文章分析了著名的BM模式匹配算法,提出了一种新的字符匹配算法zY模式匹配算法,该算法的时间复杂度为O（n*(m-1)),比BM算法的时间复杂度O(n*m)低。最后对ZY模式匹配算法进行了并行化设计,并给出了设计代码。     

一种曲线形态的描述与识别方法及其应用

为准确描述与识别时间序列曲线形态,根据曲线段类型定义了5个语素和1个通配符,进而定义语素向量及通配符向量,使得对曲线的描述具有层次性.据此将任意时间序列曲线转变为对应的二维表,二维表第二列组成的字符串能够进行初级的模板匹配,二维表各行所代表的向量增强了语素关系运算的能力,可实现较深入的模式识别.在经典回溯法的启发下设计了一种属性约束下的带通配符字符串匹配算法,并以基于感应线圈信号曲线的车型分类为例,验证了所提出的方法的有效性和合理性.     

求解PMWOC问题的算法

带有灵活通配符和One-Off条件的模式匹配问题(Pattern Matching with flexible Wildcards and One-off Condition,PMWOC)在生物信息学、文本检索和数据流等领域都有着广泛的应用.给定带灵活通配符的模式和文本,在one-off条件下,已有算法不能得到模式在文本中的完备解,即模式在文本中最大的出现数目.为此,设计一个求解该问题的算法:首先,利用动态规划的思想去获得模式的所有出现及匹配位置;然后,根据模式的完备解至少包含任意一次出现中的一个位置的思想获得模式解的集合.通过DNA数据进行实验,实验结果显示相对于已有的算法,该算法能够获得最多的出现解.     

一种改进的KR模式匹配算法

在分析BF、KMP和KR等模式匹配算法的基础上提出一种改进的KR算法(IKR),在产生哈希冲突时利用双向比较法进行匹配.实验结果表明,该算法可以快速有效地进行模式匹配.     

字符串匹配算法Sunday的改进

字符串的模式匹配应用十分广泛,在信息的搜索查询等方面具有重要作用,研究串匹配算法的效率具有重要的理论价值和实际意义。在分析几种经典模式匹配算法的基础上,对当前应用最广泛的Sunday算法提出了改进的算法Zhusunday.算法主要改进之处是:在字符串从右向左匹配过程中,当文本字符中出现不匹配模式字符串的字符且该文本字符不是坏字符时,算法从右向左搜索当前文本字符在模式串中出现的位置;找到当前字符在模式串中的位置后继续再向左匹配模式串字符一次,如果仍不匹配时,模式窗口比Sunday算法多向右移动一个字符。改进的算法提高了模式匹配的执行效率,通过大量对比实验证明了该算法的有效性。最后得出结论:在实际应用中,坏字符大量存在的情况下,改进算法的最优时间复杂度可达O(n/m),在同一时间复杂度下,比Sunday算法效率提高25~50%.     

并行环境下的空间模式匹配

空间模式匹配在各类基于位置的服务中有广泛的应用,但在面向空间大数据时,现有空间模式匹配算法的效率难以满足实际要求.针对上述问题,采用并行计算框架Spark,设计基于空间模式边匹配并行的空间模式匹配算法PMSJ(Parallel Multi Star Join). PMSJ算法将空间模式匹配问题分解为可以独立、并行执行的称为边匹配的子问题,将计算量分散至集群中各个计算节点以提高计算效率.具体地,PMSJ将边匹配分为针对空间区域的最小边界矩形匹配与针对具体空间对象的边匹配两个并行步骤,并在计算边匹配前对最小边界矩形匹配的结果进行剪枝,排除无法产生完整空间模式匹配的匹配对.在四个真实数据集上的实验结果表明,在面向空间大数据时,PMSJ算法的效率优于现有算法.     

字符串随机探测模式匹配算法

分析了目前字符串模式匹配的五种算法,总结了各种算法的时间复杂度和在不同场合下的不同表现,并从经典算法出发,提出了一种随机探测模式匹配算法,同时评价了该算法的特点.     

Deep Web中一种基于本体和BP网络的模式匹配方法

针对Deep Web中模式匹配难度大的问题,根据目前模式匹配的特点,提出一种基于本体和BP网络相融合的的模式匹配新方法。该方法利用具有相同含义的本体分组来确立模式之间的对应关系,降低匹配的复杂度;利用BP网络的自我学习能力提高匹配的自动化程度。实验结果表明该方法能明显提高模式匹配的精确度和召回率,有效地提高了匹配质量。     

一种时间序列曲线形态的描述方法及其在车型识别中的应用

提出时间序列曲线形态的一种新的描述方法。首先根据曲线段类型定义了5个语素和1个通配符,进而定义语素向量及通配符向量,使得对曲线的描述具有层次性。据此可将任意时间序列曲线转变为对应的二维表,二维表表头组成的字符串能够进行初级的模板匹配,二维表表列所代表的语素向量增强了语素关系运算的能力,可实现较深入的模式识别。为使所提出的描述方法能应用于曲线形态辨识,在经典回溯法的启发下设计了一种属性约束下的带通配符字符串匹配算法。最后,以基于感应线圈信号曲线的车型分类为例,验证了所提出的方法的有效性和合理性。     

一种改进的BMH模式匹配算法

目前的入侵检测系统大多是基于特征的，系统的性能瓶颈在于模式匹配算法的执行效率．在探讨几种典型的模式匹配算法的基础上，提出了改进的BMH算法．该算法通过取文本串中的两个连续字符计算偏移量的方式，减少了匹配的次数．实验结果证明匹配速度得到了一定程度的提高．     

分块法的模式匹配算法的研究

为提高模式匹配算法性能,介绍经典的模式匹配算法Byoer-Moore和Sunday,分析它们改进后的效率,根据分块法的特点,提出一种新的分块模式匹配(block pattern matching,BPM)算法?BPM算法在预处理阶段先确定模式串的首字符在文本串的位置,再确定此字符后长度等于模式串长度的字符是否等于模式串的尾字符,若符合条件,采用单链表存储结构进行存储,在匹配阶段,利用单链表信息进行双向匹配?实验结果表明,BPM算法大大减少了匹配次数和字符比较个数,从而提高匹配效率?     

网络入侵检测系统中多模式匹配算法的研究

网络入侵检测系统的性能一定程度依赖于精确、快速的模式匹配技术。随着网络速度的快速增长,模式匹配技术必将成为入侵检测系统性能的瓶颈。首先介绍了网络入侵检测系统Snort中采用的多模式匹配算法,进而提出了一种改进的多模式匹配算法。实验结果表明,改进后的算法降低了时间复杂度,提高了系统检测效率。     

一种面向中文的快速字串多模式匹配算法

针对中文字串匹配问题,提出一种快速模式匹配算法,算法采用新型组合状态自动机,将2个状态组合起来匹配一个双字符,从而解决了双字节符构建完全Hash表时带来的存储空间膨胀问题;同时考虑到待匹配模式串中的字符在大字符集中稀疏分布的特点,尝试将单模式QS匹配算法的思想与DFSA算法进行结合,应用于多模式匹配中,实验结果显示,本算法明显优于DFSA算法,平均所花费时间仅为DFSA算法的45．2％。     

一种快速单模式准确匹配算法

引入连续跳跃查找文本的思想，提出了一种新的单模式精确匹配算法，其最优条件下的时间复杂度为O[n/(m 1)]，新算法的平均时间复杂度分析表明其具有优越的查找性能，对比实验结果显示，新算法的性能优于目前所见的同类算法，特别是在模式较短的情况下，优势更为明显，这一特点非常适合于自然语言文本的检索。     

基于空间相关预测的快速块匹配运动估计算法

为了提高自适应十字搜索(adaptiveroodpatternsearch,ARPS)算法中运动估计的速度和准确性,提出一种基于空间相关预测的快速块匹配运动估计算法.根据块匹配度量准则,将邻域块中与当前块相似度最高和次高的两个运动向量(motionvector,MV)的均值作为当前块的预测MV,改进了传统ARPS算法的固定单块预测模式,增强了起始搜索中心位置的预测,减小了由于运动变化而引起的预测误差.实验结果表明所提算法与ARPS和其他标准快速块匹配运动估计方法相比,有效地减少了计算复杂度,提高了配准精度.     

SURF算法在局域盲人图像导航中的应用

局域盲人图像导航即在建立基准图像信息特征库的基础上,对实时拍摄图像提取特征并与基准图像特征库进行匹配,得到相应地理信息并语音输出给盲人,从而实现导航的一种方法。本文基于SURF算法对图像特征进行匹配,首先提取SURF特征点,然后采用Hessian矩阵迹快速索引匹配以及匹配点距离差平方和的相似性度量方法进行匹配。实验表明SURF匹配算法优于SIFT匹配算法,并可实现快速、鲁棒、准确匹配,为实现盲人局域图像导航奠定理论基础。     

KMP扫描算法的改进

通过对字符串模式匹配BF和KMP算法的分析,提出了改进KMP扫描算法的方法,并通过对算法的复杂性进行分析,结果表明：改进后的算法KMPA比算法KMP更有效。