串匹配算法中的自动机紧缩存储技术  

Automaton Compact Representation Technology in String Matching Algorithm

作　　者：杨毅夫[1,2] 刘燕兵[1,2] 刘萍[1] 郭莉[1] 

机构地区：[1]中国科学院计算技术研究所,北京100190 [2]中国科学院研究生院,北京100039

出　　处：《计算机工程》2009年第21期39-41,共3页Computer Engineering

基　　金：国家"973"计划基金资助项目(2007CB311100)

摘　　要：自动机是串匹配算法中常用的数据结构,对自动机实现紧缩存储可以节省算法空间。总结常用自动机紧缩存储方法,分析其原理、时间效率、空间效率和优缺点,给出各种方法与数据稀疏性之间的关系。运用紧缩存储方法实现基本AC算法,对随机数据和真实数据的实验结果证明该算法有效。Automaton is one kind of data structure often being used in string matching algorithms. By realizing compact representation of automaton, the algorithm space can be decreased. This paper summarizes several frequently used compact representations of automaton, analyzes their principles, time efficiencies, space efficiencies, merits and demerits, and gives relationships between above methods and sparsity character. It implements the basic AC algorithm with compact representation method, Experimental results of random and real data demonstrate the efficiency of this algorithm.

关 键 词：紧缩存储 自动机 串匹配 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]