数学之美 不同语言的冗余度差别很大，而汉语在所有语言中冗余度是 相对小的。这和人们普遍的认识“汉语是最简洁的语言”是一致 的。 在下一集中，我们将介绍信息熵在信息处理中的应用以及两 个相关的概念互信息和相对熵。 对中文信息熵有兴趣的读者可以读我和王作英教授在电子学 报上合写的一篇文章 《语信息熵和语言模型的复杂度》 1.5.数学之美系列五一简单之美：布尔代数和搜索引擎 的索引 2006年5月10日上午09：10：00 发表者：吴军，Google研究员 [建立一个搜索引擎大致需要做这样几件事：自动下载尽可能多 的网页；建立快速有效的索引；根据相关性对网页进行公平准确 的排序。我们在介绍Google Page Rank(网页排名)时已经谈 到了一些排序的问题，这里我们谈谈索引问题，以后我们还会谈 如何度量网页的相关性，和进行网页自动下载。] 17
数学之美 不同语言的冗余度差别很大，而汉语在所有语言中冗余度是 相对小的。这和人们普遍的认识“汉语是最简洁的语言”是一致 的。 在下一集中， 我们将介绍信息熵在信息处理中的应用以及两 个相关的概念互信息和相对熵。 对中文信息熵有兴趣的读者可以读我和王作英教授在电子学 报上合写的一篇文章 《语信息熵和语言模型的复杂度》 1.5. 数学之美系列五 — 简单之美：布尔代数和搜索引擎 的索引 2006 年 5 月 10 日 上午 09:10:00 发表者: 吴军，Google 研究员 [建立一个搜索引擎大致需要做这样几件事：自动下载尽可能多 的网页；建立快速有效的索引；根据相关性对网页进行公平准确 的排序。我们在介绍 Google Page Rank (网页排名) 时已经谈 到了一些排序的问题，这里我们谈谈索引问题，以后我们还会谈 如何度量网页的相关性，和进行网页自动下载。］ 17
数学之美 世界上不可能有比二进制更简单的计数方法了，也不可能有 比布尔运算更简单的运算了。尽管今天每个搜索引擎都宣称自己 如何聪明、多么智能化，其实从根本上讲都没有逃出布尔运算的 框框。 布尔(George Boole)是十九世纪英国一位小学数学老师。 他生前没有人认为他是数学家。布尔在工作之余，喜欢阅读数学 论著、思考数学问题。l854年“思维规律”(An Investigation of the Laws of Thought,on which are founded the Mathematical Theories of Logic and Probabilities), 第一次向人们展示了如何用数学的方法解决逻辑问题。 布尔代数简单得不能再简单了。运算的元素只有两个1 (TRUE,真)和O (FALSE,.假)。基本的运算只有“与”(AND)、“或”(OR) 和“非”(N0T)三种（后来发现，这三种运算都可以转换成“与” “非”AND-NOT一种运算)。全部运算只用下列几张真 值表就能完全地描述清楚。 AND 1 0 1110 0100 这张表说明如果AND运算的两个元素有一个是0，则运算结 果总是0。如果两个元素都是1，运算结果是1。例如，“太阳 18
数学之美 世界上不可能有比二进制更简单的计数方法了，也不可能有 比布尔运算更简单的运算了。尽管今天每个搜索引擎都宣称自己 如何聪明、多么智能化，其实从根本上讲都没有逃出布尔运算的 框框。 布尔（George Boole) 是十九世纪英国一位小学数学老师。 他生前没有人认为他是数学家。布尔在工作之余，喜欢阅读数学 论著、思考数学问题。1854 年“思维规律”（An Investigation of the Laws of Thought, on which are founded the Mathematical Theories of Logic and Probabilities）一书， 第一次向人们展示了如何用数学的方法解决逻辑问题。 布尔代数简单得不能再简单了。运算的元素只有两个 1 （TRUE， 真) 和 0 （FALSE，假)。基本的运算只有“与”（AND)、“或” (OR) 和“非”（NOT) 三种（后来发现，这三种运算都可以转换成“与” “非” ＡＮＤ－ＮＯＴ一种运算）。全部运算只用下列几张真 值表就能完全地描述清楚。 AND | 1 0 ----------------------- 1 | 1 0 0 | 0 0 这张表说明如果 AND 运算的两个元素有一个是 0，则运算结 果总是 0。如果两个元素都是 1，运算结果是 1。例如，“太阳 18
数学之美 从西边升起”这个判断是假的(0)，“水可以流动”这个判断是真 的(1)，那么，“太阳从西边升起并且水可以流动”就是假的 (0)。 0R|10 1111 0110 这张表说明如果O运算的两个元素有一个是1，则运算结果 总是1。如果两个元素都是0，运算结果是0。比如说，“张三 是比赛第一名”这个结论是假的（0)，“李四是比赛第一名” 是真的(1)，那么“张三或者李四是第一名”就是真的(1)。 NOT I 110 0」1 这张表说明N0T运算把1变成0，把0变成1。比如，如 果“象牙是白的”是真的(1)，那么“象牙不是白的”必定是 假的（0)。 读者也许会问这么简单的理论能解决什么实际问题。布尔同 时代的数学家们也有同样的问题。事实上在布尔代数提出后80 多年里，它确实没有什么像样的应用，直到1938年香农在他的 硕士论文中指出用布尔代数来实现开关电路，才使得布尔代数成 为数字电路的基础。所有的数学和逻辑运算，加、减、乘、除、 乘方、开方等等，全部能转换成二值的布尔运算
数学之美 从西边升起”这个判断是假的(0),“水可以流动”这个判断是真 的（1），那么，“太阳从西边升起并且水可以流动”就是假的 （0）。 OR | 1 0 1 | 1 1 0 | 1 0 这张表说明如果 OR 运算的两个元素有一个是 1，则运算结果 总是 1。如果两个元素都是 0，运算结果是 0。比如说，“张三 是比赛第一名”这个结论是假的（0），“李四是比赛第一名” 是真的（1），那么“张三或者李四是第一名”就是真的（1）。 NOT | 1 | 0 0 | 1 这张表说明 NOT 运算把 1 变成 0，把 0 变成 1。比如，如 果“象牙是白的”是真的（1），那么“象牙不是白的”必定是 假的（0）。 读者也许会问这么简单的理论能解决什么实际问题。布尔同 时代的数学家们也有同样的问题。事实上在布尔代数提出后 80 多年里，它确实没有什么像样的应用，直到 1938 年香农在他的 硕士论文中指出用布尔代数来实现开关电路，才使得布尔代数成 为数字电路的基础。所有的数学和逻辑运算，加、减、乘、除、 乘方、开方等等，全部能转换成二值的布尔运算。 19
数学之美 现在我们看看文献检索和布尔运算的关系。对于一个用户输 入的关键词，搜索引擎要判断每篇文献是否含有这个关键词，如 果一篇文献含有它，我们相应地给这篇文献一个逻辑值-一真 (TRUE,或1)，否则，给一个逻辑值-假(FALSE,.或0)。 比如我们要找有关原子能应用的文献，但并不想知道如何造原子 弹。我们可以这样写一个查询语句“原子能AND应用AND(NOT 原子弹)”，表示符合要求的文献必须同时满足三个条件： -包含原子能 一包含应用 -不包含原子弹 一篇文献对于上面每一个条件，都有一个True或者False 的答案，根据上述真值表就能算出每篇文献是否是要找的。 早期的文献检索查询系统大多基于数据库，严格要求查询语 句符合布尔运算。今天的搜索引擎相比之下要聪明的多，它自动 把用户的查询语句转换成布尔运算的算式。当然在查询时，不能 将每篇文献扫描一遍，来看看它是否满足上面三个条件，因此需 要建立一个索引。 最简单索引的结构是用一个很长的二进制数表示一个关键字 是否出现在每篇文献中。有多少篇文献，就有多少位数，每一位 对应一篇文献，1代表相应的文献有这个关键字，0代表没有。 比如关键字“原子能”对应的二进制数是0100100001100001..， 表示第二、第五、第九、第十、第十六篇文献包含着个关键字。 20
数学之美 现在我们看看文献检索和布尔运算的关系。对于一个用户输 入的关键词，搜索引擎要判断每篇文献是否含有这个关键词，如 果一篇文献含有它，我们相应地给这篇文献一个逻辑值 -- 真 （TRUE,或 1），否则，给一个逻辑值 -- 假（FALSE, 或 0）。 比如我们要找有关原子能应用的文献，但并不想知道如何造原子 弹。我们可以这样写一个查询语句“原子能 AND 应用 AND (NOT 原子弹)”，表示符合要求的文献必须同时满足三个条件： - 包含原子能 - 包含应用 - 不包含原子弹 一篇文献对于上面每一个条件，都有一个 True 或者 False 的答案，根据上述真值表就能算出每篇文献是否是要找的。 早期的文献检索查询系统大多基于数据库，严格要求查询语 句符合布尔运算。今天的搜索引擎相比之下要聪明的多，它自动 把用户的查询语句转换成布尔运算的算式。当然在查询时，不能 将每篇文献扫描一遍，来看看它是否满足上面三个条件，因此需 要建立一个索引。 最简单索引的结构是用一个很长的二进制数表示一个关键字 是否出现在每篇文献中。有多少篇文献，就有多少位数，每一位 对应一篇文献，1 代表相应的文献有这个关键字，0 代表没有。 比如关键字“原子能”对应的二进制数是 0100100001100001...， 表示第二、第五、第九、第十、第十六篇文献包含着个关键字。 20
数学之美 注意，这个二进制数非常之长。同样，我们假定“应用”对应的 二进制数是0010100110000001..。那么要找到同时包含“原子 能”和“应用”的文献时，只要将这两个二进制数进行布尔运算 AND。根据上面的真值表，我们知道运算结果是 0000100000000001.·。表示第五篇，第十六篇文献满足要求。 注意，计算机作布尔运算是非常非常快的。现在最便宜的微 机都可以一次进行三十二位布尔运算，一秒钟进行十亿次以上。 当然，由于这些二进制数中绝大部分位数都是零，我们只需要记 录那些等于1的位数即可。于是，搜索引擎的索引就变成了一张 大表：表的每一行对应一个关键词，而每一个关键词后面跟着一 组数字，是包含该关键词的文献序号。 对于互联网的搜索引擎来讲，每一个网页就是一个文献。互 联网的网页数量是巨大的，网络中所用的词也非常非常多。因此 这个索引是巨大的，在万亿字节这个量级。早期的搜索引擎（比 如Alta Vista以前的所有搜索引擎)，由于受计算机速度和容 量的限制，只能对重要的关键的主题词建立索引。至今很多学术 杂志还要求作者提供3-5个关键词。这样所有不常见的词和太 常见的虚词就找不到了。现在，为了保证对任何搜索都能提供相 关的网页，所有的搜索引擎都是对所有的词进行索引。为了网页 排名方便，索引中还需存有大量附加信息，诸如每个词出现的位 置、次数等等。因此，整个索引就变得非常之大，以至于不可能 用一台计算机存下。大家普遍的做法就是根据网页的序号将索引 21
数学之美 注意，这个二进制数非常之长。同样，我们假定“应用”对应的 二进制数是 0010100110000001...。那么要找到同时包含“原子 能”和“应用”的文献时，只要将这两个二进制数进行布尔运算 AND。根据上面的真值表，我们知道运算结果是 0000100000000001...。表示第五篇，第十六篇文献满足要求。 注意，计算机作布尔运算是非常非常快的。现在最便宜的微 机都可以一次进行三十二位布尔运算，一秒钟进行十亿次以上。 当然，由于这些二进制数中绝大部分位数都是零，我们只需要记 录那些等于 1 的位数即可。于是，搜索引擎的索引就变成了一张 大表：表的每一行对应一个关键词，而每一个关键词后面跟着一 组数字，是包含该关键词的文献序号。 对于互联网的搜索引擎来讲，每一个网页就是一个文献。互 联网的网页数量是巨大的，网络中所用的词也非常非常多。因此 这个索引是巨大的，在万亿字节这个量级。早期的搜索引擎（比 如 Alta Vista 以前的所有搜索引擎），由于受计算机速度和容 量的限制，只能对重要的关键的主题词建立索引。至今很多学术 杂志还要求作者提供 3-5 个关键词。这样所有不常见的词和太 常见的虚词就找不到了。现在，为了保证对任何搜索都能提供相 关的网页，所有的搜索引擎都是对所有的词进行索引。为了网页 排名方便，索引中还需存有大量附加信息，诸如每个词出现的位 置、次数等等。因此，整个索引就变得非常之大，以至于不可能 用一台计算机存下。大家普遍的做法就是根据网页的序号将索引 21