摘要： 传统后缀树全文索引模型的索引建立复杂、难以维护，且空间消耗大。为此，提出一种改进的后缀树全文索引模型。将一棵完整后缀树划分为若干个三元后缀树，从而简化后缀树的组织结构，便于其建立和维护索引。将邻接字符对的公共前缀作为后缀树的根结点，以降低模型的空间消耗，提高查询效率。实验结果表明，与传统模型相比，该模型具有较高的时空效率。

关键词: 后缀树, 全文索引, 邻接字符对, 三元后缀树, 公共前缀, 时空效率

Abstract: Because of indexical high complexity of establishment, superior difficulty of maintenance and high consumption of space, an improved suffix tree full-text index model is proposed for those drawbacks of the traditional one. It divides the relatively large suffix tree into several Three Dimensional Suffix Tree(3DST). It makes the establishment and maintenance of index more convenient and faster by simplifying the structure of the suffix tree. Meanwhile, the improved model reduces the space and increases time and space efficiency by making the common prefix of Adjacent Character Pair(ACP) root node of the suffix tree. Experimental result shows that the improved model has a higher space and time efficiency than the traditional one.

Key words: suffix tree, full-text index, Adjacent Character Pair(ACP), Three Dimensional Suffix Tree(3DST), common prefix, time and space efficiency

中图分类号: 

• TP311