实时信息处理中多模式串匹配算法的研究

发布时间：2018-10-04 20:31

【摘要】：字符串匹配是计算机科学与工程中的基本问题之一,应用范围极为广泛,尤其是在计算生物学,网络安全,信息过滤等重要领域中是性能瓶颈。现如今随着信息化的高速发展,网络流量增速已超出摩尔定律的约定范围,仅通过硬件改进的方式进行以上领域的性能的提高并不现实,所以必须研究方法更新、速度更快、性能更好的字符串匹配算法,以提高多领域中实时信息处理的速度。单模式和多模式串匹配,是字符串领域研究的基础,本文对此展开研究。单模式字符串匹配是模式匹配领域中的基础研究课题,并拥有着悠久的历史,其中著名的单模式字符串匹配算法,包括:KMP算法(Knuth-Morris-Pratt算法)和BM算法(Boyer和Moore算法)等,二者的最坏时间复杂度分别为:O(n)和O(mn)。多模式字符串匹配算法相对于单模式字符串匹配算法,不单单增多了匹配模式的个数,也增多了应用的范围,尤其在实时信息处理的领域中受到非常多的关注,最为经典的算法为AC算法(Aho-Corasick算法)。本文主要工作总结为以下几个方面:第一,对字符串匹配算法的研究课题进行了总结和分析,总结出了传统模式串匹配算法的优缺点,包括:精确串匹配,正则表达式匹配,近似串匹配等,对字符串匹配的关键性能参数即时空复杂度进行总结分析。第二,提出以整数为单位的比较方法,对后缀类字符串匹配算法进行方法改进,结合几种方法机制,其中,第一种机制是多窗口机制,并给出双窗口和多窗口机制的示意图,对其提高性能的原因进行了详细的分析和总结;第二种机制是非对齐整数读机制,分析该机制的工作原理以及具体的操作方式;第三种机制是q-grams方法机制,并总结了该机制应用于模式匹配的优势。根据以上提出的方法,首先,提出了基于多窗口和非对齐整数读机制的QSMI系列算法和TBMMI系列算法,然后,提出基于q-grams机制的改进的BMHq算法,通过实验均证实了以上的改进算法在时空复杂性方面达到最优。第三,提出基于整数比较的改进型BOM类算法,其中提到了基于后缀的FO自动机以及UnrollingFO自动机的构建方法,在改进方法中融合了 q-grams方法机制和非对齐整数读方法机制,其中,利用q-grams机制增加算法的跳跃距离,利用非对齐整数读方法机制简化查表操纵,分别提出了q= 的BOMq算法,EBOM_sb系列算法和BOMq_sb系列算法,并给出自动机构建代码和BOM3算法以及BOM3__2sb算法的实现伪代码,并给出相应的实验结果数据以便后续分析总结。第四,对经典多模式串匹配AAC算法进行详细介绍,由于其匹配时消耗较大空间,且在发生失配时,查找output表的操作过于复杂,本文基于AAC算法的基础上,提出 AACA(Advanced AC with Additive State)算法和 AACN(Advanced AC with Negtive State)算法,二者虽然与AAC算法在构建自动机的方式上是一致,但是,AACA算法和AACN算法分别通过转移和改变相应状态,达到省略查找output表的操作,最后通过实验证实,两种改进后的多模式串匹配算法,在小规模模式集合中进行匹配时,能得到很好的性能。最后,在提出的改进算法的各章节的最后,给出了所做的相关实验,实验分析和实验数据的结果展示,充分证实改进算法的性能最优,并进行工作总结。
[Abstract]:......
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP391.1

【参考文献】