一种全文索引的压缩方法

A Compressed Suffix Automaton for Full Text Indexing

全文索引广泛应用于数据库、数据压缩、模式匹配算法以及信息生物学等领域。本文研究了后缀自动机全文索引结构,针对后缀自动机空间占用大的问题提出了一种边压缩方法。该方法通过后缀链接函数模拟实现自动机的跳转边,从而删除部分跳转边。在最终的压缩结构中,跳转边的数量与状态数量一致,而在后缀自动机中跳转边的数量是状态数量的一倍。证明了对于因子判定等问题,压缩的后缀自动机与后缀自动机具有相同的时间复杂度。

Full text indexes are widely used in areas such as data base,data compression,pattern matching and bioinformatics.We present in this paper a compression method for suffix automata.By deleting some transaction edges,the suffix automata can still work like the original suffix automata without losing performance.The compressed suffix automata have edges with the number similar with that of states while in the original ones the number of edges is twice of that of states.We also proved that using the compressed suffix automata the membership problem for the factor set of a given word can be solved linear time.