倒排文档压缩技巧d-gaps的改进——文档标识号重置法  

Improve the d-gaps Technique for Inverted File Compression: Document Identifier Reassignment

作　　者：张爱红[1] 

机构地区：[1]四川大学信息管理系,成都610064

出　　处：《现代图书情报技术》2004年第8期61-65,共5页New Technology of Library and Information Service

摘　　要：倒排文档是信息检索系统中最普遍使用的索引机制 ,而索引文件的压缩能大大提高检索速度和节约磁盘空间。倒排文件压缩的传统做法是文档 (标识号 )间距法 (d- gaps)。然而 ,剧烈变化的间距值并不能被著名的前缀自由代码有效编码压缩。为了使间距值得到有效的压缩 ,本文设计了一个文档标识号重置法。模拟试验表明能更有效压缩 d- gaps倒排文档。The inverted file is the most popular indexing mechanism in an information retrieval system. Compressing an inverted file can greatly improve document search rate and save disk space. Traditionally, the d-gaps technique is used in the inverted file compression by replacing document identifiers with usually much smaller gap values. However, fluctuating gap values cannot be efficiently compressed by some well-known prefix-free codes. In this paper, a document identifier reassignment algorithm is proposed to reduce the gap values. Simulation results show that the average gap values of the inverted files can be reduced effectively.

关 键 词：倒排文档 文档(标识号)间距法 文档标识号重置法 旅行商问题 贪心算法 最大生成树 

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