G o o g l e最早期的论文
G o o g l e创始人拉里佩奇和谢尔盖布林（L a w r e n c e P a g e a n d S e r g e y B r i n）在大学期间发表的论文 《T h e A n a t o m y
o f a L a r g e-S c a l e H y p e r t e x t u a l W e b S e a r c h E n g i n e》翻译为《大型超文本网络搜索引擎的剖析》。 本文介绍了G o o g l e的主要原理。
烤肉炉子
本来有中英文对照的，但本人对英文看得烦，就把英文给删了。
当然，你可以一睹为快。
译文：
大型超文本网络搜索引擎的剖析
谢尔盖布林 拉里佩奇
{s e r g e y,p a g e}@c s.s t a n f o r d.e d u
喷墨打印机墨水
计算机科学系，斯坦福大学，斯坦福,C A94305
摘要
这篇文章中，我们介绍了g o o g l e，它是一个大型的搜索引擎（o f a l a r g e-s c a l e s e a r c h e n g i n e）的原型，搜索引擎在超文本中应用广泛。G o o g l e的设计能够高效地抓网页并建立索引，它的查询结果比其它现有系统都高明。这个原型的全文和超连接的数据库至少包含24000000个网页。我们可以h t t p://g o o g l e.s t a n f o r d.e d u/下载。 设计搜索引擎是一项富有挑战性的工作。搜索引擎为上亿个网页建立索引，其中包含大量迥然不同的词汇。而且每天要回答成千上万个查询。在网络中，尽管大型搜索引擎非常重要，但是学术界却很少研究它。此外由于技术的快速发展和网页的大量增加，现在建立一个搜索引擎和三年前完全不同。
本文详细介绍了我们的大型搜索引擎，据我们所知，在公开发表的论文中，这是第一篇描述地如此详细。除了把传统数据搜索技术应用到如此大量级网页中所遇到的问题，还有许多新的技术挑战，包括应用超文本中的附加信息改进搜索结果。
本文将解决这个问题，描述如何运用超文本中的附加信息，建立一个大型实用系统。任何人都可以在网上随意发布信息，如何有效地处理这些无组织的超文本集合，也是本文要关注的问题。
关键词 W o r l d W i d e W e b，搜索引擎，信息检索，P a g e R a n k,G o o g l e
1绪论
W e b给信息检索带来了新的挑战。W e b上的信息量快速增长，同时不断有毫无经验的新用户来体验W e b这门艺术。人们喜欢用超级链接来网上冲浪，通常都以象 Y a h o o这样重要的网页或搜索引擎开始。大家认为L i s t(目录)有效地包含了大家感兴趣的主题，但是它具有主观性，建立和维护的代价高，升级慢，不能包括所有深奥的主题。基于关键词的自动搜索引擎通常返回太多的低质量的匹配。使问题更遭的是，一些广告为了赢得人们的关注想方设法误导自动搜索引擎。 我们建立了一个大型搜索引擎解决了现有系统中的很多问题。应用超文本结构，大大提高了查询质量。我们的系统命名为g o o g l e，取名自g o o g o l的通俗拼法，即10的100次方，这和我们的目标建立一个大型搜索引擎不谋而合。
1.1网络搜索引擎—升级换代（s c a l i n g u p）：
1994-2000搜索引擎技术不得不快速升级（s c a l e d r a m a t i c a l l y）跟上成倍增长的w e b数量。1994年，第一个W e b搜索引擎，W o r l d W i d e W e b W o r m(W W W W)可以检索到110，000个网页和W e b的文件。到1994年11月，顶级的搜索引擎声称可以检索到2‘000’000（W e b C r a w l e r）
至100‘000’000个网络文件（来自 S e a r c h E n g i n e W a t c h）。可以预见到2000年，可检索到的网页将超过1‘000’000‘000。同时，搜索引擎的访问量也会以惊人的速度增长。在1997年的三四月份，W o r l d W i d e W e b W o r m平均每天收到1500个查询。
在1997年11月，A l t a v i s t a声称它每天要处理大约20’000’000个查询。随着网络用户的增长，到2000年，自动搜索引擎每天将处理上亿个查询。我们系统的设计目标要解决许多问题，包括质量和可升级性，引入升级搜索引擎技术（
s c a l i n g s e a r c h e n g i n e t e c h n o l o g y），把它升级到如此大量的数据上。
1.2G o o g l e：
跟上 W e b的步伐（S c a l i n g w i t h t h e W e b）建立一个能够和当今w e b规模相适应的搜索引擎会面临许多挑战。抓网页技术必须足够快，才能跟上网页变化的速度（k e e p t h e m u p t o d a t e）。存储索引和文档的空间必须足够大。索引系统必须能够有效地处理上千亿的数据。处理查询必须快，达到每秒能处理成百上千个查询（h u n d r e d s t o t h o u s a n d s p e r s e c o n d.）。随着W e b的不断增长，这些任务变得越来越艰巨。然而硬件的执行效率和成本也在快速增长，可以部分抵消这些困难。
还有几个值得注意的因素，如磁盘的寻道时间（d i s k s e e k t i m e），操作系统的效率（o p e r a t i n g s y s t e m r o b u s t n e s s ）。在设计G o o g l e的过程中，我们既考虑了W e b的增长速度，又考虑了技术的更新。G o o g l e的设计能够很好的升级处理海量数据集。它能够有效地利用存储空间来存储索引。优化的数据结构能够快速有效地存取（参考4.2节）。进一步，我们希望，相对于所抓取的文本文件和H T M L网页的数量而言，存储和建立索引的代价尽可能的小（参考附录B）。对于象
G o o g l e这样的集中式系统，采取这些措施得到了令人满意的系统可升级性（s c a l i n g p r o p e r t i e s）。
1.3设计目标
1.3.1提高搜索质量。我们的主要目标是提高W e b搜索引擎的质量。
1994年，有人认为建立全搜索索引（a c o m p l e t e s e a r c h i n d e x）可以使查任何数据都变得容易。根据B e s t o f t h e W e b1994--N a v i g a t o r s，“最好的导航服务可以使在W e b上搜索任何信息都很容易（当时所有的数据都可以被登录）”。然而1997年的W e b就迥然不同。近来搜索引擎的用户已经证实索引的完整性不是评价搜索质量的唯一标准。用户感兴趣的搜索结果往往湮没在“垃圾结果J u n k r e s u l t”中。实际上，到1997年11月为止，四大商业搜索引擎中只有一个能够到它自己（搜索自己名字时返回的前十个结果中有它自己）。导致这一问题的主要原因是文档的索引数目增加
了好几个数量级，但是用户能够看的文档数却没有增加。用户仍然只希望看前面几十个搜索结果。因此，当集合增大时，我们就需要工具使结果精确（在返回的前几十个结果中，有关文档的数量）。由于是从成千上万个有点相关的文档中选出几十个，实际上，相关的概念就是指最好的文档。高精确非常重要，甚至以响应（系统能够返回的有关文档的总数）为代价。令人高兴的是利用超文本链接提供的信息有助于改进搜索和其它应用。尤其是链接结构和链接文本，为相关性的判断和高质量的过滤提供了大量的信息。G o o g l e既利用了链接结构又用到了a n c h o r文本（见2.1和2.2节）。
1.3.2搜索引擎的学术研究随着时间的流逝，除了发展迅速，W e b越来越商业化。
1993年，只有1.5%的W e b服务是来自.c o m域名。到1997年，超过了60%。同时，搜索引擎从学术领域走进商业。到现在大多数搜索引擎被公司所有，很少技公开术细节。这就导致搜索引擎技术很大程度上仍然是暗箱操作，并倾向做广告（见附录A）。G o o g l e的主要目标是推动学术领域在此方面的发展，和对它的了解。另一个设计目标是给大家一个实用的系统。应用对我们来说非常重要，因为现代网络系统中存在大量的有用数据（u s b e c a u s e w e t h i n k s o m e o f t h e m o s t
i n t e r e s t i n g r e s e a r c h w i l l i n v o l v e l e v e r a g i n g t h e v a s t a m o u n t o f u s a g e d a t a t h a t i s a v a i l a b l e f r o m m o d e r n w e b s y s t e m s）。例如，每天有几千万个研究。然而，得到这些数据却非常困难，主要因为它们没有商业价值。我们最后的设计目标是建立一个
体系结构能够支持新的关于海量W e b数据的研究。为了支持新研究，G o o g l e以压缩的形式保存了实际所抓到的文档。设计G o o g l e的目标之一就是要建立一个环境使其他研究者能够很快进入这个领域，处理海量W e b数据，得到满意的结果，而通过其它方法却很难得到结果。系统在短时间内被建立起来，已经有几篇论文用到了G o o g l e建的数据库，更多的在起步中。我们的另一个目标是建立一个宇宙空间实验室似的环境，在这里研究者甚至学生都可以对我们的海量W e b数据设计或做一些实验。
2.系统特点
G o o g l e搜索引擎有两个重要特点，有助于得到高精度的搜索结果。
第一点，应用W e b的链接结构计算每个网页的R a n k值，称为P a g e R a n k，将在98页详细描述它。
第二点，G o o g l e利用超链接改进搜索结果。 P R值和超链接锚文本是G o o g l e的精髓。
2.1P a g e R a n k：给网页排序：
W e b的引用（链接）图是重要的资源，却被当今的搜索引擎很大程度上忽视了。我们建立了一个包含518000000个超链接的图，它是一个具有重要意义的样本。这些图能够快速地计算网页的P a g e R
a n k值，它是一个客观的标准，较好的符合人们心目中对一个网页重要程度的评价，建立的基础是通过引用判断重要性。因此在w e b中，P a g e R a n k能够优化关键词查询的结果。对于大多数的主题，在网页标题查询中用P a g e R a n k优化简单文本匹配，我们得到了令人惊叹的结果（从
g o o g l e.s t a n f o r d.e d u可以得到演示）。对于G o o g l e主系统中的全文搜索，P a g e R a n k也帮了不少忙。
2.1.1计算P a g e R a n k
文献检索中的引用理论用到W e b中，引用网页的链接数，一定程度上反映了该网页的重要性和质量。P a g e R a n k发展了这种思想，网页间的链接是不平等的。
P a g e R a n k定义如下：我们假设T1…T n指向网页A（例如，被引用）。参数d是制动因子，使结果在0，1之间。通常d等于0.85。在下一节将详细介绍d。C（A）定义为网页A指向其它网页的链接数，
网页A的P a g e R a n k值由下式给出： P R(A)=(1-d)+d(P R(T1)/C(T1)+...+P R(T n)/C(T n))这是P R值计算公式
注意P a g e R a n k的形式，分布到各个网页中，因此所有网页的P a g e R a n k和是1。 P a g e R a n k或P R（A）可以用简单的迭代算法计算，相应规格化W e b链接矩阵的主特征向量。中等规模的网
站计算26‘000’000网页的 P a g e R a n k值要花费几小时。还有一些技术细节超出了本文论述的范围。
2.1.2直觉判断 P a g e R a n k被看作用户行为的模型。
我们假设网上冲浪是随机的，不断点击链接，从不返回，最终烦了，另外随机选一个网页重新开始冲浪。随机访问一个网页的可能性就是它的P a g e R a n k值。制动因子d是随机访问一个网页烦了的可能性，随机另选一个网页。对单个网页或一组网页，一个重要的变量加入到制动因子d中。这允许个人可以故意地误导系统，以得到较高的P a g e R a n k值。我们还有其它的P a g e R a n k算法，见98页。
另外的直觉判断是一个网页有很多网页指向它，或者一些P a g e R a n k值高的网页指向它，则这个网页很重要。直觉地，在W e b中，一个网页被很多网页引用，那么这个网页值得一看。一个网页被象Y a h o o这样重要的主页引用即使一次，也值得一看。如果一个网页的质量不高，或者是死链接，象Y a h o o这样的主页不会链向它。P a g e R a n k处理了这两方面因素，并通过网络链接递归地传递。
注意两个字：直觉，也就是情理上可以这样认为。
2.2链接描述文字（A n c h o r T e x t）：
我们的搜索引擎对链接文本进行了特殊的处理。大多数搜索引擎把链接文字和它所链向的网页（t h e p a g e t h a t t h e
l i n k i s o n）联系起来。另外，把它和链接所指向的网页联系起来。这有几点好处。
第一，通常链接描述文字比网页本身更精确地描述该网页。
第二，链接描述文字可能链向的文档不能被文本搜索引擎检索到，例如图像，程序和数据库。有可能使返回的网页不能被抓到。注意哪些抓不到的网页将会带来一些问题。在返回给用户前检测不了它们的有效性。这种情况搜索引擎可能返回一个根本不存在的网页，但是有超级链接指向它。然而这种结果可以被挑出来的，所以此类的问题很少发生。链接描述文字是对被链向网页的宣传，这个思想被用在W o r l d W i d e W e b W o r m中，主要因为它有助于搜索非文本信息，能够用少量的已下载文档扩大搜索范围。我们大量应用链接描述文字，因为它有助于提高搜索结果的质量。有效地利用链接描述文字技术上存在一些困难，因为必须处理大量的数据。现在我们能抓到24000000个网页，已经检索到259000000多个链
接描述文字。
2.3其它特点除了P a g e R a n k和应用链接描述文字外，G o o g l e还有一些其它特点。
第一，所有h i t都有位置信息，所以它可以在搜索中广泛应用邻近性（p r o x i m i t y）。 h i t的概念，在后面会看到。
第二，G o o g l e跟踪一些可视化外表细节，例如字号。黑体大号字比其它文字更重要。
第三，知识库存储了原始的全文h t m l网页。
3有关工作
家庭智能控制
W e b检索研究的历史简短。W o r l d W i d e W e b W o r m（）是最早的搜索引擎之一。后来出现了一些用于学术研究的搜索引擎，现在它们中的大多数被上市公司拥有。与W e b的增长和搜索引擎的重要性相比，有关当今搜索引擎技术的优秀论文相当少。根据M i c h a e l M a u l d i n（L y c o s I n c的首席科学家）)，“各种各样的服务（包括L y c o s）非常关注这些数据库的细节。”虽然在搜索引擎的某些特点上做了大量工作。具有代表性的工作有，对现有商业搜索引擎的结果进行传递，或建立小型的个性化的搜索引擎。最后有关信息检索系统的研究很多，尤其在有组织机构集合（w e l l c o n t r o l l e d
c o l l e c t i o n s）方面。在下面两节，我们将讨论在信息检索系统中的哪些领域需要改进以便更好的工作在W e b上。
无取向硅钢
3.1信息检索信息检索系统诞生在几年前，并发展迅速。
然而大多数信息检索系统研究的对象是小规模的单一的有组织结构的集合，例如科学论文集，或相关主题的新闻故事。实际上，信息检索的主要基准，（t h e T e x t R e t r i e v a l C o n f e r e n c e），用小规模的、有组织结构的集合作为它们的基准。
大型文集基准只有20G B，相比之下，我们抓到的24000000个网页占147G B。在T R E C上工作良好的系统，在W e b上却不一定产生好的结果。例如，标准向量空间模型企图返回和查询请求最相近的文档，把查询请求和文档都看作由出现在它们中的词汇组成的向量。在W e b环境下，这种策略常常返回非常短的文档，这些文档往往是查询词再加几个字。例如，查询“B i l l C l i n t o n”，返回的网页只包含“B i l l C l i n t o n S u c k s”，这是我们从一个主要搜索引擎中看到的。网络上有些争议，用户应该更准确地表达他们想查询什么，在他们的查询请求中用更多的词。我们强烈反对这种观点。如果用户提出象“B i l l C l i n t o n”这样的查询请求，应该得到理想的查询结果，因为这个主题有许多高质量的信息。象所给的例子，我们认为信息检索标准需要发展，以便有效地处理W e b数据。
3.2有组织结构的集合（W e l l C o n t r o l l e d C o l l e c t i o n s）与W e b的不同点
W e b是完全无组织的异构的大量文档的集合。W e b中的文档无论内在信息还是隐含信息都存在大量的异构性。例如，文档内部就用了不同的语言（既有人类语言又有程序），词汇（e m a i l地址，链接，
，电话号码，产品号），类型（文本，H T M L，P D F，图像，声音），有些甚至是机器创建的文件（l o g文件，或数据库的输出）。可以从文档中推断出来，但并不包含在文档中的信息称为隐含信息。隐含信息包括来源的信誉，更新频率，质量，访问量和引用。不但隐含信息的可能来源各种各样，而且被检测的信息也大不相同，相差可达好几个数量级。例如，一个重要主页的使用量，象Y a h o o每天浏览数达到上百万次，于此相比无名的历史文章可能十年才被访问一次。很明显，搜索引擎对这两类信息的处理是不同的。 W e b与有组织结构集合之间的另外一个明显区别是，事实上，向W e b上传信息没有任何限制。灵活利用这点可以发布任何对搜索引擎影响重大的信息，使路由阻塞，加上为牟利故意操纵搜索引擎，这些已经成为一个严重的问题。这些问题还没有被传统的封闭的信息检索系统所提出来。它关心的是元数据的努力，这在W e b搜索引擎中却不适用，因为网页中的任何文本都不会向用户声称企图操纵搜索引擎。甚至有些公司为牟利专门操纵搜索引擎。
4系统分析（S y s t e m A n a t o m y）
首先，我们提供高水平的有关体系结构的讨论。然后，详细描述重要的数据结构。最后，主要应用：抓网页，索引，搜索将被严格地检查。 F i g u r e1.H i g h L e v e l G o o g l e A r c h i t e c t u r e
4.1G o o g l e体系结构概述
这一节，我们将看看整个系统是如何工作的（g i v e a h i g h l e v e l），见图1。本节不讨论应用和数
据结构，在后几节中讨论。为了效率大部分G o o g l e是用c或c++实现的，既可以在S o l a r i s也可以在L i n u x上运行。
G o o g l e系统中，抓网页（下载网页）是由几个分布式c r a w l e r s完成的。一个U R L服务器负责向c r a w l e r s提供U R L列表。抓来的网页交给存储服务器 s t o r e s e r v e r。然后，由存储服务器压缩网页并把它们存到知识库r e p o s i t o r y中。每个网页都有一个I D，称作d o c I D，当新U R L从网页中分析出时，就被分配一个d o c I D。由索引器和排序器负责建立索引i n d e x
f u n c t i o n。索引器从知识库中读取文档，对其解压缩和分析。每个文档被转换成一组词的出现情况，称作命中h i t s。
H i t s纪录了词，词在文档中的位置，最接近的字号，大小写。索引器把这些h i t s分配到一组桶b a r r e l中，产生经过部分排序后的索引。索引器的另一个重要功能是分析网页中所有的链接，将有关的重要信息存在链接描述a n c h o r s文件中。该文件包含了足够的信息，可以用来判断每个链接链出链入节点的信息，和链接文本。 U R L分解器r e s o l v e r阅读链接描述a n c h o r s文件，并把相对U R L转换成绝对U R L，再转换成d o c I D。为链接描述文本编制索引，并与它所指向的d o c I D关联起来。同时建立由d o c I D对组成的链接数据库。用于计算所有文档的P a g e R a n k值。用d o c I D分类后的b a r r e l s，送给排序器烟雾净化
s o r t e r，再根据w o r d I D进行分类，建立反向索引i n v e r t e d i n d e x。这个操作要恰到好处，以便几乎不需要暂存空间。排序器还给出d o c I D和偏移量列表，建立反向索引。一个叫D u m p L e x i c o n的程序把这个列表和由索引器产生的字典结合在一起，建立一个新的字典，供搜索器使用。这个搜索器就是利用一个W e b服务器，使用由D u m p L e x i c o n所生成的字典，利用上述反向索引以及页面等级P a g e R a n k来回答用户的提问。
4.2主要数据结构
经过优化的G o o g l e数据结构，能够用较小的代价抓取大量文档，建立索引和查询。虽然近几年C P U和输入输出速率迅速提高。磁盘寻道仍然需要10m s。任何时候G o o g l e系统的设计都尽可能地避免磁盘寻道。这对数据结构的设计影响很大。4.2.1大文件
大文件B i g F i l e s是指虚拟文件生成的多文件系统，用长度是64位的整型数据寻址。多文件系统之间的空间分配是自动完
成的。B i g F i l e s包也处理已分配和未分配文件描述符。由于操纵系统不能满足我们的需要，B i g F i l e s也支持基本的压缩选项。
4.2.2知识库
R e p o s i t o r y D a t a S t r u c t u r e知识库包含每个网页的全部H T M L。每个网页用z l i b（见R F C1950）压缩。压缩技术的选择既要考虑速度又要考虑压缩率。我们选择z l i b的速度而不是压缩率很高的b z i p。知识库用b z i p的压缩率接近4：1。而用
z l i b的压缩率是3：1。文档一个挨着一个的存储在知识库中，前缀是d o c I D，长度，U R L，见图2。访问知识库不需要其它的数据结构。这有助于数据一致性和升级。用其它数据结构重构系统，我们只需要修改知识库和c r a w l e r错误列表文件。
4.2.3文件索引
文件索引保存了有关文档的一些信息。索引以d o c I D的顺序排列，定宽I S A M（I n d e x s e q u e n t i a l a c c e s s m o d e）。每条记录包括当前文件状态，一个指向知识库的指针，文件校验和，各种统计表。如果一个文档已经被抓到，指针指向d o c i n f o 文件，该文件的宽度可变，包含了U R L和标题。否则指针指向包含这个U R L的U R L列表。这种设计考虑到简洁的数据结构，以及在查询中只需要一个磁盘寻道时间就能够访问一条记录。还有一个文件用于把U R L转换成d o c I D。它是U R L校验和与相应d o c I D的列表，按校验和排序。要想知道某个U R L的d o c I D，需要计算U R L的校验和，然后在校验和文件中执行二进制查，到它的d o c I D。通过对这个文件进行合并，可以把一批U R L转换成对应的d o c I D。U R L分析器用这项技术把U R L转换成d o c I D。这种成批更新的
模式是至关重要的，否则每个链接都需要一次查询，假如用一块磁盘，322‘000’000个链接的数据集合将花费一个多月的时间。
4.2.4词典
词典有几种不同的形式。和以前系统的重要不同是，词典对内存的要求可以在合理的价格内。现在实现的系统，一台
256M内存的机器就可以把词典装入到内存中。现在的词典包含14000000词汇（虽然一些很少用的词汇没有加入到词典中）。它执行分两部分—词汇表（用n u l l分隔的连续串）和指针的哈希表。不同的函数，词汇表有一些辅助信息，这超出了本文论述的范围。
4.2.5h i t l i s t
h i t l i s t是一篇文档中所出现的词的列表，包括位置，字号，大小写。H i t l i s t占很大空间，用在正向和反向索引中。因此，它的表示形式越有效越好。我们考虑了几种方案来编码位置，字号，大小写—简单编码（3个整型数），紧凑编码（支持优化分配比特位），哈夫曼编码。H i t的详细信息见图3。我们的紧凑编码每个h i t用2字节。有两种类型h i t，特殊h i t和普通h i t。特殊h i t包含U R L，标题，链接描述文字，m e t a t a g。普通h i t包含其它每件事。它包括大小写特征位，字号，12比特用
于描述词在文档中的位置（所有超过4095的位置标记为4096）。字号采用相对于文档的其它部分的相对大小表示，占3比特(实际只用7个值，因为111标志是特殊h i t)。特殊h i t由大小写特征位，字号位为7表示它是特殊h i t，用4比特表示特殊h i t的类型，8比特表示位置。对于a n c h o r h i t八比特位置位分出4比特用来表示在a n c h o r中的位置，4比特用于表明a n c h o r出现的哈希表h a s h o f t h e d o c I D。短语查询是有限的，对某些词没有足够多的a n c h o r。我们希望更新
a n c h o r h i t的存储方式，以便解决地址位和d o c I D h a s h域位数不足的问题。
因为搜索时，你不会因为文档的字号比别的文档大而特殊对待它，所以采用相对字号。 h i t表的长度存储在h i t前。为节省空间h i t表长度，在正向索引中和w o r d I D结合在一起，在反向索引中和d o c I D结合存储。这就限制它相应地只占8到5比特（用些技巧，可以从w o r d I D中借8b i t）如果大于这些比特所能表示的长度，用溢出码填充，其后两字节是真正的长度。 F i g u r e3.F o r w a r d a n d R e v e r s e I n d e x e s a n d t h e L e x i c o n
4.2.6正向索引
实际上，正向索引已经部分排序。它被存在一定数量的b a r r e l中（我们用64个b a r r e l s）。每个b a r r e l装着一定范围的
w o r d I D。如果一篇文档中的词落到某个b a r r e l，它的d o c I D将被记录到这个b a r r e l中，紧跟着那些词（文档中所有的词汇，还是落入该b a r r e l中的词汇）对应的h i t l i s t。这种模式需要稍多些的存储空间，因为一个d o c I D被用多次，但是它节省了桶数和时间，最后排序器进行索引时降低编码的复杂度。更进一步的措施是，我们不是存储d o c I D本身，而是存储相对于该桶最小的d o c I D的差。用这种方法，未排序的b a r r e l的d o c I D只需24位，省下8位记录h i t l i s t长。
4.2.7反向索引
除了反向索引由s o r t e r加工处理之外，它和正向索引包含相同的桶。对每个有效的d o c I D，字典包含一个指向该词所在桶的指针。它指向由d o c I D和它的相应h i t l i s t组成的d o c l i s h，这个d o c l i s t代表了所有包含该词的文档。 d o c l i s t中d o c I D 的顺序是一个重要的问题。最简单的解决办法是用d o c l i s h排序。这种方法合并多个词时很快。另一个可选方案是用文档中该词出现的次数排序。这种方法回答单词查询，所用时间微不足道。当多词查询时几乎是从头开始。并且当用其它
R a n k算法改进索引时，非常困难。我们综合了这两种方法，建立两组反向索引b a r r e l，一组b a r r e l s的h i t l i s t只包含标题和a n c h o r h i t，另一组b a r r e l包含全部的h i t l i s t。我们首先查第一组索引桶，看有没有匹配的项，然后查较大的那组桶。
4.3抓网页运行
网络爬行机器人是一项具有挑战性的任务。执行的性能和可靠性甚至更重要，还有一些社会焦点。网络爬行是一项非常薄弱的应用，它需要成百上千的w e b服务器和各种域名服务器的参与，这些服务器不是我们系统所能控制的。为了覆盖几十亿的网页，G o o g l e拥有快速的分布式网络爬行系统。一个U R L服务器给若干个网络爬行机器人（我们采用3个）提供U R L 列表。U R L服务器和网络爬行机器人都是用P y t h o n实现的。每个网络爬行机器人可以同时打开300个链接。抓取网页必须足够快。最快时，用4个网络爬行机器人每秒可以爬行100个网页。速率达每秒600K。执行的重点是 D N S。每个网络爬行机器人有它自己的D N S c a c h e，所以它不必每个网页都查D N S。每一百个连接都有几种不同的状态：查D N S，连接主机，发送请求，接收回答。这些因素使网络爬行机器人成为系统比较复杂的部分。它用异步I O处理事件，若干请求队列从一个网站到另一个网站不停的抓取网页。运行一个链接到500多万台服务器的网页爬行机器人，产生1千多万登陆口，导致了大量的E m a i l和电话。因为网民众多，总有些人不知道网络爬行机器人是何物，这是他们看到的第一个网络爬行机器人。几乎每天我们都会收到这样的E m a i l“哦，你从我们的网站看了太多的网页，你想干什么？”还有一些人不知道网络搜索机器人避免协议（t h e r o b o t s e x c l u s i o n p r o t o c o l），以为他们的网页上写着“版权所有，勿被索引”的字样就会
被保护不被索引，不必说，这样的话很难被w e b c r a w l e r理解。因为数据量如此之大，还会遇到一些意想不到的事情。例如，我们的系统曾经企图抓一个在线游戏，结果抓到了游戏中的大量垃圾信
息。解决这个问题很简单。但是我们下载了几千万网页后才发现了这个问题。因为网页和服务器的种类繁多，实际上不在大部分I n t e r n e t上运行它就测试一个网页爬行机器人是不可能。总是有几百个隐含的问题发生在整个w e b的一个网页上，导致网络爬行机器人崩溃，或者更糟，导致不可预测的不正确的行为。能够访问大部分I n t e r n e t的系统必须精力充沛并精心测试过。由于象c r a w l e r这样大型复杂的系统总是产生这样那样的问题，因此花费一些资源读这些 E m a i l，当问题发生时解决它，是有必要的。
4.4W e b索引分析
任何运行在整个W e b上的分析器必须能够处理可能包含错误的大型集合。范围从H T M L标记到标记之间几K字节的0，非
A S C I I字符，几百层H T M L标记的嵌套，各种各样令人难以想象的错误。为了获得最大的速度，我们没有采用Y A C C产生上下文无关文法C F G分析器，而是采用灵活的方式产生词汇分析器，它自己配有堆栈。分析器的改进大大提高了运行速度，它的精力如此充沛完成了大量工作。把文档装入b a r r e l建立索引—分析完一篇文档，之后把该文档装入b a r r e l中，用内存中的h a s h表—字典，每个词汇被转换成一个 w o r d I D。当h a s h表字典中加入新的项时，笨拙地存入文件。一旦词汇被转换成w o r d I D，它们在当前文档的出现就转换成h i t l i s t，被写进正向b a r r e l。索引阶段并行的主要困难是字典需要共享。
我们采用的方法是，基本字典中有140万个固定词汇，不在基本字典中的词汇写入日志，而不是共享字典。这种方法多个索引器可以并行工作，最后一个索引器只需处理一个较小的额外词汇日志。排序—为了建立反向索引，排序器读取每个正向b a r r e l，以 w o r d I D排序，建立只有标题a n c h o r h i t的反向索引b a r r e l和全文反向索引b a r r e l。这个过程一次只处理一个b a r r e l，所以只需要少量暂存空间。排序阶段也是并行的，我们简单地同时运行尽可能多的排序器，不同的排序器处理不同的桶。由于b a r r e l不适合装入主存，排序器进一步依据w o r d I D和d o c I D把它分成若干篮子，以便适合装入主存。然后排序器把每个篮子装入主存进行排序，并把它的内容写回到短反向b a r r e l和全文反向b a r r e l。
4.5搜索
搜索的目标是提供有效的高质量的搜索结果。多数大型商业搜索引擎好像在效率方面花费了很大力气。因此我们的研究以搜索质量为重点，相信我们的解决方案也可以用到那些商业系统中。
G o o g l e查询评价过程见图4。
1.分析查询。
2.把词汇转换成w o r d I D。
3.在短b a r r e l中查每个词汇d o c l i s t的开头。
4.扫描d o c l i s t直到到一篇匹配所有关键词的文档
5.计算该文档的r a n k
6.如果我们在短b a r r e l，并且在所有d o c l i s t的末尾，开始从全文b a r r e l的d o c l i s t的开头查每个词，g o t o第四步
7.如果不在任何d o c l i s t的结尾，返回第四步。
8.根据r a n k排序匹配文档，返回前k个。图4G o o g l e查询评价在有限的响应时间内，一旦到一定数量的匹配文档，搜索引擎自动执行步骤8。这意味着，返回的结果是子优化的。我们现在研究其它方法来解决这个问题。过去根据P a g e R a n k 排序h i t，看来能够改进这种状况。
4.5.1R a n k i n g系统
G o o g l e比典型搜索引擎保存了更多的w e b信息。每个h i t l i s t包括位置，字号，大小写。另外，我们还考虑了链接描述文字。R a n k综合所有这些信息是困难的。r a n k i n g函数设计依据是没有某个因素对r a n k影响重大。首先，考虑最简单的情况—单个词查询。为了单个词查询中一个文档的r a
能量传送器n k，G o o l e在文档的h i t l i s t中查该词。G o o g l e认为每个h i t是几种不同类型（标题，链接描述文字a n c h o r，U R L，普通大字号文本，普通小字号文本，……）之一，每种有它自己的类型权重。类型权重建立了一个类型索引向量。G o o g l e计算h i t l i s t中每种h i t的数量。然后每个h i t数转换成c o u n t-w e i g h t。
C o u n t-w e i g h t开始随h i t数线性增加，很快逐渐停止，以至于h i t数与此不相关。我们计算c o u n t-w e i g h t向量和
t y p e-w e i g h t向量的标量积作为文档的I R值。最后I R值结合P a g e R a n k作为文档的最后r a n k。 对于多词查询，更复杂些。现在，多词h i t l i s t必须同时扫描，以便关键词出现在同一文档中的权重比分别出现时高。相邻词的h i t一起匹配。对每个匹配h i t的集合计算相邻度。相邻度基于h i t在文档中的距离，分成10个不同的b i n值，范围从短语匹配到根本不相关。不仅计算每类h i t数，而且要计算每种类型的相邻度，每个类型相似度对，有一个类型相邻度权t y p e-p r o x-w e i g h t。
C o u n t转换成c o u n t-w e i g h t，计算c o u n t-w e i g h t、 t y p e-p r o x-w e i g h t的标量积作为I R值。应用某种d e b u g m o d e所有这些数和矩阵与查询结果一起显示出来。这些显示有助于改进r a n k系统。
4.5.2反馈
r a n k函数有很多参数象t y p e-w e i g h t和t y p e-p r o x-w e i g h t。指明这些参数的正确值有点黑艺术b l a c k a r t。为此，我们的搜索引擎有一个用户反馈机制。值得信任的用户可以随意地评价返回的结果。保存反馈。然后，当修改r a n k函数时，对比以前搜索的 r a n k，我们可以看到修改带来的的影响。虽然不是十全十美，但是它给出了一些思路，当r a n k函数改变时对搜索结果的影响。
5执行和结果
搜索结果的质量是搜索引擎最重要的度量标准。完全用户评价体系超出了本文的论述范围，对于大多数搜索，我们的经验说明G o o g l e的搜索结果比那些主要的商业搜索引擎好。作为一个应用P a g e R a n k，链接描述文字，相邻度的例子，图4给出了G o o g l e搜索b i l l C l i n t o n的结果。它说明了G o o g l e的一些特点。服务器对结果进行聚类。这对过滤结果集合相当有帮助。这个查询，相当一部分结果来自 w h i t e h o u s e.g o v域，这正是我们所需要的。现在大多数商业搜索引擎不会返回任何来自w h i t e h o u s e.g o v的结果，这是相当不对的。注意第一个搜索结果没有标题。因为它不是被抓到的。G o o g l e是根据链接描述文字决定它是一个好的查询结果。同样地，第五个结果是一个E m a i l地址，当然是不可能抓到的。也是链接描述文字的结果。所有这些结果质量都很高，最后检查没有死链接。因为它们中的大部分P a g e R a n k值较高。P a g e R a n k百分比用红线条表示。没有结果只含B i l l没有C l i n t o n或只含C l i n t o n没有B i l l。因为词出现的相近性非常重要。当然搜索引擎质量的真实测试包含广泛的用户学习或结果分析，此处篇幅有限，请读者自己去体验G o o g l
e，
h t t p://g o o g l e.s t a n f o r d.e d u/。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议