第一节
大型互联网搜索引擎的数据中心一般运行数千台甚至数十万台计算机,而且每天向计算机集群里添加数十台机器,以保持与网络发展的同步。搜集机器自动搜集网页信息,平均速度每秒数十个网页,检索机器则提供容错的可缩放的体系架构以应对每天数千万甚至数亿的用户查询请求。企业搜索引擎可根据不同的应用规模,从单台计算机到计算机集群都可以进行部署。
搜索引擎一般的工作过程是:首先对互联网上的网页进行搜集,然后对搜集来的网页进行预处理,建立网页索引库,实时响应用户的查询请求,并对查找到的结果按某种规则进行排序后返回给用户。搜索引擎的重要功能是能够对互联网上的文本信息提供全文检索。
图1 搜索引擎的工作流程
图2 搜索引擎各个组成部分的关系
一、搜集器
搜索引擎通过一种程序robot(又称spider),搜集器的功能是在互联网中漫游,发现并搜集信息,它搜集的信息类型多种多样,包括HTML页面、XML文档、Newsgroup文章、FTP文件、字处理文档、多媒体信息等。搜索器是一个计算机程序,其实现常常采用分布式和并行处理技术,以提高信息发现和更新的效率。商业搜索引擎的搜集器每天可以搜集几百万甚至更多的网页。搜索器一般要不停地运行,要尽可能多、尽可能快地搜集互联网上的各种类型的新信息。因为互联网上的信息更新很快,所以还要定期更新已经搜集过的旧信息,以避免死链接和无效链接。另外,因为Web信息是动态变化的,因此搜集器、分析器和索引器要定期更新数据库,更新周期通常约为几周甚至几个月。索引数据库越大,更新也越困难。
在搜集器实现时,系统中维护一个超链队列,或者堆栈,其中包含一些起始URL(
理解成像DMOZ、Yahoo目录Google sitemap等),搜集器从这些URL出发,下载相应的页面,并从中抽取出新的超链加入到队列或者堆栈中,上述过程不断重复队列直到堆栈为空。为提高效率,搜索引擎将Web空间按照域名、IP地址或国家域名进行划分,使用多个搜集器并行工作,让每个搜索器负责一个子空间的搜索。为了便于将来扩展服务,搜集器应能改变搜索范围。
1、线性搜集策略
线形搜索策略的基本思想是从一个起始的IP地址出发,按IP地址递增的方式搜索后续的每一个IP地址中的信息,完全不考虑各站点的HTML文件中指向其他Web站点的超链地址。此策略不适用于大规模的搜索(主要原因在于IP可能是动态的),但可以用于小范围的全面搜索,利用此种策略的搜集器可以发现被引用较少或者还没有被其他HTML文件引用的新HTML文件信息源。
2、深度优先搜集策略
深度优先搜集策略是早期开发搜集器使用较多的一种方法,它的目的是要达到被搜索结构的叶结点。深度优先搜索顺着HTML文件上的超链走到不能再深入为止,然后返回到上一个接点的HTML文件,再继续选择该HTML文件中的其他超链。当不再有其他超链可选择时,说明搜索已经结束。深度优先搜索适宜遍历一个指定的站点或者深层嵌套的HTML文件集,但对于大规模的搜索,由于Web结构相当深,也许永远也出不来了
3、广度优先搜集策略
广度优先搜集策略是先搜索同一层中的内容,然后再继续搜索下一层。假如一个HTML文件中有三个超链,选择其中之一并处理相应的HTML文件(注意:这里的处理文件指的是对文件内容进行检索,文件上的其他超链接先不作处理),然后返回并选择刚才第一个网页的第二个超链,处理相应的HTML文件,再返回。一旦同一层上的所有超链都已被处理过,就可以开始在刚才处理过的HTML文件中搜索其余的超链。(广度链接的定义)
这样保证了对浅层的首先处理,当遇到一个无穷尽的深层分支时,也就不会再陷进去。宽度优先搜集策略容易实现并被广泛采用,但是需要花费比较长的时间才能到达深层的HTML文件
4、收录搜集策略
有些网页可以通过用户提交的方式进行搜集,例如某些商业网站向搜索引擎发出收录申请,搜集器就可以定向搜集提交申请网站的网页信息并加入到搜索引擎的索引数据库中。
二、分析器
对搜集器搜集来的网页信息或者下载的文档一般要首先进行分析,以用于建立索引,文档分析技术一般包括: 分词(有些仅从文档某些部分抽词,如Altavista)、过滤(使用停用词表stoplist)、转换(有些对词条进行单复数转换、词缀去除、同义词转换等工作),这些技术往往与具体的语言以及系统的索引模型密切相关。
三、索引器
索引器的功能是对搜索器所搜索的信息进行分析处理,从中抽取出索引项,用于表示文档以及生成文档库的索引表。索引项有元数据索引项和内容索引项两种: 元数据索引项与文档的语意内容无关,如作者名、URL、更新时间、编码、长度、链接流行度为元数据索引项等等; 内容索引项是用来反映文档内容的,如关键词及其权重、短语、单字等等。内容索引项可以分为单索引项和多索引项(或称短语索引项)两种。单索引项对于英文来讲是英语单词,比较容易提取,因为单词之间有天然的分隔符(空格); 对于中文等连续书写的语言,必须进行词语的切分。在搜索引擎中,一般要给单索引项赋予一个权值,以表示该索引项对文档的区分度,同时用来计算查询结果的相关度。使用的方法一般有统计法、信息论法和概率法。短语索引项的提取方法有统计法、概率法和语言学法。
四、检索器
检索器的功能是根据用户的查询在索引库中快速检出文档,进行文档与查询的相关度评价,对将要输出的结果进行排序,并实现某种用户相关性反馈机制。检索器常用的信息检索模型有集合理论模型、代数模型、概率模型和混合模型等多种,可以查询到文本信息中的任意字词,无论出现在标题还是正文中。