开山之作（^_^）

  前几天做了个“伟大”的决定，开始写博客了 。本来前两天一直在帮别人搞VE，GWT，SWT等桌面开发插件的安装，发现以前弄过的那些东西过一段时间又忘记了。要是把这些都写在博客里，以后找起来就简单点了，不用费那么多事情了。
  开山之作，先贴篇我带的师妹的毕业设计中要求翻译的文章吧。个人觉得还可以，因为在我大四的时候我搞不出这水平来 。下面直接来了。。。。。。
     

剖析大规模超链接文本Web搜索引擎

摘要
 
  在这个章节，我们将介绍Google搜索引擎，它是一个大规模搜索引擎的模型。这种搜索引擎很大程度上使用了超链接文本这种结构。Google搜索引擎被设计成一种能有效地在Web上抓取网页和索引的结构，比起现在存在的系统中，它能产生更多令人满意的结果。这个模型有一个完整的文档，并且在它的超链接数据库中至少有2400000个网页，这些网页都在http://google.stanford.ede/。
  对于工程师来说，搜索引擎是一项富有挑战性的工作。搜索引擎可以搜索成千上万的网页，它需要处理有数量可观的截然不同的时段。它每天需要应答成千上百万的查询请求。尽管大规模的Web搜索引擎是非常重要的，但是只有非常少的研究者才能完善它们。而且，由于技术快速的提高和互联网的扩张，现如今产生一个搜索引擎跟过去的三年相比，是相当不同的。这篇文章将对我们大规模Web搜索引擎有一个深入的描述，首先就是对我们所知道的数据进行一个详细的公开描述。
  除了使用传统搜索引擎索引相当量大小的数据所存在的问题，这里还有更多其他的新技术挑战，这些新技术能实现使用存在于超链接文本中的附加信息来产生更好的搜索结果。这篇文章将向你解释如何来建立一个实际的大规模的系统，这个系统就将使用超链接文本中的附加信息。当然我们还可以看到如何有效处理那些不受控制的超链接文本所包含的文档这些问题，也就是任何人都可以发表他们想发表的任何事情。


关键字：World Wide Web, 搜索引擎，信息恢复，PageRank，Google

1、介绍
  为了信息恢复Web上出现了许对新的挑战。信息数量在Web上增长的速度相当快，就跟这个艺术性的Web搜索引擎里的没有经验的新用户一样。人们都非常喜欢用网上的链接图标在网上冲浪，经常都是从像Yahoo这种高质量的网站或者其他搜索引擎开始，而且人们都喜欢这样。人们喜欢的那些网站都能有效的涵盖了最流行的文章，但相对来说这样太主观了，因为这样的网站建立和维护都太昂贵，不太容易发展而且也不可能包括所有奥秘的文章。传统机械化的搜索引擎都是基于关键字匹配的，并且经常返回太多低质量的文章。让事情更糟糕的是，一些广告商经常会使用一些方法来误导机械化搜索引擎，以此来吸引群众的注意。我们已经完成了一个大规模搜索引擎，它能够解决阿现存系统中的许多问题。并且，它有效地利用了超链接文本这个附加的结构，以便为用户提供更多高质量的搜索结果。我们把这个系统的名字叫做Google，因为它与googol有相同的拼写，并且与我们要建立的大规模搜索引擎这个目标不相为谋。

1．1 Web搜索引擎――搜索阶段：1994年――2000年
  搜索引擎的技术有着引人注目的大规模的发展，并和Web的发展速度保持一致。在1994年，World Wide Web Worm（WWWW）是最早的搜索引擎中的一个，它能索引110000个网页和Web上能用的文档。同时在1997年的11月份，最好的搜索引擎宣称能索引2000000到10000000个Web上的文档。随后在2000年，普通的搜索引擎都能索引超过1000000000。同时，用搜索引擎发出请求查询的应用也有明显的扩增。在1994年的3月和4月，WWWW搜索引擎平均每天能收到1500次查询请求。在1997年的11月份，Altavista搜索引擎宣称平均每天能处理大约有2000000次查询请求。随着Web上用户的增加和查询搜索引擎系统的机械化，最好的搜索引擎预计在2000年的时候每天能完成成百上千万的查询。这个目标对于我们的体统带来的很多问题，同时利用搜索引擎的各种技术来完成相当大数量的索引将带来不仅质量还有性能上的许多问题。

1．2 Google:在Web上搜索
   创造一个大规模搜索引擎对于如今的Web仍然会有许多挑战。抓取Web上的文档并将它们保存到数据库，需要技术更加快速的向前发展。存储空间必需有效地利用来存储索引或者知识一些文档本身。索引系统必需能够有效地处理成一百多bit地数据量。查询请求也必需以每秒成百上千万地速度被处理完成。随着Web地发展，完成这些目标也越来越困难。然而，硬件的执行和耗时的显著提高也可以部分弥补这些困难。与此同时，对于这个工程还有许多显著的要求，像搜索时间和操作系统的强健性。在Google的设计中，我们不仅要考虑到Web发展的速度，还要考虑Web技术的改变。Google被设计成一种能很好的处理大量的数据的体统。它能有效的利用存储空间来存储索引。为了快速和更有效的利用，这种数据结构是非常完善的。不久以后，我们希望索引和存储文本或者HTML的耗时将有明显的减少。对于像Google这样重要的系统，这将会带来很多好处的。

1．3设计目标
1．3．1提高搜索质量
  我们主要的目标就是提高Web上搜索引擎的质量。在1994年，很多人认为一个完善的搜索引擎就是能很容易的查找到任何东西。对于1994年Web上最好的搜索引擎：Navigators，“最好的导航服务就是能方便的查找到Web上的任何东西（只要所有的数据都输入进去了）”。然而，1997年的Web却相当不同了。任何使用过搜索引擎的人都能很快的了解到完善的索引不是会影响搜索结果质量的唯一原因。“垃圾结果”几乎冲掉了所有用户感兴趣的结果。事实上在1997年的11月份，只有排名在前四位的一家商业搜索引擎才能找到它自己本身（用它自己的名字搜索，能在前10条结果中返回它自己）。导致这个问题的一个主要原因就是索引文件中许多文档已经增加了许多重要的排序，但是用户能看到这些文档的能力却没有提高。人们仍然希望在十条结果中的第一条看到自己要的结果。因此，随着收集起来的文档数量的增加，我们需要工具来高精度的完成搜索（在前十条结果中返回许多有关的文档）。事实上，我们希望我们所说的有关的只包括我们最需要的文档，尽管这里会有很多成千上百万只有微小关连的文档。这种高精度在重新查询中也是很重要的（系统能返回有关文档的总数量）。许多最近调研研究显示，超链接文本的使用能很好的提高搜索质量和其他方面的应用。特别是链接结构和链接文本对于相关联的预测和高质量的过滤都能提供很多信息。Google搜索引擎就利用了链接结构和锚文本。

2、 特征
  Google搜索引擎有两个很重要的特征，它们都能够帮助产生高精度的结果。首先，它利用了Web上的链接结构来计算每一个网页的质量级别，这种级别就叫做PageRank，第二，Google利用链接结构来提高搜索结果的质量。
2．1PageRank：给Web页面进行排序
  Web上引用的图标是一个很重要的资源。我们创建了地图map，它包含了51800000之多的这些超链接，这在所有的搜索引擎中是一个很好的样本。这些地图能快速的计算出Web页面的PageRank的大小，使得对页面被引用的重要性的估量能够很好的与人们主观需要的重要性相互协调。就是因为这种协调性，对基于关键字的Web搜索给出的答案做出最优的选择，PageRank是一个最好的选择。对于许多流行的事物，当PageRank使得结果优先时，一个简单的文本匹配搜索就将本Web网页上标题所限制。对于在主要Google搜索引擎中的整篇文章搜索这种类型，PageRank将会有很大的帮助。
2．1．1PageRank计算的描述
  纯理论的理论研究已经被引用到Web中来了，大量用于对一个给定的页面计算引用和返回链接。这将给出页面重要性和质量的一个估算。基于这个观点，PageRank不仅平等的从所有网页中计算出链接，并且能进一步计算出每一个网页上的链接。
   PageRank被定义如下：
我们假设页面A有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是通过Web网页计算出来的，所以整个Web上的网页的PageRank值加在一起会是1。
  PageRank和PR（A）能通过一个简单的反复的运算法则计算出来，并且也参照Web中规范型链接矩阵的主特征向量。当然，在一台中等规模的工作站上计算由2600000网页的PageRank，需要几个小时的时间。更详细的细节将会在其他章节介绍
2．1．2直观的方法
  我们可以把PageRank想成一个模型。我们假设这里有一个任意用户随即给定一个网页并且保持点击它上面的链接，但是不要点回退键或者在用户感到无聊了可以点击另一个随机页面开始。这个任意用户访问到某个网页的可能性就是PageRank值。而且，d这个限制性因素的值就是任意用户会感到无聊并访问其他页面的可能性。其中一个很重要的变化就是增加单个网页或者整组网页的限制性因素d的大小。这将更为人性化，并且为了得到更高的等级不可能故意去误导搜索系统。对于PageRank我们会有更多其他扩充，详细请看98页。
另外一个直观的方法就是如果一个网页有许多网页指向它或者有许多PageRank值大的网页指向它，那它就可以有更高的PageRank值。一般来说，如果一个网页能很好的被许多地方引用，那它就很值得看。当然如果一个网页只有一个引用,假设只引用了Yahoo！主页，那也是很值得看的。如果一个网页没有高的质量，或者其中的链接断掉了，那么就像Yahoo这样的网页没法链接过去。PageRank通过Web上的链接结构来处理不断网页中不断增加的许多事情。
2．2锚文本
  在搜索引擎中。链接文本是以一种很特殊的方式被处理。许多搜索引擎把链接上的文本和链接所在的网页联系起来。同时，我们会把链接指向的网页和它们也联系起来。这样将会带来许多好处。首先，锚文本通常都会提供它所指向的文本的精确描述。第二，锚文本存在于不能被以文本为基础的搜索引擎索引的文本中，比如图像、程序和数据库。这就使得那些不能被搜索引擎分析的网页也能被作为结果返回。记录这些不能被分析的文档可能会带来很多问题，因为它没有有效性的检查就将结果返回给了用户。对这种情况，搜索引擎可以返回一个不存在的网页，只是因为有一个超链接指向它。然而，由于要对结果进行排序，这种特殊情况发生的可能性比较小。在网页中使用锚文本这个想法最早是在WWWW搜索引擎中实现的，特别是它可以帮助搜索非文本信息，并且可以扩展到一些可以下载的文档。我们使用锚文本最主要还是因为锚文本可以帮助提供更好质量的结果。使用锚文本在技术上有相当大的难度，因为它要处理的数据量相当大。对于现在搜索2400000网页，我们可以索引到超过25900000个锚文本。
2．3其他特征
  除了PageRank和锚文本的使用，Google还有许多其他特征。首先，它记录所有点击发生的位置信息，所以它能够完成广泛的近似搜索。第二，Google还记录网页上像字体大小等视觉信息。大号字体和粗字体比其他字都有更高的权重。第三，在Repository中能够存储所有原始的HTML页面。

4、 系统剖析
  首先，我们会给出对Google系统的深入讨论。接着，这里会有一些对重要数据结构的深入描述。最后，将深入介绍Google最主要的应用。
4．1 Google结构概述
  在这一章节，我们会对整个系统如何工作给出一个深入概述，如图1所示。接下来的章节将讨论这一章节没有介绍的具体应用和一些数据结构。为了执行效率，Google大部分都是用C或C＋＋来完成的，并且可以同时在Solaris和Linux上运行。
  在Google体系结构中，Web上的网页抓取（Web网页的下载）是由许多分散的网络爬虫来完成的。这里有一个URLserver服务器会发送获取到的URL列表给网络爬虫。接着获取到的Web网页会发送到存储服务器上。存储服务器就会将Web网页压缩并存储到Repository容器里。每一个Web网页都有一个与自己相关联的ID号，叫做docID。当每一个新的URL从网页中解析出来就能分配到一个docID。索引功能是由索引器和排序器来完成的。索引器扮演者数据功能。它从Repository容器中读取出文档并压缩文档，最后再对文档进行解析。每个文档都将转换成一系列单词时间，即命中。命中会记录单词再文档中出现的位置和单词的大小写。索引器把这些命中分布到一系列的“桶“中，并产生一个部分排序的前序索引。索引器还扮演着另一个重要的功能。它解析每个网页上所有的链接，并将关于它们的所有重要信息存储在锚文件中。这个文件保存了足够的信息，这些信息能够决定每个链接来自哪里以及指向哪里，还有这个链接所在的文档。
  URLserver服务器读取锚文件，并将里面的绝对URL转换成相对URL，接着转换成docID。通过docID的关联，锚文本的信息也被加入到前序索引中。它同时创建了一个包含一对docID的链接数据库。这个链接数据库通常是用来计算所有文档的PageRank值。
排序器是用来管理这些“桶“的，“桶”都是根据docID进行排序的，并且根据docID反向索引。这些操作都是在“桶”中完成的，所以完成这个操作只需要很少的临时空间。排序器会产生一个wordID列表，用来弥补方向索引。有一个叫做DumpLexicon的工具，它用来把这些列表和由索引器产生的字典结合起来，并产生一个新的字典提供给搜索器使用。搜索器是由Web服务器来运行的，使用由DumpLexicon产生的字典与反向索引和PageRank结合起来回答查询请求


  就这么些了，由于字数只要求这么些。后面的我心情好了再给补充完吧。

  原文出处：The Anatomy of a Large-Scale Hypertextual Web Search Engine

评论

1 楼 playfish 2008-04-07  

虽然翻译出来的文字还不够专业，但是读完还是很有收获的。刚好最近也在做一个模拟的爬虫模型，（毕业设计），期待楼主的完整版本。。。。