| 一种高效的多模式字符串匹配算法 |
| |
| 引用本文： | 许家铭,李晓东,金健,马盈. 一种高效的多模式字符串匹配算法[J]. 计算机工程, 2014, 0(3): 315-320,F0003 |
| |
| 作者姓名： | 许家铭 李晓东 金健 马盈 |
| |
| 作者单位： | [1]中国互联网络信息中心,北京100190 [2]中国科学院计算机网络信息中心,北京100190 [3]中国科学院大学,北京100190 [4]东北师范大学理想信息技术研究院,长春130117 |
| |
| 基金项目： | 国家自然科学基金资助项目“多模态Web作弊间的统计机器学习方法研究”（61005029）. |
| |
| 摘 要： | 在Fan-Su(FS)多模式字符串匹配算法基础上,结合BM-Horspool(BMH)算法和Quick Search(QS)算法的优点,提出一种高效的多模式字符串匹配算法。该算法能够充分利用本次匹配失败和部分匹配成功的信息,一方面增加模式树根节点失配的概率,提高匹配过程中失配时的跳跃距离。另一方面避免不必要的状态转移,实现不匹配时的连续跳转。分析指出,在最好情况和平均情况下,时间复杂度均优于ACBM算法和FS算法。实验结果表明,一般情况下该算法的查找时间仅为AC算法的10%~35%,ACBM算法的50%~60%,FS算法的70%左右,FSQB算法的65%左右。
|
| 关 键 词： | 字符串匹配 多模式匹配 有限自动状态机 算法复杂度 网络安全 信息检索 |
An Efficient Multiple Patterns String Matching Algorithm |
| |
| XU Jia-ming,LI Xiao-dong,JIN Jian,＇,MA Ying. An Efficient Multiple Patterns String Matching Algorithm[J]. Computer Engineering, 2014, 0(3): 315-320,F0003 |
| |
| Authors: | XU Jia-ming LI Xiao-dong JIN Jian ＇ MA Ying |
| |
| Affiliation: | 4 (1. China Internet Network Information Center, Beijing 100190, China; 2. Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China; 3. University of Chinese Academy of Sciences, Beijing 100190, China; 4. Ideal Research Institute of Information Technology, Northeast Normal University, Changchun 130117, China) |
| |
| 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. |
| |
| Keywords: | string matching multiple patterns matching finite state automata algorithm complexity network security informationretrieval |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
