摘要
在经典的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%.
出处
《计算机应用》
CSCD
北大核心
2007年第6期1415-1417,共3页
journal of Computer Applications
基金
国防基础科研项目(C2720061361)
国家863计划项目(2005AA147030)
关键词
字符串匹配
AC算法
BMH算法
多模式匹配
算法复杂度
string matching
AC algorithm
BMH algorithm
multiple patterns matching
computational complexity
