|
原文链接:
David Austin 关键词： 谷歌，搜索，随机矩阵，特征值 想象一个含有250亿份文件，却没有集中管理机构和馆员的图书馆，而且任何人都可以在任何时间添加新的文件而不需要通知其他人。一方面你可以确定，这庞大的文件堆中有一份文件含有对你至关重要的信息，而另一方面，你又像我们中的大多数人那样没有耐心，想要在几秒钟之内就找到这条信息。你有什么办法呢？ 摆在你面前的这个难题看起来似乎无法解决。而这个文件堆跟万维网（World Wide Web）其实相差无几，后者就是一个超大的、高度混乱的以各种形式存放的文件堆。当然，从万维网中找信息我们有办法解决，因为我们对搜索引擎非常熟悉（或许你就是通过搜索找到这篇文章的）。本文将介绍谷歌的网页排序算法（PageRank Algorithm），以及它如何从250亿份网页中捞到与你的搜索条件匹配的结果。它的匹配效果如此之好，以至于“谷歌”（google）今天已经成为一个被广泛使用的动词了。 包括谷歌在内，多数搜索引擎都是不断地运行计算机程序群，来检索网络上的网页、搜索每份文件中的词语并且将相关信息以高效的形式进行存储。每当用户检索一个短语，例如“搜索引擎”，搜索引擎就将找出所有含有被检索短语的网页。（或许，类似“搜索”与“引擎”之间的距离这样的额外信息都被会考虑在内。）但问题是，谷歌现在需要检索250亿个页面，而这些页面上大约95%的文本仅由大约一万个单词组成。也就是说，对于大多数搜索而言，将会有超级多的网页含有搜索短语中的单词。我们所需要的其实是这样一种办法，它能够将这些符合搜索条件的网页按照重要程度进行排序，这样才能够将最重要的页面排在最上面。 确定网页重要性的一个方法是使用人为排序。例如，你或许见过这样一些网页，他们包含了大量的链接，后者连接到某个特定兴趣领域的其他资源。假定维护这个网页的人是可靠的，那么他推荐的网页在很大程度上就可能有用。当然，这种做法也有其局限性，比如这个列表可能很快就过期了，也可能维护这个列表的人会无意或因某种未知的偏见而遗漏掉一些重要的网页。 谷歌的网页排序算法则不借助人为的内容评估来确定网页的重要性。事实上，谷歌发现，它的服务的价值很大程度上是它能够提供给用户无偏见的搜索结果。谷歌声称，“我们软件的核心就是网页排序（PageRank）。” 正如我们将要看到的，技巧就是让网页自身按照重要性进行排序。 如何辨别谁重要 如果你曾建立过一个网页，你应该会列入一些你感兴趣的链接，它们很容易使你点击到其它含有重要、可靠信息的网页。这样就相当于你肯定了你所链接页面的重要性。谷歌的网页排序算法每月在所有网页中进行一次受欢迎程度的评估，以确定哪些网页最重要。网页排序算法的提出者，谢尔盖?布林(Sergey Brin)和拉里?佩奇(Lawrence Page)的基本想法是：一个网页的重要性是由链接到它的其他网页的数量及其重要性来决定。 我们对任意一个网页P
取值接近于0.85，布林和佩奇指出，需要50到100次迭代来获得对向量I的一个足够好的近似。计算到这个最优值需要几天才能完成。 当然，网络是不断变化的。首先，网页的内容，尤其是新闻内容，变动频繁。其次，网络的隐含超链结构在网页或链接被加入或被删除时也要相应变动。有传闻说，谷歌大约1个月就要重新计算一次网页排序向量I。由于在此期间可以看到网页排序值会有一个明显的波动，一些人便将其称为谷歌舞会（Google Dance）。（在2002年，谷歌举办了一次谷歌舞会！） 总结 布林和佩奇在1998年创建了谷歌，正值网络的增长步伐已经超过当时搜索引擎的能力范围。在那个时代，大多数的搜索引擎都是由那些没兴趣发布其产品运作细节的企业研发的。在发展谷歌的过程中，布林和佩奇希望“推动学术领域更多的发展和认识。”换言之，他们首先希望，将搜索引擎引入一个更开放的、更学术化的环境，来改进搜索引擎的设计。其次，他们感到其搜索引擎产生的统计数据能够为学术研究提供很多的有趣信息。看来，联邦政府最近试图获得谷歌的一些统计数据，也是同样的想法。 还有一些其他使用网络的超链结构来进行网页排序的算法。值得一提的例子是HITS算法，由乔恩·克莱因伯格（Jon Kleinberg）提出，它是Teoma搜索引擎的基础。事实上，一个有意思的事情是比较一下不同搜索引擎获得的搜索结果，这也可以帮助我们理解为什么有人会抱怨谷歌寡头（Googleopoly）。 参考文献 Michael Berry, Murray Browne, Understanding Search Engines: Mathematical Modeling and Text Retrieval. Second Edition, Sergey Brin, Lawrence Page, The antaomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, 33: 107-17, 1998. Also available online at http://infolab./pub/papers/google.pdf Kurt Bryan, Tanya Leise, The $25,000,000,000 eigenvector. The linear algebra behind Google. Google Corporate Information: Technology. Taher Haveliwala, Sepandar Kamvar, The second eigenvalue of the Google matrix. Amy Langville, Carl Meyer, Google's PageRank and Beyond: The Science of Search Engine Rankings. This is an informative, accessible book, written in an engaging style. Besides providing the relevant mathematical background and details of PageRank and its implementation (as well as Kleinberg's HITS algorithm), this book contains many interesting "Asides" that give trivia illuminating the context of search engine design.
|
|
|
