数学应用-简单之美:布尔代数和搜索引擎的索引

发表者: 吴军,Google 研究员

[建立一个搜索引擎大致需要做这样几件事:自动下载尽可能多的网页;建立快 速 有 效 的 索 引 ; 根 据 相 关 性 对 网 页 进 行 公 平 准 确 的 排 序 。 我 们 在 介 绍 Google Page Rank (网页排名) 时已经谈到了一些排序的,这里我们谈谈索引, 以后我们还会谈如何度量网页的相关性,和进行网页自动下载。]

世界上不可能有比二进制更简单的计数方法了,也不可能有比布尔运算更简单的 运算了。尽管今天每个搜索引擎都宣称自己如何聪明、多么智能化,其实从根本 上讲都没有逃出布尔运算的框框。

布尔 (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-NOT一种运 算)。全部运算只用下列几张真值表就能完全地描述清楚。

AND | 1 0

———————– 1 | 1 0 0 | 0 0

这张表说明如果 AND 运算的两个元素有一个是 0,则运算结果总是 0。如果两 个元素都是 1,运算结果是 1。例如,“太阳从西边升起”这个判断是假的 (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 年香农在他的硕士论文中指出用布尔代数来实现开关电路,才使 得布尔代数成为数字电路的基础。所有的数学和逻辑运算,加、减、乘、除、乘 方、开方等等,全部 能转换成二值的布尔运算。

现在我们看看文献检索和布尔运算的关系。对于一个用户输入的关键词,搜索引 擎要判断每篇文献是否含有这个关键 词,如果一篇文献含有它,我们相应地给 这篇文献一个逻辑值 — 真(TRUE,或 1),否则,给一个逻辑值 — 假(FALSE, 或 0)。比如我们要找有关原子能应用的文献,但并不想知道如何造原子弹。我 们可以这样写一个查询语句“原子能 AND 应用 AND (NOT 原子弹)”,表示符合 要求的文献必须同时满足三个条件: – 包含原子能 – 包含应用

– 不包含原子弹

一篇文献对于上面每一个条件,都有一个 True 或者 False 的答案,根据上述 真值表就能算出每篇文献是否是要找的。

早期的文献检索查询系统大多基于数据库,严格要求查询语句符合布尔运算。今 天的搜索引擎相比之下要聪明的多,它自动把用户的查询语句转换成布尔运算的 算式。当然在查询时,不能将每篇文献扫描一遍,来看看它是否满足上面三个条 件,因此需要建立一个索引。

最 简单索引的结构是用一个很长的二进制数表示一个关键字是否出现在每篇文 献中。有多少篇文献,就有多少位数,每一位对应一篇文献,1 代表相应的文献 有这个关键字,0 代表没有。比如关键字“原子能”对应的二进制数是 0100100001100001…,表示第二、第五、第九、第十、第十六篇文献包含着个 关键字。注 意,这个二进制数非常之长。同样,我们假定“应用”对应的二进 制数是 0010100110000001…。那么要找到同时包含“原子能”和“应用”的文 献时,只要将这两个二进制数进行布尔运算 AND。根据上面的真值表,我们知道 运算结果是 0000100000000001…。表示第五篇,第十六篇文献满足要求。

注意,计算 机作布尔运算是非常非常快的。现在最便宜的微机都可以一次进行 三十二位布尔运算,一秒钟进行十亿次以上。当然,由于这些二进制数中绝大部 分位数都是零,我 们只需要记录那些等于 1 的位数即可。于是,搜索引擎的索 引就变成了一张大表:表的每一行对应一个关键词,而每一个关键词后面跟着一

组数字,是包含该关键词 的文献序号。

对于互联网的搜索引擎来讲,每一个网页就是一个文献。互联网的网页数量是巨 大的,网络中所用的词也非常非常多。因此这个索引 是巨大的,在万亿字节这 个量级。早期的搜索引擎(比如 Alta Vista 以前的所有搜索引擎),由于受计 算机速度和容量的限制,只能对重要的关键的主题词建立索引。至今很多学术杂 志还要求作者提供 3-5 个关键词。这样所有不常见的词和太常见的虚词就找不 到了。现在,为了保证对任何搜索都能提供相关的网页,所有的搜索引擎都是对 所有的词进行索引。为了网页 排名方便,索引中还需存有大量附加信息,诸如 每个词出现的位置、次数等等。因此,整个索引就变得非常之大,以至于不可能 用一台计算机存下。大家普遍的做法 就是根据网页的序号将索引分成很多份 (Shards),分别存储在不同的服务器中。每当接受一个查询时,这个查询就被 分送到许许多多服务器中,这些服务器 同时并行处理用户请求,并把结果送到 主服务器进行合并处理,最后将结果返回给用户。

不管索引如何复杂,查找的基本操作仍然是布尔运算。布 尔运算把逻辑和数学 联系起来了。它的最大好处是容易实现,速度快,这对于海量的信息查找是至关 重要的。它的不足是只能给出是与否的判断,而不能给出量化的 度量。因此, 所有搜索引擎在内部检索完毕后,都要对符合要求的网页根据相关性排序,然后 才返回给用户。

声明: 除非转自他站(如有侵权,请联系处理)外,本文采用 BY-NC-SA 协议进行授权 | 智乐兔
转载请注明:转自《数学应用-简单之美:布尔代数和搜索引擎的索引
本文地址:https://www.zhiletu.com/archives-2798.html
关注公众号:智乐兔

赞赏

wechat pay微信赞赏alipay pay支付宝赞赏

上一篇
下一篇

相关文章

在线留言

你必须 登录后 才能留言!

在线客服
在线客服 X

售前: 点击这里给我发消息
售后: 点击这里给我发消息

智乐兔官微