CAJ | 학술논문

自动机是串匹配算法中常用的数据结构,对自动机实现紧缩存储可以节省算法空间.总结常用自动机紧缩存储方法,分析其原理、时间效率、窄间效率和优缺点,给出各种方法与数据稀疏性之间的关系.运用紧缩存储方法实现基本AC算法,对随机数据和真实数据的实验结果证明该算法有效.
자동궤시천필배산법중상용적수거결구,대자동궤실현긴축존저가이절성산법공간.총결상용자동궤긴축존저방법,분석기원리、시간효솔、착간효솔화우결점,급출각충방법여수거희소성지간적관계.운용긴축존저방법실현기본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 efficieneies, 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.