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

• 作者: 方滨兴 殷丽华
• 来源期刊: 华中科技大学学报（自然科学版）
• 学科: 工学
• 关键词: 字符串匹配 有限状态自动机 Tuned BM算法 多模式匹配 算法复杂度
• 年，卷（期）: 2005,（z1）
• 所属期刊栏目: 信息安全与可信计算
• 页码范围: 300-303
• 页数: 4页
• 分类号: TP311
• 字数: 2718字
• 语种: 中文
• DOI: 10.3321/j.issn:1671-4512.2005.z1.084

摘要

在基于有限状态自动机的多模式匹配算法(DFSA算法)基础上,结合Tuned BM算法的优点,提出一种快速的多模式字符串匹配算法,实现了多模式匹配过程中不匹配字符的连续跳跃.在一般情况下,算法不需要匹配目标串中的每个字符,而是在实际比较之前跳过尽可能多的字符,以减少字符比较的操作,实现快速匹配.在模式串较长和较短的情况下,算法都有很好的性能.分析指出算法实际比较的字符数随着模式串长度的增加而下降,并随模式集的增大有所增多.实验表明,在模式串较短时,算法需要的匹配时间仅为AC算法的50%到33.3%,AQR算法的90%左右;在模式串较长时,所需时间为AC算法的25%至12.5%,AQR算法的75%左右.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	方滨兴	哈尔滨工业大学计算机网络与信息安全技术研究中心	175	3885	33.0	56.0
2	殷丽华	哈尔滨工业大学计算机网络与信息安全技术研究中心	11	263	8.0	11.0