论文部分内容阅读
倒排索引是Web搜索引擎的核心数据结构，也是目前为止被认为最高效的大规模文本索引方法。随着互联网络的发展，数据规模和用户数量相比早期都有了质的飞跃，这给Web搜索引擎的性能带来了极大的挑战。如何高效地存储和处理倒排索引，对搜索引擎的性能至关重要。 本文的主要研究内容是倒排索引压缩和合并技术。压缩技术能够有效地减小倒排索引体积，提高其存储效率;合并技术则能够加快倒排索引处理速度，提高查询处理效率。本文通过研究倒排索引中的文档序号局部连续性，提出了新的索引压缩和合并算法，并在实际数据集上验证了这些算法的有效性。本文的主要贡献和创新点如下: 1.详细分析了文档局部连续性对倒排索引压缩的影响。倒排索引局部连续性是指在倒排索引中，某一词项在多个连续或者邻近的文档中出现，导致文档序号的分布呈现一定的连续性。本文详细分析了局部连续性能够提高倒排索引压缩率的原因，以及文档序号重排对索引压缩的重要作用。 2.提出一种基于词项的文档序号重排方法。通过文档序号重排，可以在倒排索引中产生较好的局部连续性，进而提高索引压缩率。本文提出了一种新的基于词项的文档序号重排方法，和传统的方法相比，该方法有效地降低了算法的时间复杂度和空间复杂度;此外，该方法可以以词项为基本单位，根据词项的使用情况对倒排索引的局部连续性进行优化。 3.提出一种基于游程编码的倒排索引表示形式:D-RANGE。当倒排索引具有较好的局部连续性时，传统的D-GAP形式已经无法高效地存储倒排索引。本文提出了基于游程编码的D-RANGE形式，该形式不仅提高了倒排索引压缩率，而且减少了存储倒排索引所需要的整数个数，提高了编码、解码效率，加快了查询处理的速度。 4.设计并实现了一种基于D-RANGE形式的倒排索引快速合并算法。目前的索引合并算法都是以D-GAP形式的倒排索引为操作对象，合并的基本单位是单个文档。本文在D-RANGE形式的基础上，提出了一种新的倒排索引快速合并算法，和基于D-GAP形式的合并算法相比，该算法合并的粒度更大，效率也更高。