Wu-Manber算法在大规模模式串下的改进

对笔者在另一篇文章《一种改进的Wu-Manber多关键字匹配算法》中提出的算法进行了改进,把原算法中next链表中结点的Same-Subsuffix域中分裂成两个子域,使得搜索过程中字符比较的次数进一步减少,从而提高算法的效率.特别是在大规模模式串的情况下新算法的效率比原算法有进一步的提高.实验结果表明,当模式串较少时,新算法效率与原算法相比有一定的损失.而随着模式串的增加,新算法具有更高的效率.因此,新的算法比原算法具有更大的适用范围.     

Wu-Manber算法的一种综合改进

对孙晓山等提出的Wu-Manber算法的后缀改进算法作进一步的改进,在对next链表进行分类的同时把含有互为后缀的结点提到链表的前部,并整合了张鑫提出的精神的不良字符转移和弱化的良好后缀转移的改进方法,新改进的算法充分利用以上两种算法的优点,使区配过程中字符比较好的次数得到了进一步减少.新改进的Wu-Manber匹配算法在实验中取得了更高的效率.     

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

为提高串匹配算法在实际应用中的运算性能,对W u-M anber算法进行了改进。吸收了Q S(Q u ick Search)算法的思想,并利用匹配过程中匹配失败的信息,达到最大跳跃距离,实现了快速的多模式匹配算法。对改进后的算法和W u-M anber算法进行对比实验,当最小模式长度较大时,改进后的算法性能与原算法基本相同;而当模式最小长度较小时(<9),改进后的算法比原算法有显著提高,用于英文文本时比原算法的所用时间平均减少了8%~20%,用于中文文本时平均减少了15%~30%。     

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

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

一种改进的多关键字匹配算法

基于多关键字匹配的Sun Wu算法进行的分析,结合Qs算法的思想,设计了一种改进的多关键字匹配算法：QMS（quick multi-pattern searching）。算法使用散列技术和前缀表减少发生部分匹配时实际进行的关键字比较次数。在计算跳跃距离时,充分考虑当前窗口的紧邻下一个字符带来的信息,进而使用更加精确的跳跃距离计算方法以获得更大的平均跳跃距离,从而获得更高的扫描效率和空间利用率。在真实文本上的对比实验表明,在通常应用环境中,该算法显著的缩短了扫描时间,取得了很好的效果。     

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

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

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

字符匹配效率是很多计算机应用系统的性能瓶颈,研究设计高效的匹配算法有助于提高相应系统的应用性能。在分析典型Sunday匹配算法的基础上,对其进行了较为有效的改进。改进算法在字符串匹配前先计算模式串的倒序特征值,也就是以此计算出模式串的最后s个字符在本模式串中倒序除自己以外的下一次出现的位置。每一次字符匹配都采用倒序匹配并利用这种匹配的结果,匹配结果结合倒序特征值可以直接决定特征串的下一次位移数。在进行完一次字符匹配后,采用增加一个遍历字符的Sunday算法来遍历模式串以计算下一次位移数,以此尽可能地排除无效匹配。实验结果表明改进算法的效率比Sunday算法有一定提高。     

KMP扫描算法的改进

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

串匹配的一个新算法

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

基于改进GST算法的字符串相似度检测

为了降低贪婪模式匹配(GST)算法的运行时间,提高字符串相似度检测效率,提出一种将改进KR算法与GST相结合的字符串相似度检测算法.以学生作业源代码作为实验数据,对改进算法和GST算法进行了性能测试,结果表明,改进算法能够在较少的比较次数情况下达到与GST算法类似的查重结果.     

一种快速的字串交叉模式匹配算法

介绍了一种基于高频字串提取的快速字串交叉模式匹配算法,同已有的KMP,BM等单模式匹配算法和有限自动机等多模式匹配算法相比,在字符集∑较大且字串个数远大于字串最大长度的情况下,该算法具有较低的时间复杂度和空间复杂度,并适用于字符集较大,词长较短的文本处理。     

Horspool扩展算法在方块苗文模式匹配中的应用

分析了Horspool算法的原理及特点,提出了一种适用于方块苗文环境的字符串模式匹配算法.该算法结合方块苗文的编码方式及字符串查找的特点,通过对Horspool算法中的字符处理单位进行扩展来适应方块苗文的字符串匹配.实验结果表明,在单字词、双字词和多字词的方块苗文字符串匹配过程中,该算法均呈现出较好的性能,能够用于解决方块苗文的快速检索问题.     

模式匹配在中文问答系统中的应用研究

针对汉语文本,对自动问答系统的实现进行了初步探索,主要是基于向量空间模型对文档信息进行检索,重点研究了模式匹配在判断问句类型和获取答案方面的作用,设计并初步实现了一个面向受限领域内中文自动问答系统。     

A Single Pattern Matching Algorithm Based on Character Frequency

Based on the study of single pattern matching, MBF algorithm is proposed by imitating the string searching procedure of human. The algorithm preprocesses the pattern by using the idea of Quick Search algorithm and the already-matched pattern psefix and suffix information. In search-ing phase, the algorithm makes use of the! character using frequency and the continue-skip idea.The experiment shows that MBF algorithm is more efficient than other algorithms.