keyword：布尔代数,搜索引擎,索引

本章开始介绍搜索引擎的相关技术。作者主要所讲的是搜索引擎的相关原理和原则，并非几个具体的方法 ，旨在授“道”。 搜索引擎的原理其实很简单，建立一个搜索引擎大致需要完成以下三件事：

1. 自动下载尽可能多的网页；

2. 建立快速有效的索引；

3. 根据相关性对网页进行公平准确的排序；

本章所讲的是第二步，即索引的建立，因为索引是最基础，也是最重要的一部分。

布尔代数

布尔代数就是我们所知的二进制1（TRUE，真）和0（FALSE，假）的与（AND）、或（OR）、非（NOT）三种运算。

就是这样一个如此简单的理论，成为了数字电路的基础。而文献检索和布尔代数的关系为：

对于用户输入的关键词，搜索引擎要判断每篇文献是否包含这个词：

• 如果一篇文献包括这个词，我们给这篇文献一个逻辑值—-真（TRUE，1）；
• 如果一篇文献不含这个词，我们给这篇文献一个逻辑值—-假（FALSE，0）；

例如要查询有关原子能应用，而不想知道如何造原子弹的文献。

-> 原子能 AND 应用 AND （NOT 原子弹）

一篇文献对于上述的三个词，都有一个TRUE或者FALSE的答案，再根据上述查询语句的与或非关系进行运算， 最终得到一个TRUE或者FALSE的结果。

索引

大部分搜索引擎都能在零点零几秒内呈现搜索结果，显然，不是等到用户提交查询语句后再去上亿的网页中去查询，做布尔运算的。 这里面有一个的奥秘就是建立索引。这就如同科技读物末尾的索引，或者图书馆的索引。 只不过，搜索引擎依靠的不是图书馆的索引卡片，而是基于数据库的。数据库的查询语句支持各种复杂的逻辑组合， 但是背后的基本原理是基于布尔运算的。

早期的文献检索系统严格要求查询语句符合布尔运算，而如今的搜索引擎会自动把用户的查询语句转换为布尔运算的算式。 但是基本原理并没有什么不同。

最简单的索引结构是用很长的二进制数来表示一个关键字是否出现在每篇文章中。有多少文章，这个二进制数就有多少位。 对于词汇表中的每个词，都会生成一个这样的二进制数。最终根据检索语句，用其中关键词对应的二进制数做相应的布尔运算， 将结果中1所在的位置提取出来，便可得到检索到的文章或者网页了。

上面说的是最基本的索引原理，实际应用中，会进行很多的工作：

1. 二进制数中的大部分位为0，因此我们只需记录等于1的位数即可。于是索引就变成了一张大表：表的每一行对应一个关键词 而每一个关键词后跟着一组数字，是包含该关键词的文献序号。

2. 为了保证对任何搜索都能提供相关的网页，常见的搜索引擎会对所有词进行索引，但是这个数量是巨大的。假如互联网有100亿有意义的网页， 而词汇表的大小是30万，那么这个索引的大小是3000万亿。而考虑到一些词只出现在一部分文本，压缩比为100:1，也有300万亿的数量。 为了网页排名，索引还需要存大量的附加信息，例如每个词出现的位置、次数。所以索引需要通过分布式的方式存储到不同的服务器。 普遍的做法是根据网页的序号将索引分为很多份（Shards）,分别存在不同的服务器。查询会被分发到各个服务器，这些服务器并行处理请求， 并把结果送回到主服务器合并，最终将结果返回给用户。

3. 随着信息的增加，海量的数据会给搜索带来压力。需要根据网页的重要性、质量和访问频率建立常用和非常用等不同级别的索引。 常用的索引需要访问速度快，附加信息多，更新也要快；而非常用的就可以降低要求。