一种基于编码关联的快速多模式匹配算法  

Multi-pattern Matching Algorithm Based on Coding Association

作　　者：朱永强[1] 秦志光[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都611731

出　　处：《计算机科学》2016年第2期26-30,共5页Computer Science

摘　　要：多模式匹配算法经常使用有限自动状态机来实现多个模式串的并行匹配。针对基于自动状态机的多模式匹配算法在应用于中文编码时存在的存储空间膨胀问题,使用中文字符的拆分编码构造自动状态机,以优化算法自动状态机的存储空间,并利用中文编码的编码关联性,设计了一种基于编码关联跳转的失效跳转表,使用启发式跳跃规则提升匹配算法的时间性能。最后通过实验证明,中文编码环境下,相比于其它使用自动状态机的多模式匹配算法,改良算法拥有更小的空间消耗与更快的运行速度。Multi-pattern matching algorithms often use finite state automaton to implement parallel matching of multiple pattern strings.When multi-pattern matching algorithm based on finite state automaton is applied into the Chinese,it will lead to storage space expansion.Aiming to solve this problem,this improved algorithm constructs automatic state machine by using split coding of Chinese characters to save storage space and designs failure jump table based on coding association,and uses heuristic jumping rules to improve time performance of matching.Finally,compared to other algorithm,smaller space consumption and faster speed in Chinese environment of this improved algorithm were proved by simulation.

关 键 词：多模式匹配 DFSA算法 WM算法 DFSA-QS算法 编码关联 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]