【译】Google搜索引擎原理
试着翻译一篇学术型的论文,学习一下搜索引擎的基本原理。
原文在很多平台都有,被引量也是无出其右的了。题目:The Anatomy of a Large-Scale Hypertextual Web Search Engine
摘要
本文中,我们介绍了Google ,一个大规模搜索引擎的原型,充分利用了网络中以超文本形式呈现的文档结构。Google的设计目标是能够更高效地爬取并索引网络上的内容,并且搜索结果比现有的系统更好(satisfying)。此搜索引擎原型可以在斯坦福大学官网 找到(现在已经没有了),其中数据库包含至少2400万个网页的全部文本和链接。在工程上实现这样一个搜索引擎是一项艰巨的任务。搜索引擎需要为成千上万的网页建立索引,而每个页面都包含相当多的条目。搜索引擎每天需要对上千万的查询给出结果。尽管互联网上非常需要有这样大规模的搜索引擎,这方面的学术研究却少之又少。此外,由于技术的发展和网页数量的飞速增加,在今天构建一个网络搜索引擎已经远远不同于三年前了。这篇文章对我们的大型搜索引擎进行了一个深入的描述–是我们目前已知的最详细的描述。除了将传统的搜索技术应用到如此大规模的数据带来的困难外,还涉及到一些新的技术上的挑战,即如何使用超文本中附带的额外信息来产生更好的搜索结果。本文将阐述以下问题的解决方法:如何构建一个实用的、能够充分利用超文本中附加信息的大型系统。同时,我们也关注以下问题:如何高效地处理不可控的超文本内容(即任何人可以发布任何信息)的集合?
关键词:万维网;搜索引擎;信息检索;网页排名;Google
1. 引言
互联网给信息检索带来了新的挑战。网络上的信息呈爆炸式地增长,在网络研究领域没有经验的用户数量也是与日俱增。人们喜欢使用链接起来的一个个网站(link graph)来进行网上冲浪,通常从一些比较好的由人工维护的索引或者搜索引擎(如Yahoo! )开始。人工维护的网站列表清单能够很好的覆盖一些流行的主题,但是从另一方面来说其选定的内容也很主观,且很难构建和维护,想要改善速度也很慢,并且不能覆盖全部的(包括一些圈内人[esoteric]的)主题。使用关键字匹配的自动化搜索引擎的搜索结果的相关程度又不能让人满意。更糟糕的是,一些广告商为了吸引用户的注意,常常采取一些措施来误导自动化的搜索引擎。我们构建的大型搜索引擎解决了现存系统的这些问题。它充分利用了超文本文档结构的附加信息,以此来提供更加高质量的搜索结果。我们将系统命名为Google,因为它是一个天文数字,即10100的另一种写法,与我们构建大规模搜索引擎的想法一致。
1.1 网络搜索引擎 – 规模增长:1994-2000
搜索引擎技术不得不随着网络规模的增长而出现引人注目的增长。1994年,世界上最早的搜索引擎之一,World Wide Web Worm【参考WWW 】,拥有110,000网络上可访问的文档和网页的索引。到了1997年的十一月,顶级的搜索引擎声称能够索引200万(WebCrawler)到1亿(Search Engine Watch)个网络文件不等。可以预见到2000年,互联网上一个复杂(搜索引擎)的索引将会包含超过10亿个文件。
1.2 Google:随着网络的增长而增长
1.3 设计目标
1.3.1 改善搜索质量
我们的主要目标是改善WEB搜索引擎的质量。在1994年,一些人认为通过一个完整的搜索索引可以很容易地找到任何东西。由The Best of the Web 1994–Navigators,“最好的导航器应该可以让人们轻松地找到任何东西(一旦所有的数据都被放到了互联网上)”(那时候搜索引擎的主要作用就是导航器navigator,即通过搜索引擎搜索到其他网站)。然而到了1997年,互联网有了很大的不同。任何用过搜索引擎的人都知道,决定搜索质量的因素不只是搜索结果的完整性了。Junk Results可能把所有用户感兴趣的结果都冲掉了。事实上,到1997年11月时,最好的四个商用搜索引擎中只有一个可以搜索到它自己(在搜索框中搜索自己的品牌名,如在百度一下百度,Google一下Google,取前十条结果)。造成这个现象的主要原因是,索引中文件的数量呈几何级数增加,但是用户看文件的能力没有增长。人们还是只会看前几条(页)。
因此,随着数量级的增长,我们需要一个拥有很高准确性的工具(返回高相关性的结果,比如前几十条)。事实上,我们希望只搜索到最相关的结果,因为与之有一点关系的结果可能有上万条。精确性是很重要的即使重复寻找系统中的所有文件。最近的一些研究表明更加hypertextual(超文本结构化)的信息有助于改善搜索结果。尤其引人注目的是,链接结构和链接文本为相关性判断和过滤掉不好的结果方面提供了有用的信息。Google同时使用了链接结构和锚(anchor)文本。
1.3.2 学术上搜索引擎的研究
Web(互联网)除了在数量上有巨大的增长之外,也变得越来越商业化。1993年有1.5%的网络服务器是.com域名,到了1997年就变成了60%。搜索引擎也逐渐从学术研究走向商业化。现在许多公司在开发搜索引擎,并很少透露技术细节。这使得搜索引擎技术变成了一个黑科技,并只是为了打广告用的。通过Google,我们希望在(搜索引擎)这个学术领域上能够得到更过认识和发展。
另一个重要的设计目标就是希望设计一个大多数人能够使用的系统。之所以要实现“大多数人能使用”,是因为多数有意思的研究需要用到现代网络上的大量数据。比如每天
2. 系统特性
2.1 网页排名:给网络世界带来秩序
2.1.1 网页排名算法描述
2.1.2 直观的论证
2.2 定位文本
2.3 其它特性
3. 相关工作
3.1 信息检索
3.2 网络和良好组织结构集合的区别
4. 系统详细分析
首先,我们对架构做一个高层次的讨论。其次,对一些重要的数据结构做一些深度的描述。最后,主要的应用:爬取、索引、搜索数据的性能将会被测试。
4.1 Google架构概览
本节,我们将对整个系统的工作流程做一个概要性的描述。接下来的几节我们会讨论具体的应用和数据结构。Google搜索引擎主要是用C/C++实现的(处于效率考虑),可以运行在Linux或Solaris上。
Google搜索引擎的网页爬取工作由多个分布式的爬虫完成。有一个包含需要被爬取的URL列表的URL server,被爬取的网页之后被送到存储服务器上。存储服务器把网页压缩并存储到仓库(repository)中。每一个网页都有一个相关联的ID(docID),每当网页中解析出一个新的URL时被赋值。索引函数被索引器(indexer)和分类器(sorter)执行。索引器执行一系列函数,包括读取repository,解压文件,解析文件内容。每个文件被转换成一个被称作hits的数据结构,根据不同单词的出现频率 。hits记录了单词、在文件中出现的位置、字体大小(字母个数?)的估计值、大小写。索引器把这些hits分成一系列barrels,产生一个部分分类的前序索引。索引器接着执行另一个功能。它将每个网页中所有的链接解析出来,在anchor files(锚文件)中存储关于它们的重要信息。这些文件包含了足够的信息来确定这些链接的走向(from->to)以及链接文字。
URL解析器读取anchor files,把相对URL转换成绝对URL,进而转换成docID。它将锚文本放入前序索引,以及与之相关的docID(anchor指向的文件)。它同时产生一个链接数据库,存储了成对的docID。这个链接数据库用来为所有文件计算PageRank。