搜索引擎的基本工作原理(2)

                    搜索引擎的体系结构

    搜索引擎是指以一定的策略搜集互联网上的信息，在对信息进行组织和处理后，为用户提供检索服务的系统。

    搜索引擎主要由搜索器、索引器、检索器和用户接口构成。

    一、搜索器。

    A、网络蜘蛛：搜索引擎系统结构的搜索器（Spider）俗称网络蜘蛛或网络爬虫，十亿个自动收集网页的系统程序，其功能是日夜不停地在互联网中漫游，搜集信息。它要尽可能多、尽可能快地搜集各种类型的新信息，还要定期更新已经搜索过的旧信息，以避免出现死链接。目前有两种搜集信息的策略：

       a、从一个其实URL开始，顺着这些URL中的超链接（Hyperlink），以宽度优先、深度优先或启发式方式循环在互联网中发现信息。起始URL使一些非常流行，包含很多链接的站点（如Yahoo！）。

       b、将Web空间按照域名、IP地址或国家划分，每个搜索器负责一个子空间的穷尽搜索。搜索器将搜索回来的每个文档过滤掉格式符，提取文本数据 Fulltext。每个文档对应着一个Fulltext文件，内容包括网页标题、网页URL、大小、时间、类型、分类等属性及文本内容，所有生成的这些文件交给索引器进行索引处理。搜索器的实现常用分布式并行计算技术，以提高信息发现和更新的速度。

    B、内容提取（文本文件）。

       对网页内容的提取，一直是网络蜘蛛重要的技术。整个系统一般采用插件的形式，通过一个插件管理服务程序，遇到不同格式的网页采用不同的插件机处理，搜索引擎建立索引、处理的对象是文本文件。

    C、定期更新策略。

       由于网站的内容经常在变化，因此网络蜘蛛也不断地更新其抓取网页的内容，这就需要网络蜘蛛按照一定的周期去扫描网站，查找哪些页面是需要更新的页面，哪些页面是新增页面，哪些页面是已经过期的死链接。

    二、索引器。

    索引器（Indexer）的功能是理解搜索器所搜索的信息，由分析索引系统程序对收集回来的网页进行分析，提取网页信息（包括网页所在URL、编码类型、页面内容包含的关键词、关键词位置、生成时间、大小、与其他网页的链接关系等），根据一定的相关度算法进行大量复杂计算，得到每一个网页针对页面内容中及超链接中每一个关键词的相关度（或重要性），然后这些相关信息建立网页索引数据库。

    索引器的工作过程为：索引器读入搜索器生成的Fulltext文件，采用基于位置倒排索引与三级n元索引相结合的索引机制。首先进行分词处理生成索引项，并作归类排序，生成Index文件和inv文件，inv文件为倒排表（Inversion List），即由索引项查找相对应的文档，Index文件形成分词-倒排表对应关系，内容为分词在倒排表中相应的文档块起始地址，含有该词的文档数量等信息。索引器可以使用集中式索引算法或分布式索引算法。当数据量很大时，必须实现即时索引，否则不能跟上信息量急剧增加的速度。索引算法对索引器的性能（如大规模峰值查询时的响应速度）有很大的影响。一个搜索引擎的有效性在很大程度上取决于索引器的质量。

    索引项有客观索引项和内容索引项两种：客观索引项与文档的语义内容无关，如作者名、URL、更新时间、编码、长度、链接流行度（Link Popularity）等；内容索引项是用来反映文档内容的，如关键词极其权重，短语、单字等。内容索引项可以分为单索引项和多索引项（短语索引项）两种。单索引项对于英文来讲是英语单词，比较容易提取，因为单词之间有天然的分隔符（空格）；对于中文等连续书写的语言，必须进行词语的切分（分词）。

    词法分析是对自然语言的形态进行分析，判定词的结构、类别和性质的过程。对于以英文为代表的形态丰富的语言来说，英文的词法分析的一个重要的过程是形态分析，即将英文词还原成词干。而汉语形态变化很少，其主要的问题在于书写时词与词之间没有空格，所以通常中文词法分析的关键是分词，分词往往是后续进一步处理的基础。

    (1)、英语词法分析：英文的形态分析主要目标是将句子中的词从词性还原到词甚至词根。英文的形态分析常常也称为stemming，分析器称为 stemmer。形态分析常常采用基于自动机的规则方法，即将词形变化的规律总结成规则，然后通过自动机的方法对词形进行转换。转换的过程当中可以使用或者不使用词典。

    (2)、中文分词技术：基于机械匹配和机遇概率统计的分词方法。前者通过对已有词典的机械匹配来得到分词结果。后者不需要任何词典就可以得到粉刺结果，或者对粗切分结果进行基于概率统计后的处理来得到最终分词结果。

    中文分词技术面临的两个最大的问题是切分歧义和未定义词的问题。前者要解决在上下文环境下不同切分结果的选择；后者要解决词典中未收录词（如人名、地名、机构名等）的识别。可以在机械匹配的基础上通过规则的方法来求解上述两个问题。然而规则方法很难穷尽真实文本的各种现象。目前比较主流的方法是通过对真实文本的概率统计来求解切分歧义和未定义词问题。

     三、检索器。

     检索器（Searcher）的功能是针对用户的查询请求在索引库中快速检出文档，采用一定的信息检索模型进行文档与查询的相关度评价，对将要输出的结果进行排序、聚类等操作，并实现某用户相关性反馈机制。信息检索模型有以下几种：布尔逻辑模型、模糊逻辑模型、向量空间模型、概率模型及混合模型等。

     检索器的工作过程如下：检索器对用户接口（Uesr Interface, UI）提出的查询要求进行递归分析，在UI中一般采用基本语法来组织要检索的条件。检索器通常支持多种语法规则，如逻辑操作符AND、OR、NOT，使用 “+、-”连接号和通配符，使用逗号、括号或引号进行词组查找。对于每个索引项，匹配Index文件，查到倒排表（inv文件）中包含该索引项的文档，并对所有查找出的文档进行集合运算，将结果集按照基于内容和基于链接分析的方法进行相

关度评价并排序，最大限度地保证检索出的结果与用户查询串有很高的相关性，将最终形成的有序的文档结果集合返回给用户。

     四、用户接口。

     用户接口(UI)的作用是输入用户查询，显示结果查询结果，提供用户相关性反馈机制。UI的主要目的是方便用户使用搜索引擎，高效率、多方式地从搜索引擎中得到有效、及时的信息。UI的实际和实现使用人机交互的理论和方法，以充分适应人类的思维习惯。

     用户输入接口可以分为简单接口和复杂接口两种。简单接口只提供用户输入查询串的文本框；复杂接口可以让用户对查询进行限制，如逻辑运算（与、或、+、-）、相近关系（相邻、near）、域名范围（如edu.com）、出现位置（如标题、内容）、信息时间、长度等。目前一些公司和机构正在考虑制定查询选项的标准。

      当互联网用户通过UI提交查询时，检索器程序根据用户输入的查询关键词，在已由索引器完成索引和初排序的存储桶（Barrel）中进行查找，并采用特定的页面优先度算法对其结果进行最终排序，使之尽可能符合用户查询需求。最后UI将最终查询结果呈现在互联网用户面前。