【摘要】 随着互联网的日益强大,互联网上数据急剧增多,如何在海量的数据中快速准确地找到所需信息,就显得尤为重要,这就需要多模式串匹配算法。多模式串匹配算法在越来越多的领域里都有应用,比如:信息安全领域中,入侵检测系统、防火墙等,在医学领域、数据挖掘、信息检索等等领域中均有广泛的应用。AC算法在多模式串匹配算法中是一个能达到线性时间的算法,其算法效率较高,AC_QS算法是在AC算法基础上增加坏字符规则,进一步增加了AC算法的匹配效率,但其空间复杂度较高。本文在AC_QS算法的基础上,对算法预处理和匹配过程中继续优化,并对字典树存储时进行了优化,使算法在空间和时间复杂度上得到进一步优化,提高了算法性能。实验结果也验证了该算法的高效性。更多还原

【Abstract】 With the Internet becoming more and more powerful and the data increasing dramatically on the internet,it is very important to find the needed information quickly and accurately in the mass of data,so it is determined to require multipatterns string matching algorithm. Multi-patterns string matching algorithm has been used in more and more fields such as information security,intrusion detection system and firewall,data mining and medicine,and also has a wide range of applications in the field of information retrieval and so on. AC algorithm in multi-patterns string matching algorithm is a linear time algorithm,which can achieve high efficiency. AC_ QS algorithm is to increase the bad character in the AC algorithm and then improve the matching efficiency of AC algorithm,but its space complexity is high. In this paper,based on the AC_ QS algorithm,the algorithm will continue to optimize the preprocessing and matching process,and in the dictionary tree storage are optimized. After that,the algorithm in space/time complexity is further optimized,therefore the algorithm performance is improved. The experimental results also verify the efficiency of the algorithm.更多还原