基于多级指引索引的高效技术

《基于多级指引索引的高效技术》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、基于多级指引索引的高效技术摘要介绍了搜索引擎中基于多级指引索引的高效技术。包括索引压缩，置入文件阀值的方法。其中索引压缩介绍了字节对齐压缩、Eliasgamma编码、Eliasdelta编码、Golomb编码、二元插值编码，并对其压缩效率，解压速度以及相对性能做了比较，叙述了在不同的情况下使用不同的编码，以便提高搜索效率。关键词搜索引擎，多级指引索引，索引压缩，置入文件阀值1引言搜索引擎（SearchEngine）是随着-1)10xxxxxxxxxxxxxxxxxxxxxx4M-(1G-1)11xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx000000000100000

2、001……6300111111640100000001000000650100000001000001字节对齐压缩的优点是容易编码和解码，位操作少，占用CPU时间少，缺点是对很小的整数压缩率低，每个整数最少用一个字节的空间。3.2Eliasgamma（γ）编码用γ[2]方法表示文档ID的x的数值：表示2的次幂不超过x的最大值；一个0作为标记位（marker）；取x－余数二进制编码的位。用2＋1bits表示x的值，整数越小，则表示它值的位数就越少。大多数词频相对很小。举个例子：X=22=424≤x<254为2的次幂不超过22的最大值，所以得出4位一元码（unary）：1111x-

3、=22-24=6用4位二进制数表示余数6：0110最后的γ编码为：111100110x1234567……63γ0100101110001100111,0,1011,0,1111111,0,11111EliasGammaEncoding(γ)总结：Gamma编码对于一元码很小的小整数是有效的，但是对于存储15个以上的整数效率就降低。3.3EliasDelta(δ)编码Delta[2]编码实际上是Gamma编码的延伸，其中整数x由两部分表示，1＋位由Gamma编码得出，之后标记位，接下来是x的二进制编码，其中x的最高位取反。Delta编码在表示小的整数的时候需要更多的空间存储，但对于压缩

4、大整数是有效的。3.4Golomb编码在Golomb[8]编码中，整数x由两部分组成：商和余数。商q是由q=得出的，余数r是由r=x-q*k-1计算出来的，这里的k是Golomb编码的基础。如果r<p,可被存储为位，反之则需要位，这里的p是一个中心点（pivotpoint）,是由－k得到的。当r<p时，Golomb编码是由q个0，一个1，r（用二进制表示）组成的；当r>=p时，它是由q个0，一个1，r+p（用二进制表示）组成的。例如，k=3,整数9就可由00,1,11表示。选择k对整个编码来讲是至关重要的。如果选的不合适，编码会变得很大而且解码也需要很长时间。这里可

5、以考虑0.69*mean(a),a为整型数组。值01234…1112131415…商00001…23333…余数01230…30123…编码1001011101110100…00111000100000101000110000111…通过比较，可以将这三种编码方式结合起来，Golomb编码用于文档编号，Gamma编码用于词频，Delta编码用于表示偏移量。3.5二元插值编码（BinaryInterpolativecoding）二元插值[6]编码利用相邻元素关系，应用于单调递增整数序列。如果在单调序列X1中，对于给定的整数xi，我们知道它的前一个整数是xi-1，后一个整数是xi+1,由

6、此我们知道存储xi所需要的最大位数。因为xi一定是在[xi-1＋1，xi+1－1]的范围内，所以需要的最大比特数为㏒2（xi+1－xi-1－2），编码需要前面的xi-1和xi+1，所以序列X2可由原始的X1的第二个数开始与X1序列对应，编码可以递归的方法。进一步优化的方法是根据整数序列的平均游程长度（meanrunlength）,对位向量编码增加参数，称作局部模式。比较简单的一种方法是一个整数序列的个数是PentFrequency)推算出来。在全文索引中，单词出现的位置信息占据索引数据的主要部分，所以忽略文档号d和文档词频f。用变长压缩算法，单词出现的位置可以用少于8bit的位表示。

7、设全部文档分词后的单词总数是TN，那么单词t总的出现次数是TN×TF(TermFrequency),它的置入文件的平均长度小于TN×TF字节。3.6多级指引索引压缩总结根据文献[10]这几种压缩方法的压缩效率，解压速度以及相对性能的比较如表一所示：图3其中bpo－每个事件(occurrence)的比特数，bpr－每个记录的比特数，cpo－每个事件的周期数，cpr－每条记录的周期数。我们可以假设1.4GB的多级指引文件列表通过最高效的方案（根据表1）被压缩，