<<数学之美>> part4

---

摘要 : [布尔代数] [搜索引擎]

布尔代数

再也没有哪个运算比布尔运算更简单的了,操作数只有0和1,操作符只有and,or,not三种,随便一想就知道只有有限的几种可能的结果,而就连普通的加法,由于操作数的不确定性也有无穷的可能;

And	0	1
0	0	0
1	0	1

Or	0	1
0	0	1
1	1	1

Not	-
0	1
1	0

在我们最开始学布尔代数时,难免心里也会有这样的想法,那就是这到底有什么用?因为它太过于简单了,我们认为加法能做的事都不算多,那这个比加法还简单的东西呢?可能对人来说它能做的真的不多,起码对于我来讲貌似在数学上做一些逻辑运算之外也没有其他的帮助了,起码当时的是我这么认为的;

直到后来学习了计算机相关的知识,我们直到所有的复杂的运算都是由四则运算组成的,而四则运算以及平方开方等等都可以由布尔代数来表达,因为对于计算机也就是一堆硬件电路来说,没法直接处理四则运算这样复杂的运算方式,它只能处理最简单的运算,没错,也就是布尔代数,电路有开关两种状态,可以用于表示布尔代数的0和1,那么我们就可以用无数个电路开关搭建起一个能处理复杂运算的计算器,进而就有了今天的电脑,所以可以说布尔代数是今天无数功能强劲的计算机的最基础理论支撑;

搜索引擎

举一个实际的计算机上的应用如何用布尔代数来表达的例子;

搜索引擎的目的是根据用户输入的一个或者多个关键字,搜索出与之最匹配的网页并返回给用户,这个过程本质是由以下三部分组成:

1. 下载(将互联网上的网页下载下来);
2. 索引(搜索引擎不可能真的去遍历所有网页内容,即便再强大的计算机也没有这个能力,因此需要建立索引);
3. 排序(可能与关键字相关的有多个网页,那么以一个怎样的顺序呈现给用户呢?这就需要根据某些规则排序);

这就是搜索引擎工作的方式,抛去辞藻华丽的算法的外衣后,最本质的不过是由中学知识的人都能大概明白其含义的三板斧:下载,索引,排序;

具体的搜索部分以布尔代数方式表示:

1. 首先获取到关键字A,B,C,需要内容满足A和B,同时不满足C即可;
2. 以布尔代数表示搜索条件:A and B and (not C);
3. 我们知道对应每个关键字,有一串数字用于表示所有文章是否包含有该关键字,例如关键字S:00010001,则含义是第4,8篇文章有该关键字,其余没有,接下来要做的就很简单了,只需要找到关键字A,B,C的二进制串Ta,Tb,Tc,并且运算Ta&Tb&(!Tc)可以得到结果串Tr,则Tr中为1的位置代表的文章满足三个关键字的条件;

可以看到,看似复杂的搜索过程,就可以简单的用布尔代数解决了,同时由于计算机对于布尔代数的运算速度是非常快的(最普通的计算机也可以做到每秒几十亿次运算),所以从性能上来讲也是很好的;

PS:实际上搜索引擎还有诸多问题需要解决:

1. 关键字是非常非常多的,如何存储以及访问;
2. 建立索引;
3. 排序算法;

Thanks Doctor JunWu;