计算机应用 | 古代文学 | 市场营销 | 生命科学 | 交通物流 | 财务管理 | 历史学 | 毕业 | 哲学 | 政治 | 财税 | 经济 | 金融 | 审计 | 法学 | 护理学 | 国际经济与贸易
计算机软件 | 新闻传播 | 电子商务 | 土木工程 | 临床医学 | 旅游管理 | 建筑学 | 文学 | 化学 | 数学 | 物理 | 地理 | 理工 | 生命 | 文化 | 企业管理 | 电子信息工程
计算机网络 | 语言文学 | 信息安全 | 工程力学 | 工商管理 | 经济管理 | 计算机 | 机电 | 材料 | 医学 | 药学 | 会计 | 硕士 | 法律 | MBA
现当代文学 | 英美文学 | 通讯工程 | 网络工程 | 行政管理 | 公共管理 | 自动化 | 艺术 | 音乐 | 舞蹈 | 美术 | 本科 | 教育 | 英语 |

基于多级指引索引的高效技术(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
上一篇:电子商务中逆向物流研究综述(1) 下一篇:没有了