适合中文的双向比较模式匹配算法

分析了几种常用的模式匹配算法,提出一种适合于中文的基于KMP的改进算法,即双向比较模式匹配算法.该算法以KMP算法为基础,引入特征数组以记录模式串尾字符在模式串中出现的位置信息,从而获得模式串在匹配过程中的最大移动距离和最少比较次数.实验结果表明,双向比较模式匹配算法可有效降低匹配次数.     

字符串的模式匹配算法——基于KMP算法的讨论

重点对基本的串匹配算法和KMP算法进行了探讨。通过对这两种算法的比较分析提出了一个新算法，此算法具有比基本的串匹配算法更优越的时间复杂性，并且相对KMP算法而言更简洁易懂。     

浅论《数据结构》中KMP模式匹配算法讲解

模式匹配是《数据结构》中关于字符串的一个基本运算,一般有两种方法,分别为"朴素算法"与"KMP算法"。KMP算法是一种高效的字符匹配算法,它的关键在于当字符匹配失败以后,利用next数组中的信息使指针不需要回退,这样就减少了匹配的次数,提高效率。KMP算法不容易理解,该文通过举例等方法分析KMP算法的匹配原理及过程。     

KMP的多种计算方法

通过对串的前缀、后缀、交迭的介绍，引出了对失败函数的求解，解决了KMP算法中匹配串的移动问题，并提出了各种计算方法．该方法和传统的KMP算法的时间复杂度都为O(m n)．     

单模式精确匹配算法研究

模式匹配算法在各领域中有重大的应用价值。文章详细分析了BF、KMP、BM、Tuned BM和QS 5种单模式精确匹配算法;通过上机实验,采用不同的模式串长度对这些算法的匹配次数、比较过的字符个数和所需时间3方面进行测试;结果表明,BM、Tuned BM、QS算法在实际运行性能相对较好;而Tuned BM算法可有效地减少字符比较次数,是其中时间复杂最优的算法。     

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

在基于有限状态自动机的多模式匹配算法(DFSA算法)基础上,结合Tuned BM算法的优点,提出一种快速的多模式字符串匹配算法,实现了多模式匹配过程中不匹配字符的连续跳跃.在一般情况下,算法不需要匹配目标串中的每个字符,而是在实际比较之前跳过尽可能多的字符,以减少字符比较的操作,实现快速匹配.在模式串较长和较短的情况下,算法都有很好的性能.分析指出算法实际比较的字符数随着模式串长度的增加而下降,并随模式集的增大有所增多.实验表明,在模式串较短时,算法需要的匹配时间仅为AC算法的50%到33.3%,AQR算法的90%左右;在模式串较长时,所需时间为AC算法的25%至12.5%,AQR算法的75%左右.     

一种改进的Wu-Manber多模式串匹配算法

在分析Wu—Manber算法的基础上，结合QS算法思想，设计了一种改进的多模式串匹配算法：QWM（quick Wu—Manber）．算法充分利用紧邻当前窗口之后的B字符块，使算法的最大移动距离由原来的（m—B＋1）增大至（m＋B），平均移动距离也得到很大提高．同时对QWM算法和Wu-Manber算法进行了实验对比，无论模式串数量和最小长度怎么变化，性能都有较大提升．实验表明，改进的算法在对英文文本进行扫描时有4％～13％的提高．     

串匹配的一个新算法

本文提出了一个串匹配的新算法,该算法适合于当主串与子串不存在许多“部分匹配”时的情况,它是对串匹配算法中,一般算法和ＫＭＰ算法的补充。     

字符串匹配算法Sunday的改进

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

对KMP算法中模式串所构造自动机的改进

对发生失配现象时KMP算法中模式串所构造自动机的处理过程进行了分析，指出了其中状态函数的向后处理存在不足，并对此进行了相应的改进．     

KMP扫描算法的改进

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

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

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

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

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

一种改进的KMP算法

在给出改进的KMP模式匹配算法的定义和步骤的同时,对其进行了严格推导和证明.实验证明,当模式首次出现在文本后半段的情况下,该算法较原KMP算法具有更少的比较次数和更高的效率.     

一种针对网络流式文本数据的匹配算法

本文描述了一种对网络流式数据实时监控的搜索算法，应用有限自动机的原理．实现对任意长度数据流进行多关键字无回溯单遍匹配扫描，且加入概率计算，在一定程度上实现文本的简单模糊语义分析。该算法已被网络过滤软件使用，并有良好表现。     

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

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

一种改进的KMP入侵检测的模式匹配算法

提出了一种基于KMP的模式匹配算法,给出了具体的实现方法。在不丢失匹配项的前提下,增大next函数的值,使得模式串向右尽可能得滑动更远的一段距离,忽略不必要的比较。通过实验证明,该方法与传统的方法相比能有效地加快匹配的速度,提高入侵检测的效率。     

字符串匹配算法探讨

分析了BM和KMP算法特点,阐述了字符串匹配算法在文本处理领域、信息检索、语义学、分子生物学等学科中应用的意义,对字符串中最有影响的KMP算法、BM算法、RK随机算法和SUANDAY算法以及由此而产生的一些改进算法进行研究,实现了实验分析及功能对比,并指明各算法的适用性.