基于多级指引索引的高效技术.docx
《基于多级指引索引的高效技术.docx》由会员分享,可在线阅读,更多相关《基于多级指引索引的高效技术.docx(12页珍藏版)》请在咨信网上搜索。
1、基于多级指引索引的高效技术摘 要 介绍了搜索引擎中基于多级指引索引的高效技术。包括索引压缩,置入文件阀值的方法。其中索引压缩介绍了字节对齐压缩、Elias gamma编码、Elias delta编码、Golomb编码、二 元插值编码,并对其压缩效率,解压速度以及相对性能做了比较,叙述了在不同的情况下使用不同的编码,以便提高搜索效率。关键词 搜索引擎,多级指引索引,索引压缩,置入文件阀值1 引言 搜索引擎是随着Web信息的迅速增加,从1995年开始逐渐发展起来的技术。它是一种Web上的应用软件系统,以一定的策略在Web上发现和收集信息,对信息进行组织和处理,为用户提供Web信息查询服务。 一个搜
2、索引擎由搜索器、索引器、检索器和用户接口等四个部分组成。其中索引器是一个搜索引擎的核心部分,因此索引的好坏直接影响到整个搜索引擎的质量。采用多级指引索引数据结构,尽管建立时需要付出一定代价,但是极大地提高了查询效率。本文在多级指引索引的基础上,介绍了提高效率的策略,其中包括多级指引索引的压缩,置入文件阈值的方法。2 多级指引索引简介图1 索引多级指引结构 多级指引索引是倒排索引的进化,既满足检索接口的词语-网页结构的需要,又考虑到庞大数据量结构组织的可行性。在词语集设置网页指针,将包含该词语的网页分块放置,减少存储相同词语的空间,根据词语标识符直接找到网页分块首位置,并为下一级指引提供前提;同
3、一个词语在不同网页中出现的位置是变值,设置位置指针可以减少存储相同网页号的空间。3 多级指引索引的压缩 多级指引索引压缩的目标是通过减少存储需求来降低输入输出。需要压缩的内容包括:词语列表中的词语名,每一个置入文件列表记录中的词频,每一个置入文件列表记录文档标识符。如果多级指引索引减少存储量,I/O读写置入列表的时间就会减少,也就减少了内存、磁盘空间的占用。而一个没有被压缩的多级指引索引通常需要超过30的空间来存储可压缩的数据,压缩后的数据只占原可压缩数据的1015。但是存在的问题是,要对数据编码解码,增加了CPU时间耗用,考虑到I/O是系统的瓶颈,CPU与I/O之间不断扩大的性能差距,以时间
4、换取空间是可行的。压缩不仅提高查询时的效率,还能加快创建索引,从各方面提升系统性能。 多级指引索引压缩的方法有字节对齐压缩,Elias gamma编码,Elias delta编码,Golomb编码,二元插值编码。 字节对齐压缩 字节对齐压缩1即对于一个给定的正整数,用一个或多个字节表示。表示该数首字节最左边的两位为长度指示器,剩余位可以用来存储实际的数。文档ID不同,记为x,文档ID需要基于x的字节标识码,用前面所说的2bits写下长度指示器。写下x的二进制表示法,如下例:0-63 00xxxxxx64-(16K-1) 01xxxxxx xxxxxxxx16K-(4M-1) 10xxxxxx
5、xxxxxxxx xxxxxxxx4M-(1G-1) 11xxxxxx xxxxxxxx xxxxxxxx xxxxxxxx0 000000001 00000001 63 0011111164 01000000 0100000065 01000000 01000001字节对齐压缩的优点是容易编码和解码,位操作少,占用CPU时间少,缺点是对很小的整数压缩率低,每个整数最少用一个字节的空间。 Elias gamma编码 用方法表示文档ID的x的数值: 表示2的 次幂不超过x的最大值;一个0作为标记位;取x 余数二进制编码的 位。用2 1bits表示x的值,整数越小,则表示它值的位数就越少。大多数词
6、频相对很小。举个例子:X=22=4 24x254为2的 次幂不超过22的最大值,所以得出4位一元码:1111x- =22-24=6用4位二进制数表示余数6:0110最后的编码为:1111 0 0110x1234567630100101110001100111,0,1011,0,1111111,0,11111Elias Gamma Encoding()总结:Gamma编码对于一元码很小的小整数是有效的,但是对于存储15个以上的整数效率就降低。 Elias Delta()编码 Delta编码实际上是Gamma编码的延伸,其中整数x由两部分表示,1 位由Gamma编码得出,之后标记位,接下来是x的二
7、进制编码,其中x的最高位取反。Delta编码在表示小的整数的时候需要更多的空间存储,但对于压缩大整数是有效的。 Golomb编码 在Golomb编码中,整数x由两部分组成:商和余数。商q是由q= 得出的,余数r是由r=x-q*k-1计算出来的,这里的k是Golomb编码的基础。如果rp,可被存储为 位,反之则需要 位,这里的p是一个中心点,是由 k得到的。 当rp时,Golomb编码是由q个0,一个1,r组成的;当r=p时,它是由q个0,一个1,r+p组成的。例如,k=3,整数9就可由00,1,11表示。选择k对整个编码来讲是至关重要的。如果选的不合适,编码会变得很大而且解码也需要很长时间。这
8、里可以考虑*mean(a),a为整型数组。值012341112131415商0000123333余数0123030123编码100101110111010000111000100000101000110000111 通过比较,可以将这三种编码方式结合起来,Golomb编码用于文档编号,Gamma编码用于词频,Delta编码用于表示偏移量。 二元插值编码 二元插值编码利用相邻元素关系,应用于单调递增整数序列。如果在单调序列X1中,对于给定的整数xi,我们知道它的前一个整数是xi-1,后一个整数是xi+1, 由此我们知道存储xi所需要的最大位数。因为xi一定是在xi-11,xi+11的范围内,所以
9、需要的最大比特数为2,编码需要前面的xi-1和xi+1,所以序列X2可由原始的X1的第二个数开始与X1序列对应,编码可以递归的方法。 进一步优化的方法是根据整数序列的平均游程长度,对位向量编码增加参数,称作局部模式。比较简单的一种方法是一个整数序列的个数是Pw,则它的平均游程长度是N/Pw,设b=/Pw,则取VG=(b,b,b,)作压缩向量,前缀用一元编码,后缀是二进制编码。 在非全文索引当中,置入文件由文档号d和文档词频f组成,一个平均可以用一个字节表示;单词t的置入文件可以根据t的IDF(Inverse Document Frequency)推算出来。 在全文索引中,单词出现的位置信息占据
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 多级 指引 索引 高效 技术
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【人****来】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【人****来】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。