摘要：大多数倒排索引结构并未提出词汇表的组织形式,传统的基于Hash算法组织的词汇表存在大量碰撞的索引词。本文提出一种基于共享前缀的两级索引结构,通过对汉字、英文、数字进行统一编码,把具有相同首字的索引词映射到一级索引的相同位置;二级索引使用共享前缀树的结构组织索引词,既能通过二分查找快速定位索引文件存储块的位置,又能通过共享前缀的方式减少对相同字的存储,有效地减少了索引文件占用的存储空间。实验结果表明,该结构索引文件与源文档大小的压缩比达到0.59,与顺序索引和Hash索引相比,具有较高的时空效率。

关键词：倒排结构 两级索引 共享前缀 平衡二叉树 

单位：国防科学技术大学计算机学院 湖南长沙410073