一种高速精确单模式串匹配算法

A Fast and Exact Single Pattern Matching Algorithm

串匹配问题是计算机科学的基础问题之一,是网络安全、信息检索与过滤、计算生物学等众多领域的核心问题,其中,高速精确单模式匹配算法设计又是各种串匹配问题的基础.基于SBNDM2,通过修改位掩码有效位到无符号整数的高位,将BNDM算法核心循环化简至最简形式(5指令/字符),并引入越界保护机制,提出S2BNDM系列精确单模式匹配算法.实验结果显示,S2BNDM系列算法在任何情况下都快于SBNDM2,对于英文语料(m<32)和DNA序列(m<8),S2BNDM系列算法为现有已知最快算法.

String matching problem is a fundamental problem in computer science. It is the key problem of many important scopes such as network security, information retrieval and filtration, computational biology, etc. And the design of exact single pattern string matching algorithm with high performance is the basis of all string matching problems. In this paper, the authors improve one of the fastest exact single pattern matching algorithms known on English text, which is SBNDM2. The simplest form of the BNDM core loop is obtained, in which there are only 5 instructions per character read by amending the relationship between position in the pattern and bit in the bitmask. And a cross-border protection method is added to the algorithm in order to reduce the cost of crossborder inspection. Two algorithms named S2BNDM and S2BNDM＇ are presented. The experimental results indicate that both S2BNDM and S2BNDM＇ are faster than SBNDM2 in any case. It can be considered that S2BNDM is the fastest algorithm on English text （2〈m≤12） /DNA sequence （2〈m≤8）, and S2BNDM＇ is the fastest algorithm on English text （13≤m〈32）.