倒排索引压缩的预处理方法

摘要

一种倒排索引压缩的预处理方法。所述的倒排索引压缩的预处理方法包括：对每个倒排列表，以docID的索引为横坐标、值为纵坐标作二维散点图，基于最小二乘法生成一条线性回归直线，使得图中所有点到该直线的竖直离差的平方和最小，得到与该倒排列表等价的竖直离差列表；对每个竖直离差列表，将所有竖直离差向上取整，得到与该竖直离差列表等价的整数离差列表；对每个整数离差列表，求出最小值，同时将所有整数离差减去这个最小值，得到与该整数离差列表等价的非负整数离差列表。基于本发明的压缩算法具有较高的压缩比，提高了并行解压效率，可以更好地与集合归并方法结合。

主权项

1.一种倒排索引压缩的预处理方法，其特征在于，包括：(1)对每个倒排列表，以docID的索引x_i为横坐标、值y_i为纵坐标作二维散点图，x_i、y_i都是非负整数，其中i＝1，...，n，n为正整数，基于最小二乘法生成一条线性回归直线y＝f(x)＝α+βx，其中使得图中所有点(x_i，y_i)到该直线的竖直离差y_i-f(x_i)的平方和最小，得到与该倒排列表等价的竖直离差列表；(2)对每个竖直离差列表，将所有竖直离差y_i-f(x_i)向上取整记为得到与该竖直离差列表等价的整数离差列表；(3)对每个整数离差列表，求出最小值记为同时将所有整数离差减去这个最小值记为得到与该整数离差列表等价的非负整数离差列表。