第八章 布尔代数和搜索引擎

技术分为“术”和“道”两种,具体做事方法是术,做事的原则和原理是道。追求术的人一辈子很辛苦,只有掌握本质和精髓才能游刃有余。

  搜索引擎的原理非常简单:自动下载尽可能多的网页;建立快速有效的索引;根据相关性对网页进行公平准确的排序。

1.布尔代数

  二进制是印度学者完成的,但他们没有用0和1计数,后来德国数学家莱布尼兹进一步完善了二进制,用0和1表示它的两个数字。二进制除了是一种技术方式外,还可以表示逻辑的“是”与“非”。布尔是19世纪英国的一位中学数学老师,他出版了一本书阐述如何用数学的方法解决逻辑问题,在此之前人们普遍认为数学和逻辑是两个不同的学科。布尔代数运算的元素之有两个1(true)和0(false),基本运算有“与”、“或”、“非”三种。
  布尔运算刚提出的时候数学家们会疑惑,如此简单的理论能解决什么实际问题,直到提出的80多年后,香农在他的硕士论文里指出用布尔代数实现开关电路,才使得布尔代数成为数字电路的基础。所有的数学和逻辑运算,加减乘除开方乘方等都能转换成二进制的布尔运算,正是依靠这一点人类用一个个开关电路搭出电子计算机。
  文献搜索和布尔运算的关系是,对于一个用户输入的关键词,搜索引擎要判断每篇文献是否有这个关键词,如果一篇文献有它,我们相应给这篇文献一个逻辑值——真,否则给假。一篇文献对于每个条件都有一个ture或false的答案,根据真值表就能算出每篇文献是不是要找的。布尔代数对于数学的意义相当于量子力学对于物理学的意义,它们将对世界的认知从连续的状态扩展到离散状态。

2.索引

  建立索引是提高搜索速度的技巧之一,比如图书馆的索引卡片。当信息检索进入计算机时代后,索引便不再是卡片,而是基于数据库的。数据库的查询语句(SQL)支持各种复杂的逻辑组合,但是背后的原理是基于布尔运算的。
  最简单的索引结构是用一个很长的二进制表示一个关键字是否出现在每篇文献中,有多少篇文献就有多少位二进制,每一位对应一个文献,1代表相应文献有该关键字,0代表没有。比如“原子能”对应的二进制数是0100100010000001...表示第二、五、九、十、十六篇文献包含该关键字;同样假定“应用”对应的二进制是00101001100000001...,那么要找包含“原子能”和“应用”的文献时,只要将这两个二进制进行AND运算即可。由于网页数量和词汇表数量很大,所以索引的大小也将非常大,索引中还有很多附加信息,诸如每个次出现的次数、位置等,因此整个索引表变得非常之大,不是一台服务器能存下的。所以这些索引需要通过分布式的方式存储到不同的服务器上。普遍的做法是根据网页的序号将索引分成很多份(shards),分别存储在不同的服务器中,当接受一个查询时,这个查询被分发到很多服务器中,这些服务器同时并行处理用户的请求,并把结果送到主服务器中进行合并,再将结果返回给用户。

Truth is ever to be found in simplicity,and not in the multiplicity and confusion of things.
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容