Google搜索引擎原理

这篇文章中，我们介绍了google，它是一个大型的搜索引擎（of a large-scale search engine）的原型，搜索引擎在超文本中应用广泛。Google的设计能够高效地抓网页并建立索引，它的查询结果比其它现有系统都高明。这个原型的全文和超连接的数据库至少包含24′000′000个网页。我们可以从http://google.stanford.edu/ 下载。

设计搜索引擎是一项富有挑战性的工作。搜索引擎为上亿个网页建立索引，其中包含大量迥然不同的词汇。而且天天要回答成千上万个查询。在网络中，尽管大型搜索引擎非常重要，但是学术界却很少研究它。此外由于技术的快速发展和网页的大量增加，现在建立一个搜索引擎和三年前完全不同。

本文具体介绍了我们的大型搜索引擎，据我们所知，在公开发表的论文中，这是第一篇描述地如此具体。除了把传统数据搜索技术应用到如此大量级网页中所碰到的问题，还有许多新的技术挑战，包括应用超文本中的附加信息改进搜索结果。

本文将解决这个问题，描述如何运用超文本中的附加信息，建立一个大型实用系统。任何人都可以在网上随意发布信息，如何有效地处理这些无组织的超文本集合，也是本文要关注的问题。

关键词 World Wide Web，搜索引擎，信息检索，PageRank, Google

1 绪论

Web给信息检索带来了新的挑战。Web上的信息量快速增长，同时不断有毫无经验的新用户来体验Web这门艺术。人们喜欢用超级链接来网上冲浪，通常都以象Yahoo这样重要的网页或搜索引擎开始。大家认为List(目录)有效地包含了大家感爱好的主题，但是它具有主观性，建立和维护的代价高，升级慢，不能包括所有深奥的主题。基于关键词的自动搜索引擎通常返回太多的低质量的匹配。使问题更遭的是，一些广告为了赢得人们的关注想方设法误导自动搜索引擎。我们建立了一个大型搜索引擎解决了现有系统中的很多问题。应用超文本结构，大大提高了查询质量。我们的系统命名为google，取名自googol的通俗拼法，即10的100次方，这和我们的目标建立一个大型搜索引擎不谋而合。

1.1网络搜索引擎—升级换代（scaling up）：

1994-2000 搜索引擎技术不得不快速升级（scale dramatically）跟上成倍增长的web数量。
1994年，第一个Web搜索引擎，World Wide Web Worm(WWWW)可以检索到110，000个网页和Web的文件。
到1994年11月，顶级的搜索引擎声称可以检索到2‘000′000（WebCrawler）至100‘000′000个网络文件（来自 Search Engine Watch）。
可以预见到2000年，可检索到的网页将超过1‘000′000‘000。同时，搜索引擎的访问量也会以惊人的速度增长。
在1997年的三四月份，World Wide Web Worm 平均天天收到1500个查询。
在1997年11月，Altavista 声称它天天要处理大约20′000′000个查询。随着网络用户的增长.
到2000年，自动搜索引擎天天将处理上亿个查询。我们系统的设计目标要解决许多问题，包括质量和可升级性，引入升级搜索引擎技术（scaling search engine technology），把它升级到如此大量的数据上。

1.2 Google：

跟上Web的步伐（Scaling with the Web）建立一个能够和当今web规模相适应的搜索引擎会面临许多挑战。抓网页技术必须足够快，才能跟上网页变化的速度（keep them up to date）。存储索引和文档的空间必须足够大。索引系统必须能够有效地处理上千亿的数据。处理查询必须快，达到每秒能处理成百上千个查询（hundreds to thousands per second.）。随着Web的不断增长，这些任务变得越来越艰巨。然而硬件的执行效率和成本也在快速增长，可以部分抵消这些困难。还有几个值得注重的因素，如磁盘的寻道时间（disk seek time），操作系统的效率（operating system robustness）。在设计Google的过程中，我们既考虑了Web的增长速度，又考虑了技术的更新。Google的设计能够很好的升级处理海量数据集。它能够有效地利用存储空间来存储索引。优化的数据结构能够快速有效地存取（参考4.2节）。进一步，我们希望，相对于所抓取的文本文件和HTML网页的数量而言，存储和建立索引的代价尽可能的小（参考附录B）。对于象Google这样的集中式系统，采取这些措施得到了令人满足的系统可升级性（scaling properties）。