第二章搜索引擎索引—在世界上最大的草垛中寻针 一下寻找相邻单词的问题。在一些搜索引擎中，用户可以在查询中使用 “NEAR”关键词做到这一点。事实上，Alta Vista搜索引擎在早期就提供 了这一功能，在本书写作时仍然提供。作为一个特殊的例子，假设在一些 特别的搜索引擎中，查询cat NEAR dog会找到“dog”前后五个位置之内 出现“cat”的页面。我们如何才能在数据集中有效地执行这种查询？使 用词位置，会使查询变得很容易。“cat”的索引项是l-2、3-2,而“dog” 的索引项是2-2、3-6。可以立刻看出，第3页是唯一可能的命中。而在第 3页，“cat”出现在位置2，“dog”出现在位置6。因此这两个词之间的距 离是6-2，结果是4。因此，“cat”的确出现在“dog”前后五个位置之 内，而第3页则是查询cat NEAR dog的命中。和前面一样，请注意这次 查询的执行是多么高效：无须遍历任何网页的实际内容一相反，只参考 了索引中的两个项。 不过，在实际中，NEAR查询对搜索引擎用户并不非常重要。几乎没 人使用NEAR查询，绝大多数主要搜索引擎甚至不支持它们。尽管如此， 能执行NEAR查询的能力实际上对现实中的搜索引擎至关重要。这是因为 搜索引擎不断地在后台执行NEAR查询。要理解其中的原因，我们首先不 得不研究现代搜索引擎面临的主要问题之一：排名的问题。 排名和邻度 到目前为止，我们一直专注于匹配阶段：为一个给出的查询高效地找 出所有命中的问题。不过正如之前强调的，第二个阶段“排名”对于一个 高质量的搜索引擎是绝对必不可少的：这是挑选出前几个命中并展示给用 户的阶段。 让我们更细致地来检验排名的概念。一个网页的“排名”究竟取决于 什么？真正的问题不是“这个网页和查询匹配吗”，而是“这个网页和查 23
改意泰来的九大第法 询相关吗”。计算机科学家们使用“相关度”(relevance)这个术语来形容 一个结果网页和某个特定查询有多么相配或多么有用。 举个具体的例子，假设你对导致疟疾的原因感兴趣，并在一个搜索引 擎中输人查询malaria cause(导致疟疾)。简化考虑，假设搜索引擎对这 一查询只有两个命中一下图显示的两个网页。现在来看看这两个网页。 作为人类，你很快就知道第1页和疟疾起因有关，而第2页似乎是对刚 刚发生的一些军事行动的描述，只不过恰巧使用了“cause'”和“malaria” 这两个词。因此，和第2页相比，第1页无疑和查询malaria cause更具相 关性。可计算机不是人，让计算机理解这两页的主题也很难，似乎不可能 让搜索引擎正确地对这两个命中进行排名。 2 also 1-19 cause 1-62-2 malaria 1-8 2-19 whom 2-15 顶图：两个提及疟疾的样本网页。 底图：从上方两个网页中创建的索引的一部分。 不过，事实上，有一种很简单的方法让这个例子中的排名正确。查询 词彼此相邻的网页比那些查询词相距很远的网页相关度更高。在疟疾这个 例子中，“malaria”和“cause”在第1页中仅相距1个词，而在第2页中 则相距17个词。（记住，搜索引擎只通过查看索引项就能高效地发现这 PDF电子书基地http:/dayol982.400gb.com
PDF电子书基地 http://dayo1982.400gb.com
第二章搜索引擎索引—在世界上最大的草垛中寻针 点，无须返回查看网页。)因此，尽管计算机并不真正地“理解”查询的 主题，它也能猜测网页1比网页2更具相关性，因为网页1查询词之间的 距离要比网页2更近。 总而言之，尽管人们不经常使用NEAR查询，搜索引擎也在不断地使 用和邻度有关的信息，提高搜索排名。而它们能高效地做到这点的原因则 是，它们使用词位置把戏。 1 Bmy cat 29 he mat while a dag sat 一个网页范例集，每个网页都有一个标题和一段正文。 我们已经了解到，早在距今5000年以前，巴比伦人就开始使用索引。 而词定位把戏也不是由搜索引擎发明的：这是互联网出现以前，另一种信 息检索中用到的著名技术。不过，在下一部分，我们将了解一个看起来的 确是由搜索引擎设计者发明的新把戏：元词把戏(metaword trick)。对这 一把戏和众多相关思想的精巧运用，使AltaVista搜索引擎在20世纪90年 代晚期迅速成为搜索行业的领头羊。 元词把戏 到目前为止，我们一直都在使用极其简单的网页示例。然而，绝大多 数网页拥有众多结构，包括标题、标头、链接和图片，可我们还一直认为 网页只是普通的词表。接下来，我们将探索搜索引擎如何处理网页中的结 构。不过，为了尽可能保持简单，我们只会引人一层结构：网页的顶部会 有一个标题，之后是页面的正文。上图显示了我们熟悉的三页示例，并附 加了一些标题。 实际上，要像搜索引擎一样分析网页结构，我们需要了解更多编写 25
改惠未来的九大算法 网页的知识。网页是由一种特殊语言编写的，以便网络浏览器能用很好 的格式展示它们。（编写网页最常用的语言被称为HTML,不过HTML的 细节对本次讨论不重要。)标头、标题、链接、图片等格式化结构是用 被称为元词的特殊单词编写的。比如，网页标题开始使用的元词也许是 <titleStart>,而结束这个标题的元词可能是<titleEnd>。类似的，网页正 文可能是以<bodyStart心开始，以<bodyEnd>结束。不要纠结于“<”、“>” 这些符号。它们出现在绝大多数计算机键盘上，人们通常只知道这些符号 的数学意义是“大于”和“小于”。不过在这里，这些符号和数学没有任 何关系，只是方便的象征，将这些元词和网页中的正常单词区分开来。 3 stitlestarts my pets mat sbodyend> 和上图一样的网页集，但展示的是用元河编写的情况，而非在网络渊览器中显示的样子。 看一下上面的图。这张图展示的内容和前一张图一样，但显示的是实 际编写网页的样子，而非在网络浏览器中显示的样子。绝大多数网络浏览 器都能让用户检验网页的原始内容，这需要选择名为“查看网页源代码 的菜单选项一我建议你下次有机会试验一下。（注意，在这里使用的元 词，如<titleStart>和<titleEnd心是帮助你理解的虚构的、易于辨认的示例。 在真实的HTML中，元词被称作标签(tag)。HTML中开启和结束标题的 标签是<title>和</title>一你可以在使用“查看网页源代码”的菜单选 项后搜索这些标签。) 在创建一份索引时，囊括所有元词是件很简单的事。无须新把戏：你 只要像存储正常单词一样存储元词位置就行。下页的图显示了从带有元词 的三个网页中创建的索引。看一下这张图，确保自己理解了其中所有的奥 秘。比如，“mat”的项是1-l1、2-1l,表示“mat”是第1页的第1l个词， PDF电子书基地http:/dayol982.400gb.com
PDF电子书基地 http://dayo1982.400gb.com
第二章搜索引繁索引一在世界上最大的草垛中寻针 也是第2页的第11个词。元词位置的解读也一样，“<titleEnd>”的项是14 2-4和3-4，也就是说“<titleEnd”是第1页、第2页和第3页的第4个词。 我们称这种和索引普通单词一样索引元词的简单把戏为“元词把戏”。 这个把戏也许看起来简单得可笑，但元词把戏在让搜索引擎执行精确搜 素和高质量排名上扮演了至关重要的角色。举个简单例子证明。假设在 某个时候，有个搜索引擎支持使用IN关键词的特殊查询，因此像boat IN TITLE这样的查询只会返回在网页标题中包含了单词“boat”的网页，而 查询giraffe IN BODY则会找到在正文中包含“giraffe'”(长颈鹿)的网页。 请注意，绝大多数搜索引擎并不完全按照这种方法提供N查询，但一些 搜索引擎可以通过让你点击“高级搜索”选项，详细说明查询词必须出现 3-10 cat 1-31-73-7 d09 2-32-73-11 mat 1-112-11 my 1-22-23-2 1-92-9 pets 3-3 sat 1-83-12 stood 2-83-8 the 1-61-102-62-103-6 while 3-9 <bodvEnd> 1-122.123-13 <bodyStart>1-5 2-5 3-5 stitleEnd> <titleStart> 上一张图中的网页（包括元词）的索引 dog:2-32-73-11 <titleStart>:1-1(2-13-1 <titleEnd>:1-42-43-4 搜索引李如何执行接索dog IN TITLE