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

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

1、从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果基于多级指引索引的高效技术(1)摘要介绍了搜索引擎中基于多级指引索引的高效技术。包括索引压缩，置入文件阀值的方法。其中索引压缩介绍了字节对齐压缩、Eliasgamma编码、Eliasdelta编码、Golomb编码、二元插值编码，并对其压缩效率，解压速度以及相对性能做了比较，叙述了在不同的情况下使用不同的编码，以便提高搜索效率。关键词搜索引擎，多级指引索引，索引压缩，置入文件阀值1引言搜索引擎是随着

2、Web信息的迅速增加，从1995年开始逐渐发展起来的技术。它是一种Web上的应用软件系统，以一定的策略在Web上发现和收集信息，对信息进行组织和处理，为用户提供Web信息查询服务。一个搜索引擎由搜索器、索引器、检索器和用户接口等四个部分组成。其中索引器是一个搜索引擎的核心部分，因此索引的好坏直接影响到整个搜索引擎的质量。采用多级指引索引数据结构，尽管建立时需要付出一定代价，但是极大地提高了查询效率。本文在多级指引索引的基础上，介绍了提高效率的策略，其中包括多级指引索引的压缩，置入文件阈值的方法。多级指引索引简介图1索引多级指引结构

3、课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果多级指引索引是倒排索引的进化，既满足检索接口的词语-网页结构的需要，又考虑到庞大数据量结构组织的可行性。在词语集设置网页指针，将包含该词语的网页分块放置，减少存储相同词语的空间，根据词语标识符直接找到网页分块首位置，并为下一级指引提供前提；同一个词语在不同网页中出现的位置是变值，设置位置指

4、针可以减少存储相同网页号的空间。3多级指引索引的压缩多级指引索引压缩的目标是通过减少存储需求来降低输入输出。需要压缩的内容包括：词语列表中的词语名，每一个置入文件列表记录中的词频，每一个置入文件列表记录文档标识符。如果多级指引索引减少存储量，I/O读写置入列表的时间就会减少，也就减少了内存、磁盘空间的占用。而一个没有被压缩的多级指引索引通常需要超过30％的空间来存储可压缩的数据，压缩后的数据只占原可压缩数据的10％－15％。但是存在的问题是，要对数据编码解码，增加了CPU时间耗用，考虑到I/O是系统的瓶颈，CPU与I/O之间不断扩

5、大的性能差距，以时间换取空间是可行的。压缩不仅提高查询时的效率，还能加快创建索引，从各方面提升系统性能。多级指引索引压缩的方法有字节对齐压缩，Eliasgamma编码，Eliasdelta编码，Golomb编码，二元插值编码。字节对齐压缩字节对齐压缩[1]即对于一个给定的正整数，用一个或多个字节表示。表示该数首字节最左边的两位为长度指示器，剩余位可以用来存储实际的数。文档ID不同，记为x，文档ID需要基于x的字节标识码，用前面所说的2bits写下长度指示器。写下x的二进制表示法，如下例：0-00xxxxxx64-(16K-1)01

6、xxxxxxxxxxxxxx16K-(4M-1)课题份量和难易程度要恰当，博士生能在二年内作出结果，硕士生能在一年内作出结果，特别是对实验条件等要有恰当的估计。从本学科出发，应着重选对国民经济具有一定实用价值和理论意义的课题。课题具有先进性，便于研究生提出新见解，特别是博士生必须有创新性的成果10xxxxxxxxxxxxxxxxxxxxxx4M-(1G-1)11xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx0……字节对齐压缩的优点是容易编码和解码，位操作少，占用CPU时间少，缺点是对很小的整数压缩率低，每个整数最少用

7、一个字节的空间。gamma编码用γ[2]方法表示文档ID的x的数值：表示2的次幂不超过x的最大值；一个0作为标记位；取x－余数二进制编码的位。用＋1bits表示x的值，整数越小，则表示它值的位数就越少。大多数词频相对很小。举个例子：X=22=44≤x54为2的次幂不超过22的最大值，所以得出4位一元码：1111x-=22-24=6用4位二进制数表示余数6：0110最后的γ编码为：111100110x……63γ,0,1011,0,,0,11111EliasGammaEncoding(γ)总结：Gamma编码对于一元码很小的小整数是有

8、效的，但是对于存储15个以上的整数效率就降低。Delta(δ)编码Delta[2]编码实际上是Gamma编码的延伸，其中整数x由两部分表示，1＋位由Gamma编码得出，之后标记位，接下来是x的二进制编码，其中x的最高位取反。Delta编码在表示小的