改进的多模式字符串匹配算法

Improved multiple patterns string matching algorithm

在经典的AC多模式字符串匹配算法的基础上,结合BMH算法的优点,提出了一种快速的多模式字符串匹配算法。一般情况下,该算法不需要匹配目标文本串中的每个字符,而是在实际比较之前跳过尽可能多的字符,以减少字符比较的操作,实现快速匹配。在模式串较长和较短的情况下,算法都有很好的性能。实验表明,在模式串较短时,本算法所需的时间仅为AC算法的50%～30%;在模式串较长时,所需时间为AC算法的26.7%～15.2%。

Combined with the advantage of the Boyer-Moore-Hoospool （BMH） algorithm, a faster algorithm for performing multiple patterns matching in a string was proposed on the basis of Aho-Corasick （AC） algorithm. In general, it does not need to inspect every character of the string. It skips as many characters as possible to decrease pattern match operations before matching patterns. The proposed algorithm achieves excellent performance in the cases of both short patterns and long patterns. Experimental results show that in case of short patterns the time it takes for the proposed algorithm to search a string is only 50% -30% that of the AC algorithm, while in case of long patterns the ratio is 26.7% - 15.2%.