字符串匹配是一个在很多信息处理技术中都必须面对的问题，在入侵检测技术中由为突出，而其相关的研究也已经开展了多年，一些经典的算法已经在很多入侵检测系统中得以广泛应用。但现有的一些算法都或多或少地存在某些局限或不足。为此，相关的研究仍在继续。在总结前人经验成果的基础上，本文提出了自己的新的想法，并将新的想法通过算法加以实现，最后通过实验验证了算法的正确性和提高之处。由于目前没有任何一种字符串匹配算法能够适应各种情况，达到最好、最坏及平均时间复杂度都达到最优，只是理论上存在上述的可能。因此本文提出的算法只是对前人算法的一种改进，让新的算法更适合于多字符串并行查找，以及适应动态地增加模式字符串的情况。具体说来，本文得到如下的成果：其一：提出一个分割定理，证明了通过非“准匹配”字符可以将大文本分割为若干个用于匹配的小文本。其二：提出一个采样定理，证明了针对某一模式串，当采样距离小于模式串长度时，我们可以通过抽样检测的方式，发现文本中模式串出现的位置。其三：实现了一个依据采样定理思想来设计的算法，并通过算法进一步证明了采样定理的正确性。其四：将这一算法，应用到入侵检测的入侵识别引擎当中，用于规则匹配。并提高了检测引擎的效率。
本文来源: https://www.lw50.cn/article/c1cad7c1f8a67af9124b938e.html