一种基于共享前缀的两级索引结构

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

A Two-Level Index Structure Based on Share-Prefix

Most of the inverted index structures do not refer to the organization of the word table,and there are lots of word collisions in the conventional Hash algorithms.This paper proposes a two-level index structure,which uses simply a coding method to map words beginning with the same word to the same position of the first level index,and uses a share-prefix tree as the second level index to find the address of the index files rapidly,and reduces the storage space of the index files.The experimental results show that,the compressing ratio of the size of index files to that of the source files reaches 0.59.Compared with the sequence index and the Hash index,we acquire a better space-and-time efficiency.