摘要： 自动机是串匹配算法中常用的数据结构，对自动机实现紧缩存储可以节省算法空间。总结常用自动机紧缩存储方法，分析其原理、时间效率、空间效率和优缺点，给出各种方法与数据稀疏性之间的关系。运用紧缩存储方法实现基本AC算法，对随机数据和真实数据的实验结果证明该算法有效。

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

Abstract: 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.

Key words: compact representation, automaton, string matching

中图分类号: 

• TP311.12