共查询到18条相似文献,搜索用时 73 毫秒
1.
针对Wu-Manber算法在处理公共子后缀模式情况下的不足,该文提出了一种基于非空公共子后缀模式的处理算法。该算法把有非空公共子后缀的模式汇集在一起,进一步减小了next链表的平均长度。在匹配过程中减少了字符比较的次数,从而提高算法的运行效率。该文对搜狗实验室给出的相关文档进行全文检索实验,并和原Wu-Manber算法、孙晓山等提出的改进算法进行比较。实验结果表明,该文提出的改进算法有效地减少了匹配过程中字符比较的次数,从而提高匹配的速度和效率。 相似文献
2.
3.
多模式匹配是串处理系统中最重要的操作之一,而Wu-Manber算法是多模式串匹配算法中平均性能表现最好的算法.针对Wu-Manber多模式匹配算法在规则集中存在短模式串时性能下降的问题,提出一种按字长匹配的多模式匹配算法.改进的算法是在32位机器上实现,哈希的字符块长度取2,每次匹配的单位由原来的一个字符变为一个机器字,缩小了访存时间,同时利用机器字长存储的特点合理设计哈希函数,加快了字符块哈希值的计算,极大的提高了有短模式串存在时模式集的匹配性能.与原Wu-Manber算法对比,当最短模式串长度小于6时,改进后的算法搜索时间平均缩短了40%.当最短模式串长度为2和3时,搜索时间缩短了60%以上. 相似文献
4.
Wu-Manber算法是多模式匹配领域性能优越的算法之一.针对Wu-Manber算法不能很好的用于中文环境,以及滑动距离受限和冗余匹配的问题,提出一种改进的针对中文编码的WM_CH多模式匹配算法.WM_CH针对中文编码修改了哈希函数,优化了建立哈希表的过程;修改并优化了算法匹配过程,在执行精确匹配时消除了冗余匹配,增大了单次精确匹配后的滑动距离.实际测试表明,该算法性能优异,保持与原算法匹配精确度一致,针对中文编码能快速过滤非中文字符.在特征串集规模大于50 000时,匹配速度比原算法提升40%以上,同时滑动窗口的跳转次数显著下降. 相似文献
5.
6.
由于中英文字符在编码方面的差异,传统面向英文字符环境的多模式匹配算法无法直接应用于中英文字符混合环境。提出了一种适用于网络处理器和中英文混合环境的高效多模式匹配算法。该算法采用从左向右的正向匹配,以字节为最小匹配单位,以字符为最小移位单位,在Trie树结构基础上,利用块字符匹配降低逐字匹配的概率,结合Quick Search(QS)算法进行跳跃加速。实验表明,算法能够在中英文混合环境下避免字节错位和误匹配,匹配速度优于已有算法,且不存在空间膨胀问题,能够满足高速网络信息审计的要求。 相似文献
7.
在Fan-Su(FS)多模式字符串匹配算法基础上,结合BM-Horspool(BMH)算法和Quick Search(QS)算法的优点,提出一种高效的多模式字符串匹配算法。该算法能够充分利用本次匹配失败和部分匹配成功的信息,一方面增加模式树根节点失配的概率,提高匹配过程中失配时的跳跃距离。另一方面避免不必要的状态转移,实现不匹配时的连续跳转。分析指出,在最好情况和平均情况下,时间复杂度均优于ACBM算法和FS算法。实验结果表明,一般情况下该算法的查找时间仅为AC算法的10%~35%,ACBM算法的50%~60%,FS算法的70%左右,FSQB算法的65%左右。 相似文献
8.
随着网络技术快速发展,多模式匹配算法所处理的模式集合数目呈爆炸式增长且模式长度不统一,传统的多模式匹配算法已无法有效适应新的模式集合:不同的模式集合,同一算法呈现的性能差异明显。针对模式长度不等且分布不均匀的模式集合,提出一种改进WM的多模式匹配算法(MWM),将模式集合分为长短两个集合并构造各自的长短SHIFT表,辅助WM算法原有SHIFT表验证匹配效果,匹配过程由单一线程完成。该算法不仅减少了模式验证次数,而且提高了算法的平均跳转距离。实验结果表明,所提出的多模式匹配算法(MWM)在模式长度不等且分布不均匀的模式集合下表现出更优的性能,随着模式集合的数目增多,性能提升越明显。在模式集合数目达到100 000时,相比WM算法,该算法性能提升达到了40%。 相似文献
9.
在分析了BM模式匹配算法的基础上,提出了一种新的字符串单模式匹配算法,该算法通过对模式中的字符进行等级划分,设置模式中各个字符的优先级,改进模式串的移动方式,减少了模式匹配的次数和字符比较的次数,有效的提高了模式匹配的效率。实验显示,该算法有效的提高了模式匹配的效率。 相似文献
10.
11.
本文提出了一种对XML 文本进行快速串匹配的算法- XMatch。在对于XML 文本的含路径信息的模式串匹配中,由于XML 文本的结构化特点,使得传统的串匹配算法不能直接有效的使用;而现有的大部分XML 内容筛选方法都是基于SAX 分析的事件驱动过程,效率普遍较低。XMatch 在对XML 文本的结构-schema 进行分析的同时,结合模式串的路径信息,建立一个扫描自动机的有限状态自动机;此外,算法还支持带循环引用路径信息的模式串匹配。XMatch 容易扩展,可以支持普通的结构化文本的串匹配。实验结果显示,本算法的效率比使用SAX事件驱动的方法有明显的提高。 相似文献
12.
快速中文字符串模糊匹配算法 总被引:9,自引:3,他引:9
本文解决了中文字符串模糊匹配的两个主要问题:空间问题和时间问题。目前字符串模糊匹配的两个主要方法是位向量方法和过滤方法。由于汉字众多,应用位向量方法时,需要大量空间。对于某些内存很少的小型计算机,比如嵌入式系统,这将会是一个问题。本文改进了位向量方法,使其在应用于中文字符串时,空间需求降低到约5%。本文还利用汉字非常多的特点,提出一种新的基于过滤方法的中文字符串模糊匹配算法,BPM-BM,其速度比世界上最快的算法至少提高14%;在大部分情况下,是其速度的1.5~2倍。 相似文献
13.
针对入侵检测系统针对入侵检测系统对基于攻击特征的网络数据包的检测效率低和丢包率高的问题,在分析典型的模式匹配算法的基础上,结合入侵检测模式匹配特点,提出了一种改进的匹配算法。首先找到模式串中无重复字符集,然后在目标串中找到字符集中出现频率最小的字符进行目标串的模式匹配。实验证明,此算法对于入侵检测的模式匹配具有良好的匹配效率。 相似文献
14.
在分析传统的模板匹配算法的基础上提出了一种新的基于字符串匹配的快速匹配算法。算法的思路是在模板图像上任意确定一列像素,并将这一列像素的灰度值看成是一个字符串,以此对原图像的每一列进行字符串匹配。如果在原图像上的某一列上找到了完全匹配的串,或者找到最大匹配的串,就找到了所要匹配的模板在图像中的可能位置。然后在所有找到的位置上再做进一步的字符串匹配。如此继续就可以确定模板图像在待匹配图像上的位置。算法在统计意义上保证了匹配效果,且提高了匹配速度。实验结果表明该算法是一种有效的图像匹配算法。 相似文献
15.
16.
17.
18.
用于文本分类的改进KNN算法 总被引:2,自引:2,他引:2
最近邻分类器是假定局部的类条件概率不变,而这个假定在高维特征空间中无效。因此在高维特征空间中使用k最近邻分类器,不对特征权重进行修正就会引起严重的偏差。本文采用灵敏度法,利用前馈神经网络获得初始特征权重并进行二次降维。在初始权重下,根据样本间相似度采用SS树方法将训练样本划分成若干小区域,以此寻找待分类样本的近似k0个最近邻,并根据近似k0个最近邻和Chi-square距离原理计算新权重,搜索出新的k个最近邻。此方法在付出较小时间代价的情况下,在文本分离中可获得较好的分类精度的提高。 相似文献