搜索
本文是谷歌创始人Sergey和Larry在斯坦福大学计算机系读博士时的一篇论文。发表于1997年。在网络中并没有完整的中文译本，现将原文和本人翻译的寥寥几句和网络收集的片段（网友xfygx和雷声大雨点大的无私贡献）整理和综合到一起，翻译时借助了translate.google.com，因为是技术性的论文，文中有大量的合成的术语和较长的句子，有些进行了意译而非直译。作为Google辉煌的起始，这篇文章非常有纪念价值，但是文中提到的内容因年代久远，已经和时下最新的技术有了不少差异。但是文中的思想还是有很多借鉴价值。因本人水平有限，对文中内容可能会有理解不当之处，请您查阅英文原版。大规模的超文本网页搜索引擎的分析SergeyBrinandLawrencePage{sergey,page}@cs.stanford.eduComputerScienceDepartment,StanfordUniversity,Stanford,CA94305摘要在本文中我们讨论Google，一个充分利用超文本文件结构进行搜索的大规模搜索引擎的原型。Google可以有效地对网络资源进行爬行搜索和索引，比目前已经存在的系统有更令人满意的搜索结果。该原型的数据库包括2400万页面的全文和之间的链接，可通过访问。设计一个搜索引擎是一种具挑战性的任务。搜索引擎索索引数以亿计的不同类型的网页并每天给出过千万的查询的答案。尽管大型搜索引擎对于网站非常重要，但是已完成的、对于大型搜索引擎的学术上的研究却很少。此外，由于技术上的突飞猛进和网页的急剧增加，在当前，创建一个搜索引擎和三年前已不可同日而语。本文提供了一种深入的描述，与Web增殖快速进展今日创建Web搜索引擎是三年前很大不同。本文提供了到目前为止，对于我们大型的网页所搜引擎的深入的描述，这是第一个这样详细的公共描述。除了如何把传统的搜索技术扩展到前所未有的海量数据，还有新的技术挑战涉及到了使用超文本中存在的其他附加信息产生更好的搜索结果。本文解决这样一个问题，如何建立一个可以利用超文本中存在的其他附加信息的实用的大型系统，同时我们也研究一下如何有效处理任何人都能发布他们想发布的包含任何信息的大量自由链接的问题。关键字：互联网，搜索引擎，文献检索，PageRank，Google1.简介(注：本文由两个版本--较长的完整版本和一个较短的印刷的版本。完整版本提供在网络上和会议的CD-ROM上)。Web给信息检索带来了新的挑战。Web上的信息量快速增长，同时不断有毫无经验的新用户来体验Web这门艺术。人们喜欢用超级链接来网上冲浪，通常都以象Yahoo这样重要的网页或搜索引擎开始。人工维护的网站列表能有效的覆盖受欢迎的流行的站点，但是它具有主观性，建立和维护的代价高，升级慢，不能包括所有深奥的主题。基于关键词的自动搜索引擎通常返回太多的低质量的匹配。使问题更遭的是，一些广告为了赢得人们的关注想方设法误导自动搜索引擎。我们建立了一个大型搜索引擎解决了现有系统中的很多问题。应用超文本结构，提供高质量的查询结果，我们的系统命名为google，取名自googol的通俗拼法，即10的100次方，这和我们的目标建立一个大型搜索引擎较好的符合。1.1网络搜索引擎—升级换代：1994-2000搜索引擎技术不得不快速升级跟上成倍增长的网站数量。1994年，第一个Web搜索引擎，WorldWideWebWorm（）拥有110，000个网页和网站可访问文档的索引。到1994年11月，顶级的搜索引擎声称可以检索到2万（WebCrawler）100万个网络文件（来自搜索引擎监视）。可以预见到2000年，可检索到的网页将超过10亿。同时，搜索引擎的访问量也会以惊人的速度增长。在1997年的三四月份，WorldWideWebWorm平均每天收到1500个查询。在1997年11月，Altavista声称它每天要处理大约20’百万个查询。随着网络用户的增长，可以预见到到2000年，自动搜索引擎每天将处理上亿个查询。我们系统的设计目标要解决许多问题，包括质量和可升级性，引入升级搜索引擎技术，把它升级到如此大量的数据上。1.2Google：升级与网络建立一个能够和当今web规模相适应的搜索引擎会面临许多挑战。抓网页技术必须足够快并且保持是最新的版本。存储空间必须高效的存储索引和文档。索引系统必须能够高效地处理上百亿GB的数据。处理查询必须快，达到每秒能处理成百上千个查询。随着Web的不断增长，这些任务变得越来越艰巨。然而硬件的性能和成本也在快速增长，可以部分抵消这些困难。然而，还有几个值得例外，如磁盘的寻道时间，操作系统的效率。在设计Google的过程中，我们既考虑了网络的增长速度，又考虑了技术的更新。Google的设计能够很好的升级处理超大量数据集。它能够高效地使用存储空间来存储索引。优化的数据结构能够快速有效地存取（请参见4.2节）。进一步，我们希望，相对于所抓取的文本文件和HTML网页的数量而言，存储和建立索引的代价尽可能的小（请参阅附录B）。对于象Google这样的集中式系统，采取这些措施得到了良好的系统可升级性。1.3设计目标1.3.1改进搜索质量。我们的主要目标是提高Web搜索引擎的质量。1994年，有人认为建立全搜索索引就有可能很容易找到任何东西。根据BestoftheWeb1994--Navigators，“最佳导航服务应更容易找到几乎任何在网络上（已经输入的所有数据）。”。然而1997年的Web就迥然不同。任何最近使用搜索引擎的用户很容易证实索索引的完整性并不是唯一影响搜索引擎结果的因素。用户感兴趣的搜索结果往往被“垃圾结果”淹没。实际上，到1997年11月为止，四大商业搜索引擎中只有一个能够找到它自己（使用自己的搜索自己的名字时返回的前十个结果中有它自己）。导致这一问题的主要原因是文档的索引数目增加了好几个数量级，但是用户能够看的文档数却没有增加。人们仍然只希望看前面的几十个搜索结果。因此，当集合增大时，我们就需要高精确度的工具（在返回的前几十个结果中，相关文档的数量）。由于是从成千上万个有点相关的文档中选出几十个，实际上，我们希望相关的概念就是指最好的文档。高精确非常重要，甚至以响应（系统能够返回的有关文档的总数）为代价。令人十分乐观的的是利用超文本链接提供的信息有助于改进搜索和其它应用[Marchiori97][Spertus97][Weiss96][Kleinberg98]。尤其是链接结构和链接文本，为相关性的判断和高质量筛选提供了大量的信息。Google既利用了链接结构又用到了链接文本（请参见2.1和2.2节）。1.3.2搜索引擎的学术研究除了发展迅速，Web越来越商业化。到1993年，只有1.5%的网络服务是来自.com域名。到1997年，增长超过了60%。同时，搜索引擎从学术领域走进商业。到现在大多数搜索引擎被公司所有，很少发布技术细节。这就导致搜索引擎技术很大程度上仍然是暗箱操作，并倾向做广告（请参阅附录A）。对于Google来讲我们有一个的主要目标是推动学术领域在此方面的发展和了解。另一个设计目标是给适合数目的人们一个实用的系统。对我们来说应用十分重要，因为一些研究表明，现代网络系统中存在大量的有用数据。例如，每天有数千万个查询被执行。然而，获得这些数据却非常困难，主要因为它们被认为有商业价值。我们的最终设计目标是构建一个体系结构，可以支持大型Web数据上的一种新的研究活动。为了支持新研究，Google以压缩的形式保存了实际所抓到所有的文档。我们设计Google的主要目标之一就是要建立一个环境使其他研究者能够很快进入这个领域，处理海量网络数据，得到满意的结果，而通过其它方法却很难得到。系统在短时间内被建立起来，已经有几篇论文用到了Google建立的数据库，更多的在起步中。我们的另一个目标是建立一个宇宙空间实验室似的环境，在这里研究人员甚至学生都可以对我们的海量网络数据设计或做有趣的实验。2.系统功能Google搜索引擎有两个重要功能，帮助它产生高精度的搜索结果。首先，应用Web的链接结构计算每个网页的质量等级值，这个等级称为PageRank，将在98页详细描述它。第二点，Google利用超链接改进搜索结果。2.1PageRank：带来网页排序网络的引用（链接）图形是重要的资源，却没有被现有的大多搜索引擎使用。我们建立了一个包含518百万个超链接的图，它是一个具有重要意义的样本。这些图能够快速地计算网页的PageRank值，它是一个客观的标准，较好的符合人们主观的对一个网页重要程度的评价，由此对应的是，PageRank值是一个较好的区分通过网络搜索关键字获得的结果的方法。建立的基础是通过引用判断重要性。对于大多数的主题，一个简单的被限制为网页标题的文本匹配搜索当使用PageRank区分时得到了极好的结果（从google.stanford.edu可以得到演示）。对于Google主系统中的全文搜索，PageRank也有很大的帮助。2.1.1PageRank计算的描述：文献引用理论应用到Web中，主要由引用或反向链接到给定页来计数。这会反映了该网页的重要性和质量的近似值。PageRank扩展了这种思想，不平等的计算所有页面上的链接并且通过一个页面上的所有链接。PageRank定义如下:我们假设页面T1…Tn指向网页A（例如，被引用）。参数d是一个设定在0，1之间的制动因子。我们通常设置d为0.85。在下一节有更多关于d的详情，C（A）定义为网页A指向其它网页的链接数，网页A的PageRank值由下式给出：PR(A)=(1-d)+d(PR(T1)/C(T1)+...+PR(Tn)/C(Tn))请注意PageRank涵盖所有网页的一个概率分布得来，因此所有网页PageRank和是1。PageRank或PR(A)可使用一个简单的迭代算法来计算，相应对应月网页链接矩阵的主特征向量。中等规模的网站计算26万网页的PageRank值要花费几小时。还有一些技术细节超出了本文论述的范围。2.1.2直觉的解释PageRank被看作用户行为的模型。我们假想一个“随机上网者”；随机地给他一个网页；他漫无目的地命中网页的链接，而从来不点“返回键”；最终他觉得烦了，又从另一个随机的网页从新开始。随机访问一个网页的可能性就是它的PageRank值。制动因子d是随机访问一个网页烦了的可能性，随机另选一个网页。对单个网页或一组网页，一个重要的变量加入到制动因子d中。这允许个人可以故意地误导系统，以得到较高的PageRank值几乎变成不可能的。我们还有其它的PageRank算法，见98页。另外的直觉判断是一个网页有很多网页指向它，或者一些PageRank值高的网页指向它，则这个网页很重要。直觉地，在Web中，一个网页被很多网页引用，那么这个网页值得一看。一个网页被象Yahoo这样重要的主页引用即使一次，也值得一看。如果一个网页的质量不高，或者是死链接，象Yahoo这样的主页不会链向它。PageRank处理了这两方面因素，并通过网络链接递归地传递。2.2链接描述文字我们的搜索引擎对链接文本进行了特殊的处理。大多数搜索引擎把链接文字和它所链向的网页联系起来。另外，把它和链接所指向的网页联系起来。这有几点好处。第一，通常链接描述文字比网页本身更精确地描述该网页。第二，链接描述文字可能链向的文档不能被文本搜索引擎检索到，例如图像，程序和数据库。有可能使返回的网页不能被抓到。注意那抓不到的网页将会带来一些问题。在返回给用户前检测不了它们的有效性。这种情况搜索引擎可能返回一个根本不存在的网页，但是有超级链接指向它。然而这种结果可以被挑出来的，所以此类的问题很少发生。链接描述文字是对被引用网页的描述这个思想被用在WorldWideWebWorm中，主要因为它有助于搜索非文本信息，能够用少量的已下载文档扩大搜索范围。我们大量应用链接描述文字，因为它有助于提高搜索结果的质量。有效地利用链接描述文字技术上