数学之美 分成很多份(Shards),分别存储在不同的服务器中。每当接受 一个查询时，这个查询就被分送到许许多多服务器中，这些服务 器同时并行处理用户请求，并把结果送到主服务器进行合并处 理，最后将结果返回给用户。 不管索引如何复杂，查找的基本操作仍然是布尔运算。布尔 运算把逻辑和数学联系起来了。它的最大好处是容易实现，速度 快，这对于海量的信息查找是至关重要的。它的不足是只能给出 是与否的判断，而不能给出量化的度量。因此，所有搜索引擎在 内部检索完毕后，都要对符合要求的网页根据相关性排序，然后 才返回给用户。 1.6.数学之美系列六一图论和网络爬虫(Web Crawlers) 2006年5月15日上午07：15：00 发表者：吴军，Google研究员 [离散数学是当代数学的一个重要分支，也是计算机科学的数学 基础。它包括数理逻辑、集合论、图论和近世代数四个分支。数 理逻辑基于布尔运算，我们已经介绍过了。这里我们介绍图论和 互联网自动下载工具网络爬虫(Web Crawlers)之间的关系。顺 便提一句，我们用Google Trends来搜索一下“离散数学”这 22
数学之美 分成很多份（Shards)，分别存储在不同的服务器中。每当接受 一个查询时，这个查询就被分送到许许多多服务器中，这些服务 器同时并行处理用户请求，并把结果送到主服务器进行合并处 理，最后将结果返回给用户。 不管索引如何复杂，查找的基本操作仍然是布尔运算。布尔 运算把逻辑和数学联系起来了。它的最大好处是容易实现，速度 快，这对于海量的信息查找是至关重要的。它的不足是只能给出 是与否的判断，而不能给出量化的度量。因此，所有搜索引擎在 内部检索完毕后，都要对符合要求的网页根据相关性排序，然后 才返回给用户。 1.6. 数学之美系列六 — 图论和网络爬虫 (Web Crawlers) 2006 年 5 月 15 日 上午 07:15:00 发表者: 吴军，Google 研究员 [离散数学是当代数学的一个重要分支，也是计算机科学的数学 基础。它包括数理逻辑、集合论、图论和近世代数四个分支。数 理逻辑基于布尔运算，我们已经介绍过了。这里我们介绍图论和 互联网自动下载工具网络爬虫 (Web Crawlers) 之间的关系。顺 便提一句，我们用 Google Trends 来搜索一下“离散数学”这 22
数学之美 个词，可以发现不少有趣的现象。比如，武汉、哈尔滨、合肥和 长沙市对这一数学题目最有兴趣的城市。] 我们上回谈到了如何建立搜索引擎的索引，那么如何自动下 载互联网所有的网页呢，它要用到图论中的遍历(Traverse)算 法。 图论的起源可追溯到大数学家欧拉(Leonhard Euler)。1736 年欧拉来到德国的哥尼斯堡(Konigsberg,大哲学家康德的故乡， 现在是俄罗斯的加里宁格勒)，发现当地市民们有一项消遣活动， 就是试图将下图中的每座桥恰好走过一遍并回到原出发点，从来 没有人成功过。欧拉证明了这件事是不可能的，并写了一篇论文， 一般认为这是图论的开始。 图论中所讨论的的图由一些节点和连接这些节点的弧组成。 如果我们把中国的城市当成节点，连接城市的国道当成弧，那么 全国的公路干线网就是图论中所说的图。关于图的算法有很多， 但最重要的是图的遍历算法，也就是如何通过弧访问图的各个节 23
数学之美 个词，可以发现不少有趣的现象。比如，武汉、哈尔滨、合肥和 长沙市对这一数学题目最有兴趣的城市。] 我们上回谈到了如何建立搜索引擎的索引，那么如何自动下 载互联网所有的网页呢，它要用到图论中的遍历（Traverse) 算 法。 图论的起源可追溯到大数学家欧拉（Leonhard Euler）。1736 年欧拉来到德国的哥尼斯堡（Konigsberg，大哲学家康德的故乡， 现在是俄罗斯的加里宁格勒），发现当地市民们有一项消遣活动， 就是试图将下图中的每座桥恰好走过一遍并回到原出发点，从来 没有人成功过。欧拉证明了这件事是不可能的，并写了一篇论文， 一般认为这是图论的开始。 图论中所讨论的的图由一些节点和连接这些节点的弧组成。 如果我们把中国的城市当成节点，连接城市的国道当成弧，那么 全国的公路干线网就是图论中所说的图。关于图的算法有很多， 但最重要的是图的遍历算法，也就是如何通过弧访问图的各个节 23
数学之美 点。以中国公路网为例，我们从北京出发，看一看北京和哪些城 市直接相连，比如说和天津、济南、石家庄、南京、沈阳、大同 直接相连。我们可以依次访问这些城市，然后我们看看都有哪些 城市和这些已经访问过的城市相连，比如说北戴河、秦皇岛与天 津相连，青岛、烟台和济南相连，太原、郑州和石家庄相连等等， 我们再一次访问北戴河这些城市，直到中国所有的城市都访问过 一遍为止。这种图的遍历算法称为“广度优先算法”(BFS),因 为它先要尽可能广地访问每个节点所直接连接的其他节点。另外 还有一种策略是从北京出发，随便找到下一个要访问的城市，比 如是济南，然后从济南出发到下一个城市，比如说南京，再访问 从南京出发的城市，一直走到头。然后再往回找，看看中间是否 有尚未访问的城市。这种方法叫“深度优先算法”(DFS),因为 它是一条路走到黑。这两种方法都可以保证访问到全部的城市。 当然，不论采用哪种方法，我们都应该用一个小本本，记录已经 访问过的城市，以防同一个城市访问多次或者漏掉哪个城市。 现在我们看看图论的遍历算法和搜索引擎的关系。互联网其 实就是一张大图，我们可以把每一个网页当作一个节点，把那些 超链接(Hyperlinks)当作连接网页的弧。很多读者可能已经注 意到，网页中那些蓝色的、带有下划线的文字背后其实藏着对应 的网址，当你点下去的的时侯，浏览器是通过这些隐含的网址转 到相应的网页中的。这些隐含在文字背后的网址称为“超链接”。 有了超链接，我们可以从任何一个网页出发，用图的遍历算法， 24
数学之美 点。以中国公路网为例，我们从北京出发，看一看北京和哪些城 市直接相连，比如说和天津、济南、石家庄、南京、沈阳、大同 直接相连。我们可以依次访问这些城市，然后我们看看都有哪些 城市和这些已经访问过的城市相连，比如说北戴河、秦皇岛与天 津相连，青岛、烟台和济南相连，太原、郑州和石家庄相连等等， 我们再一次访问北戴河这些城市，直到中国所有的城市都访问过 一遍为止。这种图的遍历算法称为“广度优先算法”（BFS)，因 为它先要尽可能广地访问每个节点所直接连接的其他节点。另外 还有一种策略是从北京出发，随便找到下一个要访问的城市，比 如是济南，然后从济南出发到下一个城市，比如说南京，再访问 从南京出发的城市，一直走到头。然后再往回找，看看中间是否 有尚未访问的城市。这种方法叫“深度优先算法”（DFS)，因为 它是一条路走到黑。这两种方法都可以保证访问到全部的城市。 当然，不论采用哪种方法，我们都应该用一个小本本，记录已经 访问过的城市，以防同一个城市访问多次或者漏掉哪个城市。 现在我们看看图论的遍历算法和搜索引擎的关系。互联网其 实就是一张大图，我们可以把每一个网页当作一个节点，把那些 超链接（Hyperlinks)当作连接网页的弧。很多读者可能已经注 意到，网页中那些蓝色的、带有下划线的文字背后其实藏着对应 的网址，当你点下去的的时候，浏览器是通过这些隐含的网址转 到相应的网页中的。这些隐含在文字背后的网址称为“超链接”。 有了超链接，我们可以从任何一个网页出发，用图的遍历算法， 24
数学之美 自动地访问到每一个网页并把它们存起来。完成这个功能的程序 叫做网络爬虫，或者在一些文献中称为"机器人"(Robot)。世界 上第一个网络爬虫是由麻省理工学院(MIT)的学生马休.格雷 (Matthew Gray)在1993年写成的。他给他的程序起了个名字 叫“互联网漫游者”("www wanderer")。以后的网络爬虫越写越 复杂，但原理是一样的。 我们来看看网络爬虫如何下载整个互联网。假定我们从一家 门户网站的首页出发，先下载这个网页，然后通过分析这个网页， 可以找到藏在它里面的所有超链接，也就等于知道了这家门户网 站首页所直接连接的全部网页，诸如雅虎邮件、雅虎财经、雅虎 新闻等等。我们接下来访问、下载并分析这家门户网站的邮件等 网页，又能找到其他相连的网页。我们让计算机不停地做下去， 就能下载整个的互联网。当然，我们也要记载哪个网页下载过了， 以免重复。在网络爬虫中，我们使用一个称为“哈希表”(Hash Table)的列表而不是一个记事本纪录网页是否下载过的信息。 现在的互联网非常巨大，不可能通过一台或几台计算机服务 器就能完成下载任务。比如雅虎公司(Google没有公开公布我 们的数目，所以我这里举了雅虎的索引大小为例)宣称他们索引 了200亿个网页，假如下载一个网页需要一秒钟，下载这200 亿个网页则需要634年。因此，一个商业的网络爬虫需要有成 千上万个服务器，并且由快速网络连接起来。如何建立这样复杂 25
数学之美 自动地访问到每一个网页并把它们存起来。完成这个功能的程序 叫做网络爬虫，或者在一些文献中称为"机器人"（Robot)。世界 上第一个网络爬虫是由麻省理工学院 (MIT)的学生马休.格雷 （Matthew Gray)在 1993 年写成的。他给他的程序起了个名字 叫“互联网漫游者”("www wanderer")。以后的网络爬虫越写越 复杂，但原理是一样的。 我们来看看网络爬虫如何下载整个互联网。假定我们从一家 门户网站的首页出发，先下载这个网页，然后通过分析这个网页， 可以找到藏在它里面的所有超链接，也就等于知道了这家门户网 站首页所直接连接的全部网页，诸如雅虎邮件、雅虎财经、雅虎 新闻等等。我们接下来访问、下载并分析这家门户网站的邮件等 网页，又能找到其他相连的网页。我们让计算机不停地做下去， 就能下载整个的互联网。当然，我们也要记载哪个网页下载过了， 以免重复。在网络爬虫中，我们使用一个称为“哈希表”(Hash Table)的列表而不是一个记事本纪录网页是否下载过的信息。 现在的互联网非常巨大，不可能通过一台或几台计算机服务 器就能完成下载任务。比如雅虎公司（Google 没有公开公布我 们的数目，所以我这里举了雅虎的索引大小为例）宣称他们索引 了 200 亿个网页，假如下载一个网页需要一秒钟，下载这 200 亿个网页则需要 634 年。因此，一个商业的网络爬虫需要有成 千上万个服务器，并且由快速网络连接起来。如何建立这样复杂 25
数学之美 的网络系统，如何协调这些服务器的任务，就是网络设计和程序 设计的艺术了。 1.7.数学之美系列七一信息论在信息处理中的应用 2006年5月25日上午07：56：00 发表者：吴军，Google研究员 我们已经介绍了信息熵，它是信息论的基础，我们这次谈谈 信息论在自然语言处理中的应用。 先看看信息熵和语言模型的关系。我们在系列二中谈到语言 模型时，没有讲如何定量地衡量一个语言模型的好坏，当然，读 者会很自然地想到，既然语言模型能减少语音识别和机器翻译的 错误，那么就拿一个语音识别系统或者机器翻译软件来试试，好 的语言模型必然导致错误率较低。这种想法是对的，而且今天的 语音识别和机器翻译也是这么做的。但这种测试方法对于研发语 言模型的人来讲，既不直接、又不方便，而且很难从错误率反过 来定量度量语言模型。事实上，在贾里尼克(Fred Jelinek)的人 研究语言模型时，世界上既没有像样的语音识别系统，更没有机 器翻译。我们知道，语言模型是为了用上下文预测当前的文字， 模型越好，预测得越准，那么当前文字的不确定性就越小。 26
数学之美 的网络系统，如何协调这些服务器的任务，就是网络设计和程序 设计的艺术了。 1.7. 数学之美系列七 — 信息论在信息处理中的应用 2006 年 5 月 25 日 上午 07:56:00 发表者：吴军, Google 研究员 我们已经介绍了信息熵，它是信息论的基础，我们这次谈谈 信息论在自然语言处理中的应用。 先看看信息熵和语言模型的关系。我们在系列一中谈到语言 模型时，没有讲如何定量地衡量一个语言模型的好坏，当然，读 者会很自然地想到，既然语言模型能减少语音识别和机器翻译的 错误，那么就拿一个语音识别系统或者机器翻译软件来试试，好 的语言模型必然导致错误率较低。这种想法是对的，而且今天的 语音识别和机器翻译也是这么做的。但这种测试方法对于研发语 言模型的人来讲，既不直接、又不方便，而且很难从错误率反过 来定量度量语言模型。事实上，在贾里尼克(Fred Jelinek)的人 研究语言模型时，世界上既没有像样的语音识别系统，更没有机 器翻译。我们知道，语言模型是为了用上下文预测当前的文字， 模型越好，预测得越准，那么当前文字的不确定性就越小。 26