史 亮，张 鸿，刘欣然，王 勇，王 斌

(1. 国家计算机网络应急技术处理协调中心，北京 100029； 2. 中国科学院 信息工程研究所，北京 100093)



倒排索引中的文档序号重排技术综述

史 亮1，张 鸿1，刘欣然1，王 勇1，王 斌2

(1. 国家计算机网络应急技术处理协调中心，北京 100029； 2. 中国科学院 信息工程研究所，北京 100093)

倒排索引作为文本搜索的核心索引技术，广泛应用于搜索引擎、桌面搜索和数字图书馆领域。倒排索引由字典和对应的倒排表组成，倒排表一般采用差值存储和整数编码进行压缩。研究表明，当倒排表具有较好的局部连续性时，上述方法能够获得很高的压缩率。整数编码研究通过不断改进编码算法来充分利用倒排表的局部连续性特征，而文档序号重排正是一种对文档序号重新排列来产生局部连续性的技术。通过文档序号重排，索引压缩率得到显著提高。该文主要介绍近年来文档序号重排技术取得的研究成果： 首先介绍索引压缩的基本原理，然后详细介绍文档序号重排技术，包括分析、对比各个方法的优劣；最后对文档序号重排技术进行总结、整理和展望。

搜索引擎；性能优化；索引压缩；文档序号重排；局部连续性

1 引言

随着互联网的快速发展，搜索引擎已经成为人们获取信息的主要手段。在搜索引擎中，倒排索引被证明是最合适并广泛使用的索引格式[1]。随着网络数据和用户规模的不断增长[2-3]，索引存储和查询处理都面临前所未有的挑战。

根据倒排索引的特点，索引压缩(Index Compression)采用文档序号重排技术和整数编码算法对倒排索引进行压缩。……