基于多级指引索引的高效技术(1)
2014-05-15 01:04
导读:计算机应用论文论文,基于多级指引索引的高效技术(1)论文样本,在线游览或下载,科教论文网海量论文供你参考:
摘 要 介绍了搜索引擎中基于多级指引索引的高效技术。包括索
摘 要 介绍了搜索引擎中基于多级指引索引的高效技术。包括索引压缩,置入文件阀值的方法。其中索引压缩介绍了字节对齐压缩、Elias gamma编码、Elias delta编码、Golomb编码、二 元插值编码,并对其压缩效率,解压速度以及相对性能做了比较,叙述了在不同的情况下使用不同的编码,以便提高搜索效率。 关键词 搜索引擎,多级指引索引,索引压缩,置入文件阀值1 引言 搜索引擎(Search Engine)是随着Web信息的迅速增加,从1995年开始逐渐发展起来的技术。它是一种Web上的应用软件系统,以一定的策略在Web上发现和收集信息,对信息进行组织和处理,为用户提供Web信息查询服务。 一个搜索引擎由搜索器、索引器、检索器和用户接口等四个部分组成。其中索引器是一个搜索引擎的核心部分,因此索引的好坏直接影响到整个搜索引擎的质量。采用多级指引索引数据结构,尽管建立时需要付出一定代价,但是极大地提高了查询效率。本文在多级指引索引的基础上,介绍了提高效率的策略,其中包括多级指引索引的压缩,置入文件阈值(posting list threshold)的方法。2 多级指引索引简介

图1 索引多级指引结构 多级指引索引是倒排索引的进化,既满足检索接口的词语-网页结构的需要,又考虑到庞大数据量结构组织的可行性。在词语集设置网页指针,将包含该词语的网页分块放置,减少存储相同词语的空间,根据词语标识符直接找到网页分块首位置,并为下一级指引提供前提;同一个词语在不同网页中出现的位置是变值,设置位置指针可以减少存储相同网页号的空间。3 多级指引索引的压缩 多级指引索引压缩的目标是通过减少存储需求来降低输入输出。需要压缩的内容包括:词语列表中的词语名,每一个置入文件列表记录(entry)中的词频,每一个置入文件列表记录文档标识符。如果多级指引索引减少存储量,I/O读写置入列表(posting list)的时间就会减少,也就减少了内存、磁盘空间的占用。而一个没有被压缩的多级指引索引通常需要超过30%的空间来存储可压缩的数据,压缩后的数据只占原可压缩数据的10%-15%。但是存在的问题是,要对数据编码解码,增加了CPU时间耗用,考虑到I/O是系统的瓶颈,CPU与I/O之间不断扩大的性能差距,以时间换取空间是可行的。压缩不仅提高查询时的效率,还能加快创建索引,从各方面提升系统性能。 多级指引索引压缩的方法有字节对齐压缩,Elias gamma编码,Elias delta编码,Golomb编码,二元插值编码。3.1 字节对齐压缩(Byte-Aligned) 字节对齐压缩[1]即对于一个给定的正整数,用一个或多个字节表示。表示该数首字节最左边的两位为长度指示器(length indicator),剩余位可以用来存储实际的数。文档ID不同,记为x,文档ID需要基于x的字节标识码,用前面所说的2bits写下长度指示器。写下x的二进制表示法,如下例:0-63 00xxxxxx64-(16K-1) 01xxxxxx xxxxxxxx16K-(4M-1) 10xxxxxx xxxxxxxx xxxxxxxx4M-(1G-1) 11xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx0 000000001 00000001… …63 0011111164 01000000 0100000065 01000000 01000001字节对齐压缩的优点是容易编码和解码,位操作少,占用CPU时间少,缺点是对很小的整数压缩率低,每个整数最少用一个字节的空间。3.2 Elias gamma(γ)编码 用γ[2]方法表示文档ID的x的数值:

表示2的

次幂不超过x的最大值;一个0作为标记位(marker);取x-

余数二进制编码的

位。用2

+1bits表示x的值,整数越小,则表示它值的位数就越少。大多数词频相对很小。举个例子:X=22