一种可适应字符分布特征的多串匹配算法

摘要

确定有限状态自动机(DFA)被广泛地应用到模式串匹配问题中.随着模式串规模的不断增加，DFA状态转移表空间也越来越大，大量内存访问开销导致算法性能剧烈下降，因此，研究在保证随机访问的前提下如何对大型状态转移表进行压缩是一个具有挑战性的问题.本文提出了一种可以融合待扫描数据特征和模式串自身特征的链式状态转移表结构，并给出了链式状态转移表的内存访问代价，理论证明：使用Huffman编码对访问序列进行重编码可以使得其内存访问代价最小.最后根据实际数据下的访问频率呈指数下降的性质，使用Golomb编码实现了一个基于链式状态转移表的高级AC算法，在真实数据集上的测试表明了其有效性。链式内存转移表的思想是一种考虑了文本字符分布特征的DFA压缩思想，对基于DFA的正则表达式匹配算法也有很好的借鉴意义。