一种基于尾匹配q-gram的近似串匹配算法

近似串匹配是生物信息学、文本检索、信号处理等领域的一个基础问题,如何提高近似串匹配的速度一直都是研究的关键问题。提出一种新的在大文本库中快速查找近似匹配的无损过滤算法。为保证在大文本库中的匹配速度,本算法使用了查询速度较快的q-gram索引。为通过提高过滤算法的过滤效率达到提升算法整体性能的目的,详细分析了含有匹配串的文本区域,提取了一些基于尾匹配q-gram特征的新过滤条件,然后用这些特征优化了过滤算法的过滤标准。实验数据表明,新过滤条件有效地提高了算法的过滤效率,提升了算法的整体性能。结果显示新算法适合各种匹配错误率下的近似匹配,算法的通用性较强。     

基于存储优化的多模式串匹配算法

多模式串匹配算法是网络内容过滤系统的核心技术之一.自动机的存储空间大小和Cache性能是影响多模式串匹配算法速度的关键因素.随着模式串规模的扩大,自动机的巨大存储开销导致现有的串匹配算法性能大幅度下降.从压缩存储空间以提高Cache命中率的思想出发,提出了一种对经典SBOM算法的优化策略,它用Suffix Tree代替SBOM算法中的Factor Oracle结构,同时用剪枝的方法将Suffix Tree降低为近似线性的空间复杂度,然后用双数组Trie表示之,以压缩存储空间.与SBOM算法相比,改进算法不仅能够有效地节省存储空间,而且显著地提高了串匹配的速度,非常适合于在线高速匹配的应用环境.     

信息过滤系统中字符串匹配算法的研究

模式匹配是基于攻击特征的信息过滤系统中的网络数据包分析技术,匹配算法的性能直接影响到整个系统的效率,是当前信息过滤监测系统的一个主要瓶颈,因此以速度较快的BM算法为基础,提出了一种改进的字符串匹配算法,充分考虑模式匹配失败的信息.使其在每一次跳跃中跳过尽可能大的距离.通过实验证明了改进的算法减少了匹配的次数,具有更高的效率.     

基于后缀WM匹配算法的改进算法

针对基于后缀WM匹配算法中的字符重复匹配问题,给出了相应的改进算法.该算法针对扫描阶段确定的与模式串前缀、后缀和前m个字符的后缀都相同的文本串字符块,在匹配阶段跳过文本串字符块中已经确定的字符块,避免了对已经确定的字符块的重复匹配,减少匹配开销.实验结果表明,相对于原始算法,改进算法降低了系统匹配的运行时间,提高了系统运行的效率.     

病毒特征检测中改进的多模式匹配算法

针对病毒特征检测中码串长度对模式匹配算法性能影响的问题,结合基于码串长度的特征集自适应分类思路,提出了两种改进的多模式精确匹配算法,即NAC_BM和NWM_QS。改进算法通过引入文本窗口的前缀字符块WB增加了跳跃距离,减少了匹配次数,加快了匹配效率。初步实验证明,改进算法在执行时间和速率上优于原算法。     

基于随机匹配的非局部相似块搜索算法

针对非局部相似块搜索问题,提出一个基于随机匹配的k近邻块匹配算法.在基于Jump Flooding传播的块匹配算法基础上,改进其候选参考块的产生方式,增加从查询块的局部邻域中随机产生候选参考块这一方式.这一改进提高了候选参考块匹配的可能性,进而提高了算法的匹配精确度.实验结果表明改进算法在时间效率和并行性上,与原算法相差不大,但在匹配精确度上,要优于原算法.     

一种基于过滤技术的字符串模糊匹配方法研究

针对基于编辑距离的字符串模糊匹配方法搜索效率较低的问题,通过对字符串模糊匹配过程进行分析,利用并行化技术对大数据量的字符串模糊匹配过程进行优化.同时由于计算字符串间编辑距离算法性能较低,提出利用字符串过滤规则对待搜索字符串集合进行过滤后再进行模糊匹配的改进方法.实验结果表明,改进后的方法具有较高的执行效率并取得了较好的召回率和精度.     

一种适合于超大规模特征集的匹配方法

串匹配技术是入侵检测系统中的关键技术,随着特征数量的增加,现有的自动机类匹配算法都会面对内存占用过大的问题.当特征超过一定数目后,自动机可能根本无法构造.文中提出了一种针对超大规模特征匹配(SLSPM)环境的匹配算法SLSPM.SLSPM算法借助一个块式匹配自动机和若干个普通自动机完成匹配工作,而且能够支持至少上万规模的特征集.与普通匹配自动机先读入状态再判断读入符号的方式不同,SLSPM首先使用散列函数判断当前文本块是否可以被过滤掉.如果文本块无法被过滤且为合法文本块时,再检查当前状态是否是一个能够识别当前文本块的状态.仅在当前状态吻合的情况下再读入下一个文本块进行后续匹配.理论证明显示SLSPM算法具有近似O(n)的复杂度.由于SLSPM算法未能保存全部的跳转信息,其匹配速度相对于高级AhoCorasick算法未有大幅提升.算法的优势在于,该算法在软件环境下能够维持与AC算法相同的匹配性能,而且能够将特征加载规模至少提升至上万以适应超大规模特征集匹配环境.     

一种按字长匹配的Wu-Manber多模式匹配算法

多模式匹配是串处理系统中最重要的操作之一,而Wu-Manber算法是多模式串匹配算法中平均性能表现最好的算法.针对Wu-Manber多模式匹配算法在规则集中存在短模式串时性能下降的问题,提出一种按字长匹配的多模式匹配算法.改进的算法是在32位机器上实现,哈希的字符块长度取2,每次匹配的单位由原来的一个字符变为一个机器字,缩小了访存时间,同时利用机器字长存储的特点合理设计哈希函数,加快了字符块哈希值的计算,极大的提高了有短模式串存在时模式集的匹配性能.与原Wu-Manber算法对比,当最短模式串长度小于6时,改进后的算法搜索时间平均缩短了40％.当最短模式串长度为2和3时,搜索时间缩短了60％以上.     

一种WM多模匹配算法的研究与改进

针对现存多模匹配算法WM存在的三个缺点:每次参与匹配的模式串数量大、字符比较次数多、失配时文本串匹配窗口向右移动距离过小,提出一种改进WM算法——NEW_WM.采用后缀表和前缀表进行二次地址过滤,对前缀表采用平衡二叉树存储,减少每次需匹配的模式串数量;采用字频匹配快速找到失配字符,减少每次匹配时的比较次数;在失配时匹配窗口采用BMH和BMHS算法的跳跃距离的较大者右移.实验测试结果表明:在相同的条件下,相对于WM和DHSWM算法,NEW_WM算法在匹配性能方面有一定幅度的提高.     

New algorithms for fixed-length approximate string matching and approximate circular string matching under the Hamming distance

This paper proposes new algorithms for fixed-length approximate string matching and approximate circular string matching under the Hamming distance. Fixed-length approximate string matching and approximate circular string matching are special cases of approximate string matching and have numerous direct applications in bioinformatics and text searching. Firstly, a counter-vector-mismatches (CVM) algorithm is proposed to solve fixed-length approximate string matching with k-mismatches. The development of CVM algorithm is based on the parallel summation of counters located in the same machine word. Secondly, a parallel counter-vector-mismatches (PCVM) algorithm is proposed to accelerate CVM algorithm in parallel. The PCVM algorithm is integrated into two-level parallelisms that exploit not only word-level parallelism but also data parallelism via parallel environments such as multi-core processors and graphics processing units (GPUs). In the particular case of adopting GPUs, a shared-mem parallel counter-vector-mismatches (PCVMsmem) scheme can be implemented from PCVM algorithm. The PCVMsmem scheme can exploit the memory model of GPUs to optimize performance of PCVM algorithm. Finally, this paper shows several methods to adopt CVM and PCVM algorithms in case the input pattern is in circular structure. In the experiments with real DNA packages, our proposed algorithms and scheme work greatly faster than previous bit-vector-mismatches and parallel bit-vector-mismatches algorithms.     

Approximate string matching with suffix automata

Theapproximate string matching problem is, given a text string, a pattern string, and an integerk, to find in the text all approximate occurrences of the pattern. An approximate occurrence means a substring of the text with edit distance at mostk from the pattern. We give a newO(kn) algorithm for this problem, wheren is the length of the text. The algorithm is based on the suffix automaton with failure transitions and on the diagonalwise monotonicity of the edit distance table. Some experiments showing that the algorithm has a small overhead are reported.     

一种有效的字符串有序跳跃模式近似匹配算法

字符串的模式匹配问题是计算机科学的基本问题之一,而近似模式匹配更是近期的研究热点。本文分析了文本分析领域中出现的一种特殊的近似模式匹配问题,即字符串有序跳跃模式近似匹配问题,提出了一种基于有限自动机的组件组合分析算法。算法的特点在于将组件匹配过程与组配过程进行分离,这样既降低了问题的复杂度,又可以实现按策略组配的灵活性。组件匹配过程中利用有限自动机对跳跃模式的组件进行匹配查找;组件的组配过程中先对查找到的组件进行组合分析,然后再对各种组合进行初步筛选和基于策略的优选。初步筛选工作是依据顺序性、唯一性和最大数三条原则进行;而优选工作是根据四个设计的评价参数选择其中最佳组合。实验结果表明,该算法的确能解决字符串有序跳跃模式匹配问题,完全可以适用于句型匹配与主题词跳词匹配。     

允许错误的（汉字）字符串快速检索技术

在计算机应用的诸多领域中都会遇到字符串似检索问题。本提出了一种技术。它通过应用搜索状态向量及字符－模式匹配向量，将字符串匹配比较转化简单的整数字位运算，有效地解决了字符／汉字串的相似匹配问题，中也给出了实现算法并分析了算法的复杂性。     

A Randomized Algorithm for Approximate String Matching

We give a randomized algorithm in deterministic time O(Nlog  M) for estimating the score vector of matches between a text string of length N and a pattern string of length M , i.e., the vector obtained when the pattern is slid along the text, and the number of matches is counted for each position. A direct application is approximate string matching. The randomized algorithm uses convolution to find an estimator of the scores; the variance of the estimator is particularly small for scores that are close to M , i.e., for approximate occurrences of the pattern in the text. No assumption is made about the probabilistic characteristics of the input, or about the size of the alphabet. The solution extends to string matching with classes, class complements, ``never match' and ``always match' symbols, to the weighted case and to higher dimensions. Received July 20, 1997; revised April 20, 1998, and June 1, 1999.     

基于压缩后缀数组的近似字符串匹配算法

近似字符串匹配是模式匹配研究领域中的一个重要研究方向。压缩后缀数组是字符串匹配、数据压缩等领域广泛使用的索引结构,具有检索速度快和适用广泛的优点。利用压缩后缀数组,提出了适合近似字符串匹配搜索算法的数据结构,并在此基础上提出了一种匹配搜索算法。实验结果表明,相对于现有的算法,提出的算法在小字母表的情况下具有计算优势。     

快速中文字符串模糊匹配算法

本文解决了中文字符串模糊匹配的两个主要问题:空间问题和时间问题。目前字符串模糊匹配的两个主要方法是位向量方法和过滤方法。由于汉字众多,应用位向量方法时,需要大量空间。对于某些内存很少的小型计算机,比如嵌入式系统,这将会是一个问题。本文改进了位向量方法,使其在应用于中文字符串时,空间需求降低到约5%。本文还利用汉字非常多的特点,提出一种新的基于过滤方法的中文字符串模糊匹配算法,BPM-BM,其速度比世界上最快的算法至少提高14%;在大部分情况下,是其速度的1.5～2倍。     

一种快速的基于BM模式匹配的改进算法

模式匹配算法是入侵检测系统(IDS) 中非常重要的一种算法. 在研究和分析几种常用模式匹配算法的基础 上, 提出一种快速的基于BM(Boyer-Moore) 模式匹配的改进算法—–IBM 算法. 该算法充分利用模式串的末字符和 末字符所对应的文本串的后两字符的唯一性, 同时参考文本串本身的信息来提高模式串的移动量, 使得每次失配后, 在保证不丢失匹配成功可能性的前提下尽可能多地向后跳跃. 实验结果表明, 该算法相比其他模式匹配算法, 在检测 性能和匹配效率上均具有很大优势, 并且能够有效地提高IDS 的检测效率和性能.

     

KR字符串匹配算法的研究与实现

字符串匹配是判断模式串(短串)是否是文本串(长串)的子串。KR算法是一种随机串匹配算法,详细介绍KR串匹配算法的算法描述及代码实现过程,并对该算法进行测试,讨论该算法的实现效率。     

字符串模糊匹配算法的探讨

字符串模糊匹配问题在计算机中有着广泛的应用．尝试探讨一种无论从算法时间复杂度上讲还是编程复杂度上都比较优秀的一种模糊匹配算法。