Web搜索引擎工作原理和体系结构

时间:2021-04-10 08:59:54

1 现代大规模高质量搜索引擎一般采用三段式工作流程:

       搜集 ---  预处理 --- 服务

2 搜集:在具体搜集过程中,如果抓取一篇篇的网页,也可以有不同的考虑。最常见的一种是所谓的“爬取”:将Web上的网页集合看成是一个有向图,搜集过程从给定的起始URL集合S开始,沿着网页中的链接,按照先深,先宽,或者某种策略遍历,不停的从S中移除URL,下载相应的网页,解析出网页中的超链接URL,看是否已经被访问过,将未访问过的那些URL加入到集合S,继续抓取直到S为空。

3 搜集:搜集到的网页应该是相对比较重要的,所以在不可能将web上的网页搜集完全的情况下,使用先宽搜索方式要比先深搜索得到的网页集合重要,但是困难在于无法很好的提取所有的URL

4 搜集:还有一种搜集的方式是,在第一次全面网页搜集后,系统维护相应的URL集合S,以后的搜索就都基于这个集合,并且每当搜到一个网页,都要检查是否发生变化,如果有新的URL则爬取,反之则删除。

5 预处理:网页搜集后,最终需要按照一定的方式存储在服务器系统中,同时要便于检索,所以使用“倒排文件”这种数据机构来将文档中的关键字作为索引,文档作为索引目标,提高检索速度。

   这样一来,预处理主要包括以下4个方面:

    1 关键词提取

    2 镜像页面或者转载页面的消除

    3 链接分析

    4 网页重要程度计算

6 预处理.关键字提取:需要去除HTML页面上与实际内容信息无关的信息,再从网页源文件中提取出可以代表它的内容的一些特征,也就是内容部分所含的关键词(对于中文来说,除了使用标点符号分句分词,还应该进行切词操作)最后网页则由一组词来近似表示,当然我们需要去掉如“的”等没有意义的词

  预处理.重复或者转载网页的消除

  预处理.链接分析:大量的HTML标记既给网页的预处理造成了一些麻烦,也带来了新的机遇,从信息检索的角度来讲,如果系统面对的仅仅是内容的文字,那么我们能依据的就是“公共词汇假设”,即内容所包含的关键词集合,最多加上词频和词在文档集合中出现的文档频率的统计量。而有了HTML后,我们可以利用HTML标签的隐含信息获取更有意义的内容,同时HTML文档内的指向其他文档的链接信息不仅给出了网页间的关系,也对判断网页的内容有很大作用

  预处理.网页重要程度计算

7 服务:查询服务。查询服务的输入是前面两个阶段(将爬取得到的网页集合S进行预处理得到对S的一个子集的元素的某种内部表示)的结果,查询就是在这个基础之上进行的。

8 服务:对于子集元素,需要在系统中用一定的方式表示,元素主要有以下几个方面构成:

   原始网页文档

   URL和标题

   网页唯一编号

   网页内所含的重要关键字集合

   其他指标(重要程度,分类代码等)

  然后借助倒排文件结构来支持查询服务,也就是 将所有网页的关键词总体的集合和所有网页的编号一起构成一个倒排文件结构,这样一来就可以很快速的从关键字索引到目标文档。

9 服务.服务子系统的要求和工作原理,主要有三个方面:

   1 查询方式和匹配

   2 结果排序

   3 文档摘要

10 服务.服务子系统.查询方式和匹配:主流的简单的搜索引擎查询模式主要是按照客户输入的词或者短语,检索含有这些词或者短语中的词的网页。对于英文输入序列,我们可以利用英文单词间的空格来识别用户输入的关键词,并进行匹配查询,而对于中文,我们需要先对短句进行切词,即将它分成一个词的序列(最小元素是词),最后形成一个查询词表 q={t1,t2…,tm}。而如果我们的索引方式是使用倒排文件,那么q中的词只有在在倒排文件所含的词表中才有意义。所以我们不仅要将用户的查询文字进行分词得到q集合,还必须使得q集合中的元素都对应倒排文件中的一个或者多个文件,最终形成文档编号的集合,这就是我们所要的结果。

11 服务.服务子系统.结果排序:在这里我们使用传统的结果显示,即以列表的形式来返回给客户结果。而这时候 结果结合R={r1,r2,r3…rn}和q的相关性就是形成这个顺序的基本因素。我们无法很精确的定义相关性,因为它不仅和查询词有关,还和用户的各种背景有关,早期的解决方案是使用词频作为排序的关键。可以这样来判定词频,一个文档中包含的查询q中的词越多,这个文档就应该排在越前面,也可以这样考虑,如果一个词在越多的文档中出现,那么这个词用来区分文档的相关性的作用就越小。这种思路在倒排文件这种数据结构上很容易实现,我们在截取文档关键字的同时可以统计该关键字的出现次数等,而每个倒排表的长度则对应着一个词所涉及的文档的篇数。

    而仅仅依赖这种词频来排序文档是不够的,目前的搜索引擎使用的是一种PageRank的补充方法,通过在预处理阶段为每篇网页形成一个独立于查询词的重要性指标,将他和查询过程中形成的相关性指标结合成一个最终的排序。

12 服务.服务子系统.文档摘要:从网页中抽取相关性摘要文档是自然语言理解领域的一个课题,然而通过自然语言理解分析得到摘要性文档不适合在搜索引擎上使用:第一,网页写作不规范,增大了语言理解的难度;第二,复杂的语言理解算法耗时太多,不适合搜索引擎要高效处理海量网页信息的需求。所以我们可以简单的在预处理过程中抽取出一些文字,但是这些文字和查询词并没有关系(属于静态摘要抽取),而针对查询词的摘要抽取则属于动态抽取,我们根据查询词在文档中的位置,提取出周围的文字来,在显示时将查询词标亮。

13 搜索引擎的体系结构:

              Web搜索引擎工作原理和体系结构

   这里的控制器帮助我们更好的完成持续地大规模地进行网页搜集,改进性能问题等。

   收集器需要爬取大规模的网页数据,所以利用并发可以提供搜集效率,我们可以考虑一台计算机上的并发爬取:

     1 启动多个抓取进程或者线程
     2 利用异步通信,无需等待页面返回
     3 让多个网络通信时间重叠(协调同时完成多个页面请求)
     4 让网络通信时间和存放网页的磁盘访问时间重叠(协调好页面请求和索引建立)

   也可以考虑分布式环境下的爬取,让多台设备分布在网络上的不同位置,进行分布式搜集。
   除此以外,搜集还需要设定搜集频率,防止发生目标拒绝访问,还需要考虑爬取的网页质量,网页重复等问题