三、内容索引
搜索引擎为什么这么快？
好的搜索引擎的评价标准之一就是要快，那么搜索引擎是如何实现的呢？
在开始讲解之前，我们可以考虑另外一个相似的问题：如何在图书馆找到一本书？
最笨的方法是一个书架、一个书架地找，这会花费大量的时间。
聪明一些的方式是通过索书号，快速找到所在书架，进而找到这本书。
搜索引擎中的索引就相当于图书馆里每本书的索书号，通过索引，可以快速找到需要的信息。
索引到底长啥样？
以网页搜索引擎为例：下面这张图是一个简单的索引系统（更准确的说法是倒排索引，至于为什么是倒排，这里先卖个小关子，后面会讲到）。
左边是关键词，右边是这个关键词出现在哪个网页中，一个关键词可能同时出现在很多网页中，所以是一对多的关系。
与图书馆索引不同是：一个图书馆再大，藏书毕竟还有有限的，图书管理员可以手工给每个图书建立索书号。但搜索引擎存储的数据都是以亿计算的，不可能手工建立索引，只能借助一些技术手段。
从上面的表格我们可以看出，构建索引主要有两个过程：查找关键词，把关键词和网页对应起来。
关键词
构建索引的前提是提取出关键词，那么给定一个文本（也就是网页的文字内容），如何获取里面的关键词呢？
主要有两步：首先是获得文本里出现的所有词语，也叫做分词，之后再从中筛选一些作为关键词。
第一步，分词。
如果是一句英文，“Marry had a little lamb”，每个词都是用空格分开的，里面有“marry”、“had”、“a”’、“little”、“lamb”这五个单词，但中文“玛丽有一只小绵羊”，因为没有分隔符（比如：空格）把每个词语分开，就有些麻烦了。
最容易想到的分词方法就是查字典，把句子从左到右看一遍（程序员的说法叫做遍历），每个词语如果在字典中出现过就标记出来。
拿“玛丽有一只小绵羊”举例，比如：“玛丽”这个词在字典中出现过，就把“玛丽”作为一个词语，“有”在词典中出现过，就把“有”作为一个词语，就这样一直做下去，最后可以分为“玛丽、有、一只、小绵羊”。
这种最简单的方式可以解决一部分问题，但也有很大的问题，比如是“小”“绵羊”还是作为整体的“小绵羊”呢？
程序员使用统计学解决这个问题：
从形式上看，词是字的组合，两个字组合在一起可能是一个词语，也可能不是，如果是词语的可能性（概率）大一些，我们就倾向于认为它们可以组成词语。
这就像：天气预报说明天下雨的概率70%，不下雨的概率30%，我们就倾向于认为明天下雨。“小绵羊”一起出现的概率是70%，分开出现的概率是30%，我们就倾向于认为“小绵羊”是一个词语。
那么，如何计算相邻的字组成词语的概率呢？
我们可以对语料库中相邻出现的各个字的组合的次数进行统计，计算所有的字相邻出现的频率，当语料库足够大时，出现的频率越高，对应的概率也就越高。
我们可以计算一个句子中所有组合出现的概率，产生最大的概率组合，就是分词的结果。
比如：“玛丽、有、一只、小绵羊”每一个词语出现的概率就大于“玛丽、有一、只、小、绵羊”等其他组合出现的概率，那么，我们就认为这个句子就按照“玛丽、有、一只、小绵羊”划分。
第二步，获得关键词。
对所有的文本分词之后会发现，“的”、“了”、“吗”、“也许”等没有很强实际意义的功能词有很多，相比之下“产品经理”、“搜索引擎”等词语更加具有实际意义的反而较少，后者更应该作为关键词。
于是，我们使用把所有这些功能词存起来，作为停用词（stop word），如果一个词语出现在停用词中，就不能作为关键词。于是，我们就从分词结果中，获得了关键词。
下面是一个简单的停用词表，可能看出，基本都是我们经常使用的、没有很强实际意义的词语。
中文分词是几乎所有中文自然语言处理（Natural Language Processing）的基础，所以学术界和产业界对中文分词的技术研究已经很深入了，有高质量的商用分词库，也有像jieba这样的开源中文分词库，可以免费使用。
通过提取每个网页的关键词，最终每个网页和关键词的对应关系如下：
需要注意的是：获取关键词不仅用在网页处理，而且也用在输入搜索框中。当我们搜索一句中文的时候，搜索引擎内部会进行分词、去掉停用词，获得关键词，之后再进行后续处理。
倒排索引
现在，我们已经建立好了索引，对于每一个网页，我们找到了出现的所有关键词。
当用户查询时，我们从头到尾，对每一篇文件扫描一遍，看哪个网页出现了用户查询的关键词，就把这个文件作为搜索结果。
但问题是：动辄上亿的网页数量，从头到尾扫描一次就要花好长时间，根本无法满足正常的需求，更别说快速响应了。
那我们能不能把关键词放前面，网页放后面？
这样，当我们检索的关键词的时候，不需要遍历整个系统，只用查找对应的几个关键词，就可以找到需要的网页了！
对计算机而言，直接寻找关键词所在位置的信息，所需的时间非常短，完全可以满足搜索的需要。
比如：用户搜索“关键词1”，那么搜索引擎只需要找到“关键词1”，就可以会直接找到“网页1，网页2，网页5，……网页L”。
用户搜索“关键词1+关键词2”，那么搜索引擎需要找到“网页1，网页2，网页5，……网页L”，“网页3，网页4，网页5，……网页M”，找到同时出现的“网页3、网页5，……”。这样就大大加快了呈现排名的速度。
把“文件-关键词”这种结构颠倒一下，“关键词-文件”，就是倒排索引名字的由来。
更进一步，倒排索引中不仅仅记录了包含网页的ID，还会记录关键词出现的频率（term frequency）、每个关键词对应的文档频率（inverse document frequency），以及关键词出现在文件中的位置等信息，这些信息可以直接用在搜索结果排序上。
