一种改进的多模式匹配算法

发布时间：2018-05-05 10:42

本文选题：字符串匹配 + 有限状态自动机　；参考：《华中科技大学学报(自然科学版)》2005年S1期

【摘要】：在基于有限状态自动机的多模式匹配算法(DFSA算法)基础上,结合Tuned BM算法的优点,提出一种快速的多模式字符串匹配算法,实现了多模式匹配过程中不匹配字符的连续跳跃.在一般情况下,算法不需要匹配目标串中的每个字符,而是在实际比较之前跳过尽可能多的字符,以减少字符比较的操作,实现快速匹配.在模式串较长和较短的情况下,算法都有很好的性能.分析指出算法实际比较的字符数随着模式串长度的增加而下降,并随模式集的增大有所增多.实验表明,在模式串较短时,算法需要的匹配时间仅为AC算法的50%到33.3%,AQR算法的90%左右;在模式串较长时,所需时间为AC算法的25%至12.5%,AQR算法的75%左右.
[Abstract]:On the basis of multi-pattern matching algorithm based on finite state automata and combining the advantages of Tuned BM algorithm, a fast multi-pattern string matching algorithm is proposed, which realizes the continuous jump of mismatched characters in the process of multi-pattern matching. In general, the algorithm does not need to match each character in the target string, but skips as many characters as possible before the actual comparison, so as to reduce the operation of character comparison and achieve fast matching. When the pattern string is longer and shorter, the algorithm has good performance. It is pointed out that the number of characters compared with the algorithm decreases with the increase of the length of the pattern string and increases with the increase of the pattern set. The experimental results show that the matching time of the algorithm is only about 50% to 33. 3% of the AC algorithm when the pattern string is short, and 25% to 75% of the AC algorithm when the pattern string is longer.
【作者单位】：哈尔滨工业大学计算机网络与信息安全技术研究中心哈尔滨工业大学计算机网络与信息安全技术研究中心
【基金】：国家自然科学基金资助项目(60203021)
【分类号】：TP391.1

【共引文献】