摘要： 在Fan-Su(FS)多模式字符串匹配算法基础上，结合BM-Horspool(BMH)算法和Quick Search(QS)算法的优点，提出一种高效的多模式字符串匹配算法。该算法能够充分利用本次匹配失败和部分匹配成功的信息，一方面增加模式树根节点失配的概率，提高匹配过程中失配时的跳跃距离。另一方面避免不必要的状态转移，实现不匹配时的连续跳转。分析指出，在最好情况和平均情况下，时间复杂度均优于ACBM算法和FS算法。实验结果表明，一般情况下该算法的查找时间仅为AC算法的10%~35%， ACBM算法的50%~60%，FS算法的70%左右，FSQB算法的65%左右。
关键词:
字符串匹配,
多模式匹配,
有限自动状态机,
算法复杂度,
网络安全,
信息检索
Abstract: Combined with the advantages of BM-Horspool(BMH) algorithm and Quick-Search(QS) algorithm, an effective algorithm to perform multiple patterns matching in a string is proposed on the concept of Fan-Su(FS) algorithm. To reduce the number of comparisons, and improve the efficiency of matching, the proposed algorithm skips as many characters as possible and avoids useless state transitions, by making full use of the successful and failing information during the matching. Experimental results show that the proposed algorithm can achieve more excellent performance than the ACBM algorithm and FS algorithm. The time it takes for the proposed algorithm to search a string is only 10%~35% of the AC algorithm, 50%~60% of the ACBM algorithm, 70% of the FS algorithm, and 65% of the FSQB algorithm.
Key words:
string matching,
multiple patterns matching,
finite state automata,
algorithm complexity,
network security,
information retrieval
中图分类号: