快速的多模式匹配算法.pdfVIP

第39卷 第l2期 哈 尔 滨 工 业 大 学 学 报 V01．39 No．12 2 0 0 7年l2月 JOURNAL OF HARBIN INSTITUTE OF TECHNOLOGY Dec．20H07 快速的多模式匹配算法 殷丽华，方滨兴，张宏莉 (哈尔滨工业大学计算机网络与信息安全技术研究中心，哈尔滨150001，E—mail：yinlh@hit．edu．cn) 摘 要：在基于有限状态自动机的多模式匹配算法(DFSA算法)基础上，结合Tuned BM算法的优点，提出 一 个快速的多模式字符串匹配算法，实现了多模式匹配过程中不匹配字符的连续跳跃．在此基础上进一步改 进，得到一个最差时间复杂度为线性的匹配算法．分析指出算法实际比较的字符数随着模式串长度的增加而 下降，并随模式集的增大有所增多．实验表明，在模式串较短时，算法需要的匹配时间仅为AC算法的1／2到 1／3，AQR算法的9／10左右；在模式串较长时，所需时间为AC算法的1／4至1／8，AQR算法的3／4左右． 关键词：字符串匹配；有限状态自动机；Tuned BM算法；多模式匹配；时间复杂度 中图分类号：TP311 文献标识码：A 文章编号：0367—6234(2007)12—1925—05 Improved algorithms for multiple patterns matching YIN Li—hua，FANG Bin—xing，ZHANG Hong—li (Research Center of Computer Network and Information Security Technology，Harbin Institute of Technology， Harbin 1 50001，China，E—mail：yinlb@hit．edu．cn) Abstract：Combined with the advantages of the Tuned Boyer—Moore algorithm，an effective algorithm for per- forming multiple patterns matching in a string was put forward on the concept of determ inistic finite state automa— ta(DFSA)，and achieved better performance by shifting unmatched characters consecutively．Experimental re— sults indicate that，to search a string，the algorithm takes only 1／2～1／3 that of AC and 9／10 of AQR in case of short patterns while the ratio is 1／4～1／8 and 3／4 in case of long patterns． Key words：string matching；finite state automaton；Tuned BM algorithm；multiple patterns matching；con— putational complexity 在单模式匹配算法中，Boyer—Moore算法¨ 位置．时间复杂度在最优和最坏情况下均为 (简称BM算法)是一种经典的跳跃式匹配算法． O(／Z)．Jang—Jong Fan和Keh—Yih Su将BM算 Qs算法 是BM的一种简化形式，充分利用了模 法和自动机算法结合并进行改进得到的Fs算 式串中本次匹配不成功的信息，实现文本的快速 法 ，王永成等在自动机算法的基础上结合QS 匹配．Tuned BM算法 也是BM的简化实现． 算法的思想，并进行改进得到的反向跳跃自动机 多模式匹配中比较经典的算法是Aho—Cora