变未来的九大，法 古老的索引 索引的概念是所有搜索引擎背后最基础的思想。但索引并非由搜索引 擎发明：事实上，索引的思想几乎和书写本身一样古老。比如，人类学家 发现了一座具有五千年历史的巴比伦神庙图书馆，里面按学科对楔形文字 泥版进行了分类。因此，索引可以称得上是计算机科学中最古老的有用思想。 如今，“索引”这个词通常指参考书最后的一个板块。你可能想要查 看的所有概念都以固定顺序（通常是按字母排序）列出，每一个概念下 都列出了这个概念出现的位置（通常是页码）。因此，一本和动物有关 的书也许会有一个像“cheetah124,l56”的索引项。这个索引项意味着 “cheetah”(猎豹)这个词在第124页和第l56页出现过。（让你做个相当 有趣的练习，你可以在本书的索引中查询“index”这个词。你应该可以 找到这一页。) 在上 72/ 狗贴在垫子 3/ 个假想的万维网，由编号为1、2和3的三个页面组成。 3 cat 13 dog 23 mat 12 12 Sat 13 stood 23 the 123 while 3 一个用页码表示的简单索引。 互联网搜索引擎的索引和一本书的索引有着相同的工作原理。书 “页”现在成了万维网上的网页，而搜索引擎则给互联网上的每个网页分 配了一个不同的页码。（是的，互联网上虽然有很多网页一最新的数据 显示有成百上千亿个一但计算机很擅长处理大数字。)上图给出了一个 PDF电子书基地http:/dayol982.400gb.com
PDF电子书基地 http://dayo1982.400gb.com
第二章授索引琴索引一在世界上最大的草噪中寻针 会让整个过程更具体的例子。想象万维网只由上面显示的3个短网页组 成，它们分别分配到了页码1、2和3。 计算机可以为这三个网页创建一个索引：首先要为出现在任一页面上 的所有单词创建一个列表，然后按字母表顺序整理这张列表。我们可以 将结果称为单词表(word list)一在这个例子中是“a、cat、dog、mat、 on、sat、stood、.the、while”。然后计算机会一个单词一个单词地搜遍所 有页面。计算机会标注每个单词所在的页码，然后再标注单词表中下一个 单词的位置。最终结果显示在上图中。比如，你可以立即看到单词“cat” 出现在第1页和第3页，却不在第2页。而单词“while”只出现在第3页。 通过这种简单方法，搜索引擎就已经能回答许多简单的查询。比如， 假设你输入查询词“cat”,搜索引擎能很快跳转到单词表中的“cat”项。 (因为字母表是按字母排序的，计算机能很快找到任何项，就像我们可以 很快找到词典中的一个单词-一样。)一旦计算机找到“cat”项，搜索引擎 就能给出该项的页面列表一在这个例子中就是第1页和第3页。现代搜 索引擎对结果的组织很合理，只摘取了返回页面的少诈片段，不过，我们 基本上会忽略这样的细节，将精力集中在搜索引擎如何知道页面“符合” 用户输入的查询上。 再举另一个非常简单的例子，让我们来检查一下查询“og”的步 骤。在这个例子中，搜索引擎很快会找到“d0g”项，并返回页码2和3。 如果查询多个单词，如“cat dog”呢？这表示你正在寻找同时包含单词 “cat”和“dog”的页面。通过已有的索引，搜索引擎也能很容易查到结 果。搜索引擎首先会单独查找这两个单词，找出它们分别在哪些页面中。 结果是“cat”在第1页和第3页，“dog”在第2页和第3页。之后，计 算机能快速扫描这两个命中列表，寻找同时出现在两个列表中的页码。在 这个例子中，第1页和第2页被排除了，但第3页同时出现在两个列表中， 因此最终答案就是第3页上的一次单独命中。与之极其相似的一个策略也 适用于超过两个单词的查询。比如，查询“cat the sat'”会返回第1页和第 19
塞未来的九大法 3页为命中，因为它们是“cat”(1,3)、“the”(1,2,3)和“sat”(1,3) 这个列表的通用元素。 就目前来看，搭建一个搜索引擎听起来相当容易。最简单的索引技术 似乎运行得很好，即便对多词查询也是如此。不幸的是，这种简单方法完 全不能满足现代搜索引擎的需要。出现这种情况的原因有几个，不过现在 我们只会关注其中之一：如何做短语查询。短语查询是指寻找一个确切短 语的查询，而非凑巧一些单词出现在页面中的某些地方。比如，“cat sat' 查询和cat sat查询的意义截然不同O。cat sat查询寻找的是在任何位置包 含“cat”和“sat”两个单词的页面，不考虑顺序；而“cat sat'”查询寻找 的是包含单词“cat”之后紧跟单词“sat”的页面。在上面那个由三个网 页组成的简单例子中，cat sat查询结果命中第1页和第3页，但“cat sat'” 查询只返回一次命中，就在第1页。 一个搜索引擎如何才能有效地进行一次短语查询呢？继续说“cat sat'” 这个例子。第一步和平常的多词查询cat sat-一样，从单词表中获取每个单 词出现的网页列表，在这个例子中就是出现在第1页和第3页的“cat”: “sat”也一样，出现在第1页和第3页。不过搜索引擎到这里就卡住了。 搜索引擎很确切地知道两个单词同时出现在页面1和页面3上，但没有办 法来分辨这些单词是否以正确的顺序紧挨着彼此出现。你也许会想，搜索 引擎可以返回查看原网页，看这个短语是否存在。这的确是个可能的解决 方案，但效率却非常非常低。这需要遍历每一个可能包含这个短语的网页 的全部内容，而且可能有海量这样的网页。记住，我们在这里打交道的是 一个只由三个页面组成的极小的例子，真正的搜索引擎必须从数百亿个网 页中找出正确的结果。 ①注意英文单词的双引号。一译者注 PDF电子书基地http:/dayol982.400gb.com
PDF电子书基地 http://dayo1982.400gb.com
第二查搜索引繁素引一在世界上最大的草垛中寻针 词位置把戏 这一问题的解决方案是让现代搜索引擎运行良好的首个、真正精巧的 思想：索引应该不单单存储页码，还要存储页面内的位置。这些位置并不 神秘：它们只是代表了一个词在页面中的位置。第3个词的位置是3，第 29个词的位置是29，依此类推。例子中三个页面组成的数据集如下页图 所示，还加上了词位置。图下面的是索引一由存储页码和词位置中得出 的结果组成。我们称这种创建索引的方法为“词位置把戏”(word location tick)。举几个例子，以确保大家理解了词位置把戏。索引的第一行是 “3-5.”。这意味着词“a”只在数据集中出现过一次，是第3页的第5个 单词。索引中最长的一行是“the1-11-52-12-53-1”。这一行可以让你知 道，这个数据集中所有出现单词“the”的具体位置。它在第1页出现过 两次（位置1和5），第2页出现过两次（位置1和5），第3页出现过1 次（位置1）。 你还记得介绍页内词位置的目的吗？是为了解决如何有效地进行短语 查询这个问题。让我们来看看如何用这个新索引做一次短语查询。还是和 前面一样，查询短语“cat sat'”。第一步和使用旧索引时一样：从索引中 提取单个词的位置，“cat”的位置是1-2、3-2，“sat”的位置是1-3、3-7。 到这里还好：我们知道短语查询“cat sat'”唯一可能的命中就是在第1页 和第3页。但与之前一样，我们还不确定相同的短语是否出现在了这些页 面中一有可能这两个单词的确出现了，但并不是以正确的顺序彼此相 邻。幸运的是，从位置信息中确认这一点很容易。首先从第1页开始。根 据索引信息，我们知道“cat”出现在第1页的位置2（这就是1-2的含义）。 我们还知道“sat”出现在第1页的位置3（这是1-3的含义）。但如果“cat” 在位置2，“sat”在位置3，我们就知道“sat”紧挨着出现在“cat”之后 (因为2之后立即就是3)一因此我们寻找的整个短语“cat sat'”必定出 现在第1页，并从位置2开始。 21
李未来的九大算法 2 3 the cat stopd 456 3-5 cat 1-23-2 2-23-6 1-62-6 1-4 2-4 1-3 2126 顶图：3个网页加上了页内词位置。 底图：同时色含页码和页内词位置的新索引。 我知道自己在这点上谈得很多，但巨细无遗、从头至尾地研究这个 例子，是为了让读者真正地理解为了获得答案究竞使用了哪些信息。注 意，我们已经为短语“cat sat'”找到了一次命中，仅仅是通过查看索引信 息(“cat”的位置1-2、3-2，“sat”的位置1-3、3-7)，而非原始网页。这 很关键，因为我们只需查看索引中的两个项，而非遍历所有可能包含命中 的页面一而在进行真正短语查询的真正的搜索引擎中，可能有数百万个 这样的页面。总之：通过在索引中加入页内词位置，我们只需通过查看索 引中的几行，就能找到一次短语查询命中，而非遍历海量页面。这个简单 的词位置把戏是让搜索引擎奏效的关键之一。 事实上，我还没讲完“cat sat”这个例子。我们完成了对第1页信息 的处理，但第3页还没处理。对第3页的推理和第1页的处理方式很相 似：“cat”出现在第3页的位置2，“sat”出现在位置7，因此它们不可能 相邻一因为紧跟2之后出现的不是7。这样我们就知道，第3页并不是 短语查询“cat sat”的命中，尽管它是多词查询cat sat的命中 顺便说一下，词位置把戏不仅仅对短语查询重要。举个例子，思考 22 PDF电子书基地http:/dayol982.400gb.com
PDF电子书基地 http://dayo1982.400gb.com