数学之美梳理（五）搜索引擎的原理

发表于 更新于 分类于 Waline：

搜索引擎的基础原理其实非常简单，建立一个搜索引擎大致需要这样几件事情：自动下载尽可能的网页，建立快速有效的索引，根据相关性对网页进行公平准确的排序。

布尔代数与索引建立

最简单的索引结构是用一个很长的二进制数表示一个关键字是否出现在每篇文献中。有多少篇文献，就有多少位数，每一位对应一篇文献，1代表相应的文献有这个关键字，0代表没有。

比如关键字“原子能”对应的二进制数是0100100011000001，表示第2，第5，第9，第10，第16篇文献包含这个关键字。这个过程就是将一篇篇千差万别的文本进行量子化的过程。注意，这个二进制数非常之长。

同样，假定“应用”对应的二进制数字是0010100110000001，那么要找到同时包含“原子能”和“应用”的文献时，只要将这两个二进制数进行布尔运算AND，可知结果为0000100000000001，表示第5和第16篇的文献满足要求

注意，计算机做布尔运算是非常快的，现在最便宜的微机都可以在在一秒内进行数十亿次。当然，由于这些数字中绝大部分位数都为0，只需要记录那些等于1的位数即可。

于是，搜索引擎就变成了一张大表，表的每一行对应一个关键词，每一个关键词后面跟着一串数字，是包含该关键词的文献的序号。

对于互联网的搜索引擎来讲，每个网页就是一个文献。互联网网页的数量是巨大的，网络中所用的词非常多，因此这个索引是巨大的，在万亿字节这个量级。显然这不是一台服务器的内存可以存下的，所以要通过分布式的方式存储到不同的服务器上。普遍的做法是根据网页的序号将索引非常多份

图论与网络爬虫

离散数学是当代数学的一个重要分支，也是计算机科学的数学基础。它包括数理逻辑、集合论、图论和近世代数四个分支。数理逻辑基于布尔代数，刚才我们谈了布尔代数和索引的索引的建立，现在我们讨论下图论及其在网络爬虫上的应用。

关于图，最基本的操作就是遍历图中所有的节点，最主要的两种算法是DFS和BFS。

那么我们在构建爬虫的时候，是选择BFS还是DFS呢？

虽然从理论上讲，这两个算法都能够在大致相同的时间内爬下整个“静态”的网络，但是这两个假设——不考虑时间因素，互联网静态不变，在现实中是做不到的，搜索引擎的网络爬虫问题更应该被定义成“如何在有限时间里最多地爬下最重要的网页”。

显然，各个网站最重要的网页应该是它的首页，在最极端的情况下，如果爬虫非常小，只能下载非常有限的网页，那么应该下载的是所有网站的首页，如果爬虫再扩大些，应该爬下从首页直接链接到的网页。在这个前提下，显然BFS是要优于DFS。

那么是否DFS就不是用了呢？也不是这样，这跟爬虫的分布式结构以及网络通信的握手成本有关。所谓握手，就是指下载服务器和网站服务器建立通信的过程，这个过程需要额外的时间，如果握手次数太多，下载的效率就降低了。

实际的网络爬虫是一个由成百上千甚至成千上万台服务器组成的分布式系统。对于某个网站，一般是由特定的一台或者几台服务器专门下载。这些服务器下载完一个网站，再进入下一个网站，这样可以避免握手次数太多。要是下载完第一个网站再来下载第二个，这又有点像DFS，虽然下载同一个网站时，还需要用BFS。

总结来说，网络爬虫对网页遍历的次序不是简单的BFS或者DFS，而是有一个相对复杂的下载优先级排序的算法。管理这个优先级排序的子系统一般称为调度系统，由它来决定下载完成一个网页时，接下来下载哪一个。

PageRank：民主表决式网页排名技术

PageRank的基本原理也很简单：在互联网上，如果一个网页被很多其他网页链接，说明它受到普遍的承认和信赖，那么它的排名就高，这就是PageRank的核心思想。

这个核心思想某种程度上与其他算法相同，就是充分挖掘数据内部隐含的信息，在PageRank中，这个隐含的信息就是：如果一个网页被很多其他网页链接，说明它受到普遍的承认和信赖，PageRank充分利用了这个信息。

当然，Google的PageRank算法实际上要复杂得多，比如对于不同网页的链接区别对打，因为那些排名高的网页的链接更可靠，所以要给这些链接更大的权重。

举个例子，我们知道一个网页Y的排名应该来自于所有指向这个网页的其他网页X1,X2,X3,⋯ ,XkX_1,X_2,X_3,\cdots,X_k 的权重之和。接下来的问题是，X1,X2,X3,⋯ ,XkX_1,X_2,X_3,\cdots,X_k 的权重分别是多少，如何度量。PageRank的作者之一佩奇认为，应该是这些网页本身的网页排名。

现在麻烦来了，计算搜索结果的网页排名的过程需要用到网页本身的排名，这就成了“先有鸡还是先有蛋”的问题了。

破解这个问题的是PageRank的另一个作者布林。他把这个问题变成了一个二位矩阵相乘的问题，并用迭代的方法解决了这个问题。他们先假定所有的网页排名相同，并根据这个初始值，算出各个网页的第一次迭代的排名，然后再根据第一次迭代计算出第二次迭代。

理论问题解决了，接下来解决实际问题，因为互联网上网页的数量是巨大的，上面提到的二维矩阵从理论上讲有网页数量的二次方这么多个元素，假定有10亿个网页，那么二维矩阵就有100亿亿个元素，这么大的矩阵相乘，计算量是非常巨大的，最终佩奇和布林是通过稀疏矩阵的计算技巧来解决了这个问题。

如何确定网页和查询的相关性

影响搜索引擎质量的诸多因素，除了用户的点击数据外，都可以归纳为以下四个方面：

  1. 完备的索引
  2. 对网页质量的度量，如PageRank算法
  3. 用户偏好
  4. 确定一个网页的某个查询的相关性的方法

短语“原子能的应用”可以分成三个关键词：原子能，的，应用。根据直觉，我们知道，这三个词出现较多的网页应该比它们出现较少的网页相关性高。当然，这个方法有一个明显的漏洞，这就是篇幅长的网页比篇幅短的网页占便宜，因为一般来说长网页包含的关键词要多。因此，需要根据网页的长度，对关键词的次数进行归一化，也就是关键词的次数除以网页的总字数。我们把这个商称为“关键词的频率”，或者“单文本词频”（Term Frequency）。

因此，度量网页和查询的相关性，有一个简单的方法，就是直接使用各个关键词在网页中出现的总词频。具体的讲，如果一个查询包括N个关键词 w_1,w_2,w_3,\cdotsw_N ，它们在一个特定网页中的词频分别是：TF1,TF2,⋯ ,TFNTF_1,TF_2,\cdots,TF_N，那么这个查询和该网页的相关性就是：

TF1+TF2,⋯ ,+TFNTF_1 + TF_2, \cdots, + TF_N

这里有两个漏洞：

  1. 在上面的例子中，“的”这个词占了总词频的80%以上，而它对确定网页的主题几乎没什么用处。我们称这种词位“停止词”，也就是说，在度量相关性时不应该考虑他们的概率
  2. 在汉语中，应用是个很通用的词，而原子能是个很专业的词，后者在相关性排名中应该比前者重要，因此，需要对汉语中每一个词一个权重，这个权重的设定必须满足以下两个条件：
    （1）一个词预测主题的能力越强，权重越大
    （2）停止词的权重为0

我们很容易发现，如果一个关键词只在很少的网页中出现，通过它就很容易锁定目标，它的权重也就应该大。反之，如果一个词在大量网页中出现，看到它仍然不清楚要找什么内容，它的权重就应该小。

概括地讲，假定一个关键词w在DwD_w 个网页中出现，那么DwD_w 越大，w的权重越小。在信息检索中，使用最多的是“逆文本频率”（Inverse Docuemnt Frequency， IDF），它的公式为log(DDw)log(\frac{D}{D_w})，其中D是全部网页数。

比如，假定中文网页数是10亿，停止词“的”在所有网页中都出现，即DwD_w 也是10亿，那么IDF = log(1) = 0，假设“原子能”在200万个网页中出现，那么Dw=200万D_w = 200万 ，则它的IDF = log(500) = 8.96，又假定“应用”出现在5亿个网页中，那么它的IDF = log(2) = 1。

也就是说，在网页中找到一个“原子能”的命中率相当于找到九个“应用”，利用IDF，相关性的计算公式就变为：

TF1⋅IDF1+TF2⋅IDF2+…+TFN⋅IDFNTF_1 \cdot IDF_1 + TF_2 \cdot IDF_2 + \ldots + TF_N \cdot IDF_N

所谓IDF，就是一个特定条件下关键词的概率分布的交叉熵。