论文部分内容阅读
模式匹配是计算机应用领域重要的研究方向之一,广泛应用于入侵检测、信息检索、生物科学等方面。随着计算机网络技术的飞速发展,信息量呈爆炸式增长,如何提高模式匹配算法的性能成为了信息检索、内容过滤等领域研究的热门课题。本文介绍了几种重要的模式匹配算法,包括单模式匹配和多模式匹配算法,如BF算法、BM算法、QS算法和AC算法、AC_BM算法、WM算法等,分析了它们的时间性能,并比较了各自的优缺点。随着中文模式串数目的增加,基于有限状态自动机的多模式匹配算法的存储空间会快速膨胀,goto函数以及查询跳转距离的计算量大,从而导致算法的时空性能急剧下降。针对该问题,本文提出了带跳转距离的邻接链表存储方式,为每一状态建立一个单链表,所有单链表与顶点表构成邻接链表,并与跳转距离表融为一体,可同时完成状态与跳转距离的查询,提高了算法的时空效率。基于带跳转距离的邻接链表存储方式,设计了一种适合中文的多模式匹配算法—AC_SC算法,并分析了AC_SC算法的时空性能。最后,对有限状态自动机不同存储方式的时空性能和不同跳跃式匹配算法的时间性能进行了测试。实验结果表明,本文提出的带跳转距离的邻接链表存储方式,其空间性能远优于完全Hash表和状态矩阵存储方式,时间性能优于状态矩阵存储方式,略低于完全Hash表存储方式。AC_SC算法的平均跳转距离和时间性能优于AC_Tuned BM算法、AC_WM算法及IACBM算法,适合大规模中文模式匹配。