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

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

一种改进的针对中文编码的Wu-Manber多模式匹配算法

Wu-Manber算法是多模式匹配领域性能优越的算法之一.针对Wu-Manber算法不能很好的用于中文环境,以及滑动距离受限和冗余匹配的问题,提出一种改进的针对中文编码的WM_CH多模式匹配算法.WM_CH针对中文编码修改了哈希函数,优化了建立哈希表的过程;修改并优化了算法匹配过程,在执行精确匹配时消除了冗余匹配,增大了单次精确匹配后的滑动距离.实际测试表明,该算法性能优异,保持与原算法匹配精确度一致,针对中文编码能快速过滤非中文字符.在特征串集规模大于50 000时,匹配速度比原算法提升40%以上,同时滑动窗口的跳转次数显著下降.

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

针对Wu-Manber算法在处理公共子后缀模式情况下的不足,该文提出了一种基于非空公共子后缀模式的处理算法。该算法把有非空公共子后缀的模式汇集在一起,进一步减小了next链表的平均长度。在匹配过程中减少了字符比较的次数,从而提高算法的运行效率。该文对搜狗实验室给出的相关文档进行全文检索实验,并和原Wu-Manber算法、孙晓山等提出的改进算法进行比较。实验结果表明,该文提出的改进算法有效地减少了匹配过程中字符比较的次数,从而提高匹配的速度和效率。

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

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

Wu-Manber算法性能分析及其改进

在模式匹配中,多模式匹配算法越来越受到人们的关注。本文首先介绍了一些著名的多模式匹配算法,重点介绍了Wu-Manber算法的基本概念及其实现原理,此算法在实践应用中是最有效的。然后提出了对Wu-Manber算法的改进,以解决多模式串长度很短时出现的性能问题。最后,实验数据表明,改进后的Wu-Manber算法,其性能远远优于传统的Wu-Manber算法。

基于Wu-Manber的快速跳跃多模式匹配算法

海量信息处理以及网络入侵检测等应用都对串匹配技术提出了新的挑战。在分析多模式匹配的Wu-Man- ber算法之后,提出一种基于WM的快速跳跃多模式匹配算法。该算法采用增大跳跃距离、减少冗余移动的方法,提高了WM算法的查找效率。试验数据表明该算法的查找时间比WM算法减少了5-9%。

Wu-Manber算法的改进研究

Wu-Manber算法是一种经典的多模式字符串匹配算法,常用于解决网络入侵检测等问题。为了解决Wu-Manber算法在模式集规模增长时,prefix表中会出现过长的模式链表这一问题,通过改变原有prefix表中的链表结构以及存储信息的格式,提出两种改进算法,分别用于处理较小的模式集合和较大的模式集合。实验证实了改进算法可以提高字符串匹配速度,具有很高的实用价值。

基于CUDA的Wu-Manber多模式匹配算法

多模式匹配是计算机科学中最基本的问题,其应用在许多领域,在一些情形下也是比较耗时的。GPU拥有比CPU更强的并行计算能力,随着CUDA架构的推出,GPU用于通用计算领域的并行编程工作变得更加轻松。实现了基于CUDA架构的Wu-Manber多模式匹配算法,实验结果表明,相比传统串行算法而言,本文的实现获得了10倍以上的加速。

基于Wu-Manber算法的大规模URL模式串匹配算法

大规模高速URL匹配是许多网络安全系统中的关键技术,经典串匹配算法在大规模URL情况下有许多限制。针对URL数据的特点在经典多模式串匹配算法Wu-Manber基础上提出XWM-Tree算法和XWM-Hash算法。算法应用了模式串窗口选择,两阶段哈希和关联容器组织冲突链表等多种优化手段,大幅度提高了算法的匹配性能。在大规模真实数据集上的测试结果表明本文提出的算法匹配速度可以提高一倍以上,尤其是当最短模式串较长的时候更有优势。

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

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

基于Wu反走样的三角形光栅化边缘反走样算法

对于光栅化的三角形,其边缘存在明显的锯齿现象,因此需要进行反走样处理。基于Wu直线反走样算法的思想,考虑了水平直线外侧直接添加插值点的算法和三角形三边外侧反走样的算法。综合两者的优点,在绘制光栅化的三角形的同时,边缘叠加Wu反走样直线,并考虑背景像素灰度值的作用。结果表明,改进的三角形光栅化的边缘反走样算法有效提高了三角形光栅化后边缘的显示效果,该算法计算量小,便于FPGA实现,可用于对图形显示质量要求很高的机载显示系统。

小角度直线反走样的改进Wu算法

直线是机载座舱显示画面中最基本的图元,其显示质量对于整个画面的显示效果影响较大,尤其是小角度下直线显示的"麻花"现象一直是影响显示效果的关键问题之一。为了提高小角度下直线的显示效果,本文提出了一种基于Wu算法的亮度渐变改进算法。该算法通过渐进地展现直线从轴方向上的亮度变化过程,减少亮度畸变,有效地改进了显示效果。通过Matlab仿真和FPGA实现,验证了该算法反走样后的小角度直线显示效果明显优于其他算法,而且结合中点画线法后,绘制时间与Wu算法相当。同时该算法还可改善大角度直线和圆弧的显示效果,消除了大角度直线的边缘锯齿,解决了圆弧在小角度部分的虚化问题。因此本文算法可用于对实时性和显示效果要求高的机载座舱显示系统,以缓解飞行员的视觉疲劳。

一种面向入侵检测的快速多模式匹配算法

随着网络速度和入侵检测规则的持续增长，模式匹配正在成为网络入侵检测系统的性能瓶颈。提出了一种新的Wu-Manber类型的模式匹配算法，通过将模式分组，对不同予模式组采用不同匹配方法，显著提高了模式匹配的效率。对比实验表明，当模式组中含有长度小于3的模式时，新算法性能比原算法平均提高了29％-44％。

入侵检测系统中模式匹配算法的研究与改进

入侵检测系统的性能很大程度上取决于规则检测的效率,模式匹配算法是规则检测引擎的核心算法。对模式匹配算法进行了研究,重点分析了多模式匹配算法Wu-Manber算法。针对Wu-Manber算法在单字节模式串下移动距离短的不足,并结合网络数据包和入侵检测系统中规则的特点,提出了一种适合入侵检测系统的改进的模式匹配算法。该算法利用位示图方法解决了单字节模式串匹配的问题,增加了移动距离,提高了检测数据包与规则匹配的速度,提升了系统运行的效率。

一种基于分段匹配的字符串匹配算法

针对已有算法对文本和模式的相关性依赖较大,提出一种基于分段的字符串匹配算法——SM。该算法利用特殊字符将文本先分段再匹配,且匹配过程对模式内容和长度不敏感。通过将SM算法与经典算法进行分析和实验对比,证明SM算法性能稳定,特别是在多模式字符串匹配情况下,SM算法具有比Wu-Manber算法更快的速度和更小的空间消耗。

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

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

三像素宽反走样直线的绘制算法研究

直线绘制是计算机图形学的基本内容。在光栅图形显示系统中 ,要快速绘制无锯齿的光滑直线是很困难的。本文从走样的机理入手 ,在对 Wu反走样直线算法和 Gupta &Sproull圆锥滤波反走样算法进行研究的基础上 ,提出了改进的三像素宽度直线反走样算法 ,用于显示高质量的反走样直线 ,应用于飞机座舱显示系统中全罗盘画面的刻度线绘制 ,取得了较好的应用效果。

多模式匹配算法及硬件实现

介绍了多模式匹配的算法和硬件实现方法.首先介绍了两种常用的多模式匹配算法——Aho-Corasick基于自动机的算法和Wu-Manber基于hash的后缀匹配加移位跳跃的算法以及相关的改进算法.并通过实验对各种多模式匹配算法的时空复杂度进行了分析比较.通过几个硬件实现的实例介绍了多模式匹配的硬件实现方法及策略.最后对多模式匹配的发展趋势进行了展望.

基于FPGA的直线反走样算法研究

反走样是计算机图形学的基本问题。为了提高直线反走样的效率,针对FPGA硬件实现的特点,结合经典的Wu反走样算法,提出一种新的直线反走样算法。该算法根据像素点中心到理想直线的距离来计算灰度值,在生成直线时预测直线相邻像素点之间的灰度值变化,并建立递推公式,使用整数移位、加法和比较来完成直线反走样,计算简单,便于硬件实现。经计算机和FPGA分别实现验证,新算法的反走样效果较好,运算速度快于Wu反走样算法并能通过FPGA进一步提高速度。

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

针对WM算法的查找效率随着模式集规模的增大而降低的问题,提出一种改进算法。在预处理阶段,改变原有Hash表中的链表结构,采用双哈希法将模式串存放在Hash1表中指定的区间,Hash表中存放该存储区间的起始位置与区间长度;Prefix表用于判断模式集中是否存在与当前匹配窗口中文本前缀相同的模式;当Shift表中出现移动值为0时,根据后缀出现在模式串其他位置的信息计算匹配窗口可滑动的最大距离并存于Shift1表中。在查找阶段,采用双哈希法在Hash1表的某一区间中查找模式串,避免在大规模模式集情况下查找过长的模式链表,扩大匹配操作后匹配窗口滑动的距离,减少冗余的匹配操作,缩短查找时间。研究结果表明:在模式集规模较大时,改进后的算法显著地提高了匹配速度;当模式串数目超过5 000条时,改进算法的查找时间要比WM算法缩短40%～47%。