8.5.3 倒排索引

我不知道大家有没有对搜索引擎好奇过，无论你查找什么样的信息，它都可以在极短的时间内给你一些结果。是什么算法技术达到这样的高效查找呢？

我们在这里介绍最简单的，也算是最基础的搜索技术——倒排索引。

我们来看样例，现在有两篇极短的英文“文章”——其实只能算是句子，我们暂认为它是文章，编号分别是1和2。
1.Books and friends should be few but good.（读书如交友，应求少而精。）
2.A good book is a good friend.（好书如挚友。）

假设我们忽略掉如“books”、“friends”中的复数“s”以及如“A”这样的大小写差异。我们可以整理出这样一张单词表，如表8-5-1所示，并将单词做了排序，也就是表格显示了每个不同的单词分别出现在哪篇文章中，比如“good”它在两篇文章中都有出现，而“is”只是在文章2中才有。

有了这样一张单词表，我们要搜索文章，就非常方便了。如果你在搜索框中填写
“book”关键字。系统就先在这张单词表中有序查找“book”，找到后将它对应的文章编号1和2的文章地址（通常在搜索引擎中就是网页的标题和链接）返回，并告诉你，查找到两条记录，用时0.0001秒。由于单词表是有序的，查找效率很高，返回的又只是文章的编号，所以整体速度都非常快。

如果没有这张单词表，为了能证实所有的文章中有还是没有关键字“book”，则需要对每一篇文章每一个单词顺序查找。在文章数是海量的情况下，这样的做法只存在理论上可行性，现实中是没有人愿意使用的。

在这里这张单词表就是索引表，索引项的通用结构是：

• 次关键码，例如上面的“英文单词”；
• 记录号表，例如上面的“文章编号”。

其中记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）。这样的索引方法就是倒排索引（inverted index）。倒排索引源于实际应用中需要根据属性（或字段 、次关键码）的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引。

倒排索引的优点显然就是查找记录非常快，基本等于生成索引表后，查找时都不用去读取记录，就可以得到结果。但它的缺点是这个记录号不定长，比如上例有7个单词的文章编号只有一个，而“book”、“friend”、“good”有两个文章编号，若是对多篇文章所有单词建立倒排索引，那每个单词都将对应相当多的文章编号，维护比较困难，插入和删除操作都需要作相应的处理。

当然，现实中的搜索技术非常复杂，比如我们不仅要知道某篇文章有要搜索的关键字，还想知道这个关键字在文章中的哪些地方出现，这就需要我们对记录号表做一些改良。再比如，文章编号上亿，如果都用长数字也没必要，可以进行压缩，比如三篇文章的编号是“112,115,119”，我们可以记录成“112,+3,+4”，即只记录差值，这样每个关键字就只占用一两个字节。甚至关键字也可以压缩，比如前一条记录的关键字是“and”而后一条是“android”，那么后面这个可以改成“<3,roid>”，这样也可以起到压缩数据的作用。再比如搜索时，尽管告诉你有几千几万条查找到的记录，但其实真正显示给你看的，就只是当中的前10或者20条左右数据，只有在点击下一页时才会获得后面的部分索引记录，这也可以大大提高了整体搜索的效率。

呵呵，有同学说得没错，如果文章是中文就更加复杂。比如文章中出现“中国人”，它本身是关键字，那么“中国”、“国人”也都可能是要查找的关键字——啊，太复杂了，你还是自己去找相关资料吧。如果想彻底明白，努力进入google或者百度公司做搜索引擎的软件工程师，我想他们会满足你对技术知识的渴求。

我们课堂上就是起到抛砖引玉的作用，希望可以让你对搜索技术产生兴趣。