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

A Two-Level Index Structure Based on Share-Prefix

作　　者：喻波[1] 赵国鸿[1] 陈曙晖[1] 

机构地区：[1]国防科学技术大学计算机学院,湖南长沙410073

出　　处：《计算机工程与科学》2010年第12期113-116,121,共5页Computer Engineering & Science

基　　金：国家自然科学基金资助项目(90604006)

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

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]