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

在对著名的SunWu多模式串匹配算法进行分析之后,结合QS算法的优点,设计了一种较高效的多模式串匹配算法QMS.该算法使用散列技术和前缀表减少发生部分匹配时实际进行的模式串比较次数.在计算跳跃距离时,充分考虑当前窗口紧邻的下一个字符带来的信息,使用更加精确的跳跃距离计算方法以获得更大的平均跳跃距离,从而获得更高的扫描效率和空间利用率.在真实文本上的对比实验表明,在通常应用环境中,该算法缩短了扫描时间,取得了较好的效果.     

一种高效的多目标串匹配算法

本文通过引入右对齐位置标识方式解决了Boyer-Moore算法思想用于多串匹配的串长不等的问题，提出用于多模式串的高效匹配算法MP_BM。该算法的特点主要在于能够直接处理长度不等的多模式串匹配，同时又能获得很高的匹配效率。     

改进的多模式匹配算法

在有限自动机的多模式匹配算法（DFSA算法）的基础上，结合Quick Search算法的优点，提出了一个快速的多模式字符串匹配算法，之后在算法中以连续跳跃的思想，给出了另一个更加有效的改进，在一般情况下，这两个算法不需要匹配目标文本串中的每个字符，并充分利用了匹配过程是本次匹配不成功的信息，跳过尽可能多的字符，在模式串较长和较短的情况下，算法都有很好的性能，实验表明，在模式串较短时，所提出的算法需要的匹配时间仅为DFSA算法的1／2到1／5，在模式串较长时，所需时间为DFSA算法的1／3至1／7。     

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

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

     

一种改进的Boyer-Moore算法在IDS中的应用

在IDS的检测引擎模块设计中,基于Pattern-Matching的误用检测算法是设计师们最常用到的一种核心技术实现途径,而IDS丢包率和误报率的高低以及检测引擎匹配速度的快慢都取决于模式匹配算法性能的好与坏。Boyer-Moore算法及其改进了的Boyer-Moore Horspool算法和Boyer-Moore HorspoolS算法是目前应用最广泛的单模式匹配算法。在分析了 BM 算法及各种改进算法的基础上提出了一种新的基于BM算法的改进算法。该算法利用了字符串末字符和末字符对应文本串的下一字符的唯一性,同时考虑了文本串的信息以加大匹配速率,从而更好地适应IDS对模式匹配算法高效性的要求。     

基于坏字符序检测的快速模式匹配算法

提出一种基于坏字符序检测的快速模式匹配算法(BCSBM)。该算法利用相邻字符序列在模式串中不出现的概率较单字符高的特性,基于好字符和坏字符序表实现字符匹配过程的"跳跃"。BCSBM算法显著减少了匹配窗口内字符的匹配次数,同时增大了匹配窗口的平均移动距离。算法的实际测试效率较高,在文本或模式串相对较长的情况下该算法的效率提高明显。     

一种快速的单模式匹配算法*

在对Boyer-Moore(BM)算法及其改进的Tuned Boyer-Moore(TunedBM)算法进行分析的基础上,提出了一种更加快速的单模式匹配算法--NFS.该算法利用当前尝试中匹配失败字符的位置信息进行更大的尝试位置移动,使算法具有更高的效率.实验结果表明,NFS算法的性能优于同类的其他算法,特别是在模式长度较短的情况下,优势更为明显.     

基于KMP算法的改进算法KMPP

KMP算法和BM算法是经典的单模式匹配算法,但KMP算法中文本指针i每次只能移动一个字符,整体的匹配效率并不高,结合KMP算法和BM算法的优点提出一种改进算法(KMPP)。算法的思想是模式串与文本在j处不匹配时,预算出模式串移动next[j]后末字符在文本中的位置,当该位置的文本字符与末字符不匹配时,则用该字符进行坏字符匹配,这两步的跳跃距离就是文本指针i移动的距离,从而使指针i每次移动的距离达到最大。实验结果表明,该算法匹配次数远低于KMP算法的匹配次数,提高了模式匹配的效率。     

面向比特流的分组快速搜索匹配算法

在比特流的模式匹配中,由于目标串和模式串字符集简单,匹配过程中匹配窗口平均跳跃长度短,导致快速搜索(QS)匹配算法效率不高。为此,分析QS算法坏字符启发规则匹配效率与字符集大小的关系,借鉴编码QS算法的编码思想,提出一种对模式串进行分组预处理并使用字符组计算跳跃集的分组QS算法,给出坏字符组启发规则与最佳分组长度的计算方法。实验结果表明,与不分组的算法相比,该算法能够增加比特流模式串匹配中匹配窗口的平均跳跃长度,提高计算效率。     

对BM串匹配算法的一个改进

在对著名的Boyer-Moore串匹配算法进行分析后，对BM算法中的尝试位置移动处理部分进行改进，提出了IBM算法，该算法将好后缀移动与坏字符移动合并进行处理，从而尽量利用已有信息进行更大的尝试位置移动，使算法具有更高的效率，对IBM算法进行复杂度分析，对BM算法、KMP算法和IBM算法进行实际性能比较，结果表明IBM算法的平均运行时间明显优于BM算法与KMP算法。     

Boyer-Moore串匹配算法的改进

在分析Boyer-Moore (BM)算法的基础上，提出了BM算法的一个新的变形。其基本思想是在算法的预处理阶段，对扩展模式串Pa建立好后缀规则，其中：P是模式串，a是字母表中的任一字符，既加大了已匹配后缀的长度，同时隐含了Sunday算法的坏字符规则，从而获得更大的窗口跳跃距离。理论分析证明，该算法具有线性最差时间复杂度和亚线性平均时间复杂度，空间复杂度为O(m(σ+1))。实验结果表明，该算法的实际性能与BM算法相比有明显改善，尤其适合小字母表的情形。     

Fast string searching

Since the Boyer-Moore algorithm was described in 1977, it has been the standard benchmark for the practical string search literature. Yet this yardstick compares badly with current practice. We describe two algorithms that perform 47% fewer comparisons and are about 4.5 times faster across a wide range of architectures and compilers. These new variants are members of a family of algorithms based on the skip loop structure of the preferred, but often neglected, fast form of Boyer-Moore. We present a taxonomy for this family, and describe a toolkit of components that can be used to design an algorithm most appropriate for a given set of requirements.     

对BM模式匹配算法的一个改进

在分析BM算法的基础上，提出了一个改进的模式匹配算法QBM算法。该算法采用最长前缀的思想，在匹配后缀的时候采用一个位置移动表shift表代替BM算法中的两个移动表，提高了算法的运行效率。从理论和实践两个方面证明了该算法要优于BM算法。     

BWT Boyer Moore压缩域搜索算法的研究*

针对BoyerMoore匹配算法对压缩文本文件搜索的不足,分析了当前对于压缩文件搜索的主要方法,提出了一种基于BW转换的高效的搜索算法并予以验证。     

Snort研究及BM算法改进

Snort是一个轻型的入侵检测系统,在检测过程中,字符串匹配算法的效率决定了Snort系统的性能.分析了Snort的系统结构和工作流程,对Snort的BM字符匹配算法进行深入研究,提出了BM字符匹配算法的改进方法.实验数据表明,改进的BM字符匹配算法可提高Snort的效率.     

BM算法中函数shift的研究

建立BM算法中函数shift及其构造算法的严格的形式理论,对于BM算法及其各种变形的研究与改进是十分必要的。给出了shift的一个清晰的形式定义,引入模式串后缀的特征集及其最小值函数,通过特征集描述了shift的构造,从而严格建立了shift及其构造算法的理论基础。根据shift的构造定理与最小值函数的迭代计算方法,给出了shift的一个新的构造算法,证明了该算法具有线性的时间与空间复杂度。理论分析和计算结果表明,该算法比已有算法更简单,计算复杂度更低,因而更适合硬件实现。     

Improved string searching

We show that it is possible to improve the average time of the Boyer-Moore string matching algorithm using more space. This is accomplished by applying a transformation that virtually increases the size of the alphabet in use. The improvement is such that for long patterns it is possible to obtain an algorithm more than 50 per cent faster than the original one. We include experimental results on random and English text. Some improvements for searching on English text are also discussed.     

A mechanically verified incremental garbage collector

As an application of a system designed for concurrent program verification, we describe a formalisation and mechanical proof of the correctness of Ben-Ari's incremental garbage collection algorithm. The proof system is based on the Manna-Pnueli model of concurrency and is implemented as an extension of the Boyer-Moore prover. The correctness of the garbage collector is represented by two theorems, stating a) that nothing except garbage is ever collected (safety), and b) that all garbage is eventually collected (liveness). We compare our mechanised treatment with several published proofs of the same results.     

入侵检测中模式匹配算法的性能分析

模式匹配算法在入侵检测中有着广泛的应用，它直接影响到入侵检测系统的实时性能。论文主要研究了Boyer-Moore算法，Modified Wu—Manber算法，Exclusion—Based算法和Aho—Corasick算法。通过实验对上述四种算法在混合攻击和特定攻击的条件下进行了性能测试，根据实验结果，得出了不同算法的应用范围，为今后入侵检测系统开发者选择模式匹配算法提供了有价值的参考。