正文

搜索引擎索引——在世界上最大的草垛中寻针(5)

改变未来的九大算法 作者:(美)约翰·麦考密克


我知道自己在这点上谈得很多,但巨细无遗、从头至尾地研究这个例子,是为了让读者真正地理解为了获得答案究竟使用了哪些信息。注意,我们已经为短语“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的命中。

顺便说一下,词位置把戏不仅仅对短语查询重要。举个例子,思考一下寻找相邻单词的问题。在一些搜索引擎中,用户可以在查询中使用“NEAR”关键词做到这一点。事实上,AltaVista搜索引擎在早期就提供了这一功能,在本书写作时仍然提供。作为一个特殊的例子,假设在一些特别的搜索引擎中,查询cat NEAR dog 会找到“dog”前后五个位置之内出现“cat”的页面。我们如何才能在数据集中有效地执行这种查询?使用词位置,会使查询变得很容易。“cat”的索引项是1-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查询。要理解其中的原因,我们首先不得不研究现代搜索引擎面临的主要问题之一:排名的问题。


上一章目录下一章

Copyright © 读书网 www.dushu.com 2005-2020, All Rights Reserved.
鄂ICP备15019699号 鄂公网安备 42010302001612号