搜索引擎的体系结构与索引技术探析

王改香 (山西金融职业学院信息技术系,山西太原030008)

从20世纪末开始,经济文化领域就迅速进入了信息时代,知识和信息的爆炸式发展与网络的应用成为信息扩张的先锋。面对着网络中浩如星海的庞大知识信息库,无法准确全面的找到所需要的信息成为制约网络信息发展的枷锁。信息检索的索引技术发展弥补了这一缺陷,搜索引擎应运而生,成为海量网络信息准确全面定位的应用技术。搜索引擎是网络信息精准定位的应用,实现了庞大网络信息量的查询。而索引技术是搜索引擎的核心技术。下面,笔者对搜索引擎体系结构和索引技术进行分析。

1 搜索引擎的体系结构

搜索引擎的基本结构一般包括数据采集、数据分析、数据组织、数据检索和信息挖掘5个功能模块。数据采集是负责按照一定的方式和要求对网络上的WWW站点等资源进行搜集,并将搜集到的WWW网页信息经过网络传输,存储到搜索引擎的搜索端数据库中;数据分析负责对收集到的网页信息进行分析,按照特定的算法,从中提取有检索或查询价值的内容 (网页关键词、网页的分类类别、被其他网页链接次数等);数据组织是形成规范的索引数据库或便于浏览的层次型分类目录结构;数据检索负责帮助用户用一定的检索方式来检索索引数据库或浏览分类目录结构,以获取用户所需的信息;信息挖掘负责提取用户相关信息,以利用这些信息来提高检索服务的质量。如根据用户以前检索行为的学习统计及其登记的信息,可以实现个性化检索[1]。这5个功能模块构成了搜索引擎的基本体系结构,而不同的搜索引擎体系结构也有很多不同,下面笔者以几个典型的搜索引擎为例来分析搜索引擎的体系结构。

1)独立搜索引擎 实际中,独立搜索引擎就是以搜索引擎的结构为基础建立而成的。现在主流应用的第二代搜索引擎的构成具有结构上的统一和相似性:以搜集器完成广域网中网页信息和超链接信息的获取;网页数据库储存已经获取的网页信息与超链接结构的信息,做为备用等待分析器进行处理分析;分析器以网络中数据信息的特点为依据,以一定的算法作为分析方法,对网页数据库中储存的网络与超链接信息进行处理分析,提取与用户检索内容相关的页面描述信息,将分析后的信息传送到索引器建立结构索引;索引器将分析器所处理分析的页面抽象数据建立索引,分析器处理分析的页面描述信息,是页面与页面之间数据描述的正派表;索引数据库将与用户检索内容相关的信息进行存储,其中包括页面描述信息、各种索引数据、对检索结果有影响的用户信息等;检索器对用户检索请求进行响应,并对用户的检索进行跟踪;用户信息库将检索用户的相关信息进行存储,包括用户的IP地址、所有检索串和用户对检索的不同响应;挖掘器用于用户信息的获取,并以这些信息为依据对检索服务质量进行调整;用户接口为搜索引擎在用户端所显示的界面,提供用户的相关查询、结果显示与相关的反馈机制。

2)元搜索引擎 元搜索引擎的基本原理是调用各独立搜索引擎进行检索,并提供统一的用户界面和结果输出,因此,可将其按照功能分为3大部分:用户接口、查询代理和结果汇总。元搜索引擎采用统一的检索界面,供用户输入查询请求。用户接口包括请求提交和检索接口两部分组成。其中,请求提交的功能是将用户检索请求发送至成员搜索引擎。通常情况下,元搜索引擎对所能调动的成员搜索引擎进行设定;也存在部分元搜索引擎提供成员搜索引擎给用户进行选择;还有部分元搜索引擎以用户的搜索信息与网络的及时状况为用户提供成员搜索引擎,对用户的查询的响应速度和准确率进行优化。

元搜索引擎的优点从元搜索引擎的结构可以看出,元搜索引擎的技术重点在于查询前的处理 (检索请求的分发和转换)和检索结果的集成。一般来说,元搜索引擎都是选择那些比较典型的、性能优异的独立搜索引擎作为其成员搜索引擎。这样,与独立搜索引擎相比,元搜索引擎具有如下主要优点:搜索信息的覆盖面广、搜索结果具有权威性、可靠性、易维护性。元搜索引擎的出现大大提高了用户查询信息的覆盖面。由于它能够在多个搜索引擎中搜索,必然能够为检索提供更多的机会。但它在查询的准确度上却不一定强于独立搜索引擎。元搜索引擎的主要局限性体现在以下几个方面:调用搜索引擎的局限性、查询请求上的局限性、查询结果数量上的局限性、查询结果排序上的局限性。

3)分布式搜索引擎 以机器人为基础的搜索引擎 (Alta Vista)与目录式搜索引擎 (Yahoo!)在体系结构的角度皆为集中形式,工作方式都是通过自动搜索程序在广域网中抓取Web页面,在处理之后将信息集中存储在站点中,用户查询中通过对站点的访问实现查询过程[2]。一般情况下,集中式搜索引擎各部分都是独立对信息进行抓取和处理分析,没有协作性,从而造成工作的无效重复,也是对网络带宽资源极大的浪费,也成为各Web站点中无谓的负担。所以说,集中式搜索引擎的结构体系不能够适应现在网络规模不断扩大的形式。

而分布式搜索引擎是针对这种先天不足的搜索引擎而产生的,建立的中心思想是将IP地址、所在地域和主题等划分标准为依据,将广域网络划分为不同的搜索域,在搜索域中分别设置不同的检索服务器 (Index Server)。各个分域中的检索服务器由代理 (Broker)、信息搜集软件 (Gatherer)和索引数据库 (Index Database)3个部分构成。代理的任务是为用户提供查询服务的借口,实现与其他代理之间的互通,完成不同检索服务器之间的信息交换;信息搜索软件的功能是对本域内的数据信息进行抓取,在索引信息的处理后将信息发送到索引数据库。用户的查询要求通过代理完成定向的重置,在当前索引库无法完成用户的查询任务请求时,将请求发送至其他检索服务器,实现查询的分布式搜索。

2 索引技术

Indexer模块及Collection Analysis模块为页面集合创建了许多种类型的索引。Indexer模块创建2种基本索引,即文本索引 (网页的内容索引)及链接索引 (超链接结构)[3]。Collection Analysis模块利用这2种索引创建许多其他的辅助索引。

1)文本索引 文本索是查找与用户查询词相关页面的主要方法。可以使用任何传统索引方法为页面内容建立索引,如倒排文件、倒排索引、后缀数组、签名文件等。倒排索引方式是Web环境中最常用的索引方法。

2)链接索引 为了创建链接索引,可以将Web看做是一个巨大的图,图中的节点表示页面。从页面A到页面B的超链接构成图的边。链接索引的目的是实现对图的高效访问。搜索算法最常用的访问方式是找出与某一页面邻接的页面。使用Web构成的图及其补图的邻接链表可以有效地对这种邻接信息进行访问。其他类型的链接信息也可以通过邻接链表方便地得到。例如,若要获得某一页面的 “兄弟”节点,可以通过2个邻接矩阵得到。

3)辅助索引 辅助索引的数量及类型是Collection Analysis模块根据搜索引擎的特色及搜索算法所利用的Web特性所决定的。例如,若需要在指定网站范围内响应查询,建立网站索引将会高效率地处理该查询。同样,采用链接索引包含的邻接信息,可以比较容易地计算每个页面的PageRank权值。

4)倒排索引 倒排索引由倒排列表构成。每个词对应一个倒排列表。倒排列表是词在页面中的位置的有序列表。在最简单情况下,位置信息包括页面标识及词在页面中出现的位置。查询算法通常还要用到词的其他特征信息。例如,该词是否被加粗,是否在标题中,是否是超链接的锚文本。评估算法可能对这样的词分配高的权重。为了实现这样的功能,需要为每个词配置一些额外的信息。除了倒排列表之外,许多文本索引还保存语汇信息。语汇信息列出所有在倒排索引中出现的词及其统计信息,例如,某个词在页面集中出现的次数。这些统计信息同样也被评估算法使用。

由于Web的数据规模庞大,为Web建立倒排索引是一个极具挑战性的工作。一般地,建立倒排索引首先需要按词排序,然后再按词位置排序,最后将这些信息保存到磁盘中。对于小规模的数据集,例如,传统的信息检索 (IR)系统,建立索引的时间可以忽略不计[4]。但是对于Web上的中大规模数据集,这种简单的建立索引的方案不可操作,需要耗费很大的资源及时间。例如,WebBase存储了4百万的页面,只占可索引Web信息总量的4%,但这已经比最大的IR测试数据集TREC-7(100GB)大了许多。

此外,由于Web内容不断变化,需要定时地对索引进行更新,以便保持数据的 “新鲜”程度。这样,也需要不断地重建索引。通常的增量式索引更新方法对于Web的情况不适用,因为通常相邻时间采集的2个页面集合差别很大。倒排索引的存储格式必须仔细考虑。有效的压缩方法对索引访问性能的影响很大,因为在内存中同时可以保存更多的索引条目。此时,必须对性能上的收益与解压缩的代价进行权衡。

3 搜索引擎的发展趋势

随着网络信息的爆炸式增长和内容形式的不断出新,搜索引擎越来越不能满足客户的各种信息需求,目前的搜索引擎仍然存在着不少的局限性:搜索引擎对信息的标引深度不够,搜索引擎的信息量占有不足,搜索引擎的检准率不高,检索功能单一、缺乏灵活性,搜索引擎自身的技术局限。所以,搜索引擎发展的方向是以更先进、更高效的搜索技术为基础,为用户提供更精准、更适用的专业搜索工具,从而满足用户搜索查询需求。

1)发展垂直化专业领域搜索 随着社会分工的细化,不同领域的用户所提出的查询要求也更精细、更专业。以综合门户性质为特点的搜索引擎对不同方面、不同学科、不同行业的信息收录过多,查询的精准度受到了严重影响。垂直结构的专业搜索引擎面向特定的领域,对专业内的搜索需求和技术要求研究更为深入,能够确保本领域内数据信息收录的完全性和及时性。

2)搜索引擎的智能化 传统搜索引擎的搜索模式是被动的,而搜索行为的准确性是对所收录的信息和搜索请求有更精准的理解。以自然语言的理解技术为基础的搜索引擎,能够完成与客户的自然语言沟通,对用户的搜索请求理解更深入,所产生的结果更精准。智能代理是信息化的另一种机制,它使用自动获得的领域模型、用户模型知识进行信息搜集、索引、过滤,并自动将用户感兴趣的、对用户有用的信息提交给用户[5]。智能代理具有不断学习、适应信息和用户兴趣动态变化的能力,可提供个性化的服务。智能代理可在用户端进行,也可在服务器端进行。

3)开展搜索引擎的本地化服务 世界上许多著名的搜索引擎都在美国,这些综合性的搜索引擎已不能满足非美国网民的信息需求,因此搜索引擎必须本土化。Yahoo!、Lycos等著名公司已陆续推出适合不同国家、不同地区的本地搜索网站,搜索的本地化已势不可挡。而中文搜索引擎自然成为搜索引擎本地化的最大潜在市场。

4)采用分布式并行处理技术提高系统规模和性能 当搜索引擎的规模达到一定程度 (网页数达到亿级)时,如何及时地获取新网页和刷新数据库,保证查询效率不会明显降低,这就要依赖于设计合理的并行处理技术,采用某种分布式方法,以提高系统性能。

[1]徐舒.浅谈搜索引擎的体系结构与索引技术 [J].中国新技术新产品,2010(1):43.

[2]禹喆.对于搜索引擎的体系结构与索引技术的研究 [J].中国农业会计,2010(18):190.

[3]王铮,胡永杰.元搜索引擎的设计与实现 [J].河北师范大学学报(自然科学版),2010,25(2):175-178.

[4]邹海华.基于网站信息组织的搜索引擎优化策略[J].素质教育论坛,2010(18):5-7.

[5]梁静,葛宇,洪洁.搜索引擎优化初探探 [J].河北师范大学学报(自然科学版),2010,25(5):194-197.