搜索引擎技术分析:信息技术基础实践

1．搜索引擎技术原理

搜索引擎有三步。

（1）从互联网上抓取网页（搜索软件的功能）。

利用能够从互联网上自动收集网页的Spider系统程序，自动访问互联网，并沿着任何网页中的所有URL“爬”到其他网页，不断重复这个过程，并把“爬”过的所有网页收集回来。

搜索引擎的Spider一般要定期重新访问所有网页（各搜索引擎的周期不同，可能是几天、几周或几月，也可能对不同重要性的网页有不同的更新频率），更新网页索引数据库，以反映网页文字的更新情况，增加新的网页信息，去除死链接，并根据网页文字和链接关系的变化重新排序。这样，网页的具体文字变化情况就会反映到用户查询的结果中。

（2）建立索引数据库（索引软件的功能）。

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

（3）在索引数据库中搜索排序（检索软件的功能）。

当用户输入关键词搜索后，由搜索系统程序从网页索引数据库中找到符合该关键词的所有相关网页。因为所有相关网页针对该关键词的相关度早已算好，所以只需按照现成的相关度数值排序，相关度越高，排名越靠前。最后由页面生成系统将搜索结果的链接地址和页面内容摘要等内容组织起来返回给用户。

互联网虽然只有一个，但由于各搜索引擎的能力和偏好不同，所以抓取的网页各不相同，排序算法也各不相同。大型搜索引擎的数据库储存了互联网上几千万至几十亿的网页索引，数据量达到几千G甚至几万G。但即使最大的搜索引擎建立的索引数据库，仍占互联网上不到30%的普通网页，不同搜索引擎之间的网页数据重叠率一般在30%以下。我们使用不同搜索引擎的重要原因，就是因为它们能分别搜索到不同的网页。而互联网上有更大量的网页，是搜索引擎无法抓取索引的。正如微软研究院负责搜索的一名技术专家说：75%的内容是搜索引擎搜索不出来的。这里面的原因包括：网站结构不合理，网页对搜索引擎不友好；由于互联网的信息是海量的，非结构化的信息需要经过结构化的梳理才能更好地展现。同时，市场需求的多元化也导致了搜索引擎的发展格局必然是行业化和细分化。

2．软件的组成及运作过程

搜索引擎在对WWW站点资源和其他站点资源进行标引和检索的过程中一般包括搜索软件、索引软件和检索软件。简单地说，搜索软件按照一定规律和方式对网络上WWW站点进行搜索，并将搜索到的WWW页面信息存入搜索引擎的临时数据库；索引软件对WWW页面信息进行整理以形成规范的页面索引，并建立相应的索引数据库；检索软件用一定方式检索索引数据库以获得符合用户需要的WWW站点或页面。

（1）搜索软件。

搜索软件是一种计算机程序，自动浏览Web上的超文本结构。该程序最重要的功能是使用索引策略，也就是查找网站和网页的次序。它一般以一个URL清单为基础，利用标准协议（如HTTP）依次请求相应的网页，并将其交给网页标引模块进行自动标引，并通过从网页中自动抽取能表达网页主题意义的词作为标引词来构建网页标引记录。由于网络上的数据量大，在现有的机器和网络条件下，搜索引擎只能对部分网络上的数据进行搜索。

搜索软件必须尽可能多地收集包括WWW超文本的所有文本、题名、摘要、关键词和 URL等信息，同时还要定期更新已有信息，避免死链接和无效链接。

对搜索引擎而言，普遍采用的是自动跟踪搜索软件，被称为“机器人”（Robot）、“蜘蛛”（Spider）、“Web爬行者”（WebcrawIer）、“漫游者”（Webwanderer）、“蠕虫”（Worm）等不同名称。下面以Robot搜索为例介绍搜索软件。

如果把整个Internet称为一个图或一棵树的话，可以发现Robot技术的基本工作原理和人工智能中的搜索树一样，这在计算机中可以方便地使用递归方法实现，具体如下：

① 根据首页进行搜索，相当于搜索树的根；

② 通过首页的第1个链接到下一个页面；

③ 重复①和②；

④ 到某页已经没有链接，回退上一级页面的下一个链接，如此循环往复。

但若要建立全面的索引数据库，必须对WWW系统进行遍历。我们可以进行这样假设：将WWW作为一个有向图处理，将页面看作图中的节点，页面中的超链看作图中的有向边。因此可以使用有向图遍历算法（深度优先或广度优先算法或启发式方式）对其进行遍历。WWW是个典型的C/S结构系统，所以可在一台主机上完成WWW遍历。

遍历一般采用以下 3种方法：

① 定一个种子URL，Robot从种子URL开始对WWW遍历；

② 定一组不同类别、被访问频率高的URL，Robot从这些URL开始遍历；

③ 据域名或IP地址将WWW空间划分为多个子空间，运行多个Robot程序并行地在不同子空间中进行遍历。

在实际使用中，一般是将这三种方法组合起来。按照上述遍历算法，Robot可以系统地、周期性地访问WWW，从而建立较为全面的索引库，并能保持对库的不断更新。

在遍历算法中，一般用到了两种方式，深度优先和广度优先两种基本的搜索策略。Robot以URL列表存取的方式决定搜索策略：

① 先进先出，则形成广度优先搜索。当起始列表包含有大量的Web服务器地址时，广度优先搜索将产生一个很好的初始结果，但很难深入服务器中去；

② 先进后出，则形成深度优先搜索。这样能产生较好的文档分布，更容易发现文档的结构，即找到最大数目的交叉引用。

这里很多人有一个误区，以为搜索软件会不断按照网页上的超链接自己延伸过去，其实不然。每个搜索软件都是按照人工指定的规则抓取一定页面，一般而言这个是按照URL来的。超出部分的链接会提交给检索索引数据库，让下一批搜索软件去查找。

在搜索软件系统里面，真正起指挥作用的是人工管理系统制定的规则和检索索引数据库。它可以决定什么样的网站抓得勤一点，或者干脆不抓。同时要判断这个网页几项要素：

① 这个网页的核心内容是什么，也就是这个网页的“关键词”是什么；(www.chuimin.cn)

② 这个网页的重要性权重如何，也就是说在同样“关键词”的网页比较，谁更符合这个“关键词”。

在第一个要素里面，需要通过对网页上的内容进行分析，而这里的“关键词”不是我们日常理解的词语，它是由语义分析学习系统按照一定规律制定的“最小语境含义表达单位（语境根）”，它可以是一个字，一个词，甚至一个短语，就是说它是表示某个含义的最小单位。通过根据“最小语境含义表达单位（语境根）”和网页文字进行比较，判断出这个网页的“关键词”。

（2）索引软件。

索引软件主要是理解Robot所搜索的网页信息，利用数据库管理系统来组织所采集标引的网页信息，并从中抽取索引项，形成索引数据库。数据库中的一条记录基本上对应于一个网页，一般包括关键词、网页摘要、网页url等信息。由于各个搜索引擎的标引原则和方式不同，它们的索引记录内容不一定相同，即使是同一网页记录内容也不完全相同。搜索引擎的有效性在很大程度上取决于索引的质量，而索引的质量由索引技术和索引策略来决定。

索引可以分为客观索引项和内容索引项两种。客观索引项与文档的语意内容无关，如作者名、URL、更新时间、编码、长度、链接流行度（link popularity）等。内容索引项是用来反映文档内容的，如关键词及其权重、短语、单字等。内容索引项可以分为单索引项和多索引项（或称短语索引项）两种。单索引项对于英文来讲是英语单词，比较容易提取，因为单词之间有天然的分隔符（空格），但对于中文等连续书写的语言，必须进行词语的切分。在搜索引擎中，一般要给单索引项赋予一个权值，以表示该索引项对文档的区分。索引项的提取方法有统计法、概率法和语言学法。索引表一般使用某种形式的倒排表（invers）度，同时用来计算查询结果的相关度。使用的方法一般有统计法、信息论法和概率法。短语索引即由索引项查找相应的文档。索引表要记录索引项在文档中出现的位置，以便检索器计算索引项之间的相邻或接近关系（proximity）。

索引软件是搜索引擎非常重要的部件，索引软件的策略很大程度影响了搜索引擎的效率与准确性。根据索引库的建立方式把搜索引擎分为目录式搜索引擎和自动搜索引擎。前者依靠人工和专家在网上浏览搜索页面收集信息，形成摘要和人工进行索引，建立自身的索引数据库；后者通过搜索软件程序定期在网上爬行，根据网页链接进行搜索，然后利用索引软件对收集的信息进行自动标引建立较为庞大的索引数据库，覆盖面相对较大并按照一定策略进行更新。

索引技术可以使用集中式索引算法或分布式索引算法。当数据量很大时，必须实现即时索引（instant indexing），否则不能跟上信息剧增的速度。索引算法对索引技术的性能（如大规模峰值查询时的响应速度）有很大的影响。一个搜索引擎的有效性在很大程度上取决于索引的质量，而索引的质量由索引技术和索引策略来决定，而现行的索引技术随着数据量的增大，其耗费的资源指数速度飞速增长，极大地影响到搜索数据库的容量和检索。基于这个情况可以考虑用提高索引智能化的方式来提高索引的质量。按建立索引的策略来看，应确定是全文关键字提取还是内容提取，因为根据不同的查询目标会有不同的提取目标和提取范围，最终将会极大影响数据提取的速度和效果，这是索引技术所要考虑的首要问题。按内容提取可以采用分类技术，把页面的主题或内容分类，进入不同的数据库中，在输入关键词查询时，要求第n个关键词必须是内容类别的词，这样第n个关键词就可以使搜索引擎知道到哪个内容类别的数据库中查找，再匹配后面的关键词，这样可以大大减少系统匹配的时间。这项技术要求在相关词库的基础上，统计使用频度，再加上一定的算法。当然上述两者应有机地结合才可提高整个系统的性能。

（3）检索软件。

检索软件是一个Web应用程序，负责提供用户使用搜索引擎的接口，接受用户检索要求，对用户输入的关键词进行语言分析，并分解成多个词或词组，将检索要求转换成计算机可执行的规范化检索式。然后利用检索式检索索引数据库，对检索词的相关性进行匹配，计算网页搜索请求的关联度，从而找到与检索词相关度接近的网页，按照相关度的高低进行排序输出结果，并实现某种用户相关性反馈机制。

检索软件主要包括4个部分：

① 检索界面：接受用户检索要求，往往分为一般检索界面和高级检索界面；

② 检索策略：将用户输入的检索要求转换成计算机可执行的规范化检索式；

③ 检索执行：利用检索式检索索引数据库，并保证检索的速度和准确性；

④ 检索结果组织：对检索中记录的整理组织。

3．缓存数据库系统

缓存数据库系统很大，大到需要几万、几十万台服务器来存储。它不是使用我们常见的各种数据库，而是按照一定编码记录在硬盘上，其实也就是一个自己开发的数据库系统。它的最大特点是索引系统极其发达，它是根据“最小语境含义表达单位（语境根）”来进行排序的。在这里指出一个常见的误区，很多人以为所有搜集并整理后的数据保存在数据库里，用户在搜索时是到这个数据库里面去检索里面的压缩数据。早期和一些小的搜索引擎确实是这样，但是搜索引擎的核心技术不是在查询上面，而是在分析部分，用户查询时，查询系统检索的是预处理系统分析的结果。类似图书馆将书分类放置的过程，网页就像一本书，图书馆的查询系统只是帮我们将这本书找到，它知道书名和大致内容，但是不知道具体内容。当我们在搜索引擎里面打开快照时，就是把这本书“网页”给找出来了。

4．检索过程分析

搜索引擎首先以输入的关键词为搜索条件，如“社会保险”，在其数据库中检索包含该关键词的网页，然后按照“匹配/位置/词频”原则返回网站排名搜索结果。该过程可以分析为：首先用户在搜索引擎的Web页面上输入查询的关键词，Web网页接口会将查询的关键词，提交给查询分析系统，这个查询分析系统根据“语义学习分析系统”生成的“最小语境含义表达单位（语境根）”来分析用户查询的关键词。这里有两种情况：一是用户查询的关键词正好在“最小语境含义表达单位（语境根）”库中就有，那么问题非常简单，分析系统就按照“最小语境含义表达单位（语境根）”的排序直接从缓存数据库中调出结果，交给查询处理系统，处理系统则按照前面的预处理系统分析的权重加以排列，最后生成网页发送给用户。一是“最小语境含义表达单位（语境根）”库中没有对应的关键词，一般而言，这种情况的出现是因为用户查询了一个很长的句子。这种情况并不复杂，查询分析系统一旦发现“最小语境含义表达单位（语境根）”库中没有关键词，那么分析出查询关键词里面包含有哪些词是“最小语境含义表达单位（语境根）”库中有的，按照“文字上尽可能多符合”的原则，找出在数据库中的那个“最小语境含义表达单位（语境根）”的结果。

假如用户搜索了几个关键词，则查询系统将进行一次“交”或者“并”的逻辑与运算，以达到检索目的。

5．网页的数据处理

网页的数据处理的是通过过滤文件系统信息，为文件系统的表达提供一种满意的索引输出，目的是获取最优的索引记录，使用户能很容易地检索到所需信息。

（1）格式过滤：网页数据处理能够过滤不同格式的文档。这使得搜索引擎不仅能够检索文字，而且能够检索原始格式文件的所有信息。

（2）语词切分：语词是信息表达的最小单位，而汉语不同于西方语言，其句子的语词间没有分隔符，因此需要进行语词切分。常用的语词切分方法有按词典进行最大词组匹配、逆向最大词组匹配、最佳匹配法，联想—回溯法、全自动词典切词等。近年来，又出现了基于神经元网络的和专家系统的分词方法和基于统计和频度分析的分词方法。

（3）词法分析：汉语语词切分中存在切分歧义，如句子“网球拍卖完了”，可以切分为“网球／拍卖完了”，也可以切分为“网球拍／卖完了”。因此，需要利用各种上下文知识解决语词切分歧义。此外，还需要对语词进行词法分析，识别出各个语词的词干，以便根据词干建立数据索引。

（4）词性标注和短语识别：在切分的基础上，利用基于规则和统计的方法进行词性标注。在此基础上，还要利用各种语法规则，识别出重要的短语结构。

（5）自动标引：从网页文档中提取出一组能最大程度上概括其内容特征、可作为用户检索入口的关键性数据。用该组数据对文档进行标引，使用户可以通过输入关键数据检索到该文档的简要数据，如标题、摘要、时间、作者和URL等，进一步单击可查询到该文档，如图6-2所示。

（6）自动分类：建立并维护一套完整的分类目录体系，根据文档的信息特征，计算出与其相关程度最大的一个或多个分类，将文档划归到这些分类中去，使用户可以通过浏览分类体系直接查询到该文档。

图6-2　信息分类/标识和检索过程图

6．搜索策略

在抓取网页的时候，网络蜘蛛一般有两种策略：广度优先和深度优先。

（1）广度优先是指网络蜘蛛会先抓取起始网页中链接的所有网页，然后再选择其中的一个链接网页，继续抓取在此网页中链接的所有网页。这是最常用的方式，因为这个方法可以让网络蜘蛛并行处理，提高其抓取速度。

（2）深度优先是指网络蜘蛛会从起始页开始，一个链接一个链接地跟踪下去，处理完这条线路之后再转入下一个起始页，继续跟踪链接。这个方法有个优点是网络蜘蛛在设计的时候比较容易。搜索软件的实现常常用分布式、并行计算技术，以提高信息发现和更新的速度。