这篇文章是基于Google创始人Lawrence Page和Sergey Brin一篇早期的论文翻译整理简化而成。尽管Google一直在修正不同因素对网页的权重影响以期排除作弊网站对搜索结果的干扰和获得最好的搜索结果，但其核心思路并没有改。

Google采用了两个重要的特性，因此而获取了准确的查询结果：第一，Google利用网页的链接结构计算出每个网页的等级排名，这就是所谓的PageRank；第二，Google利用了链接提供的信息进一步改善搜索结果。

PageRank的计算：

PageRank的基本思路是：如果一个网也被其他网页多次指向，这就说明本网页比较重要或者质量较高。除了考虑网页链接数量之外，Google还要参考链接网页本身的级别， 以及这个网页有多少正向链接到其它网页。当然“重要”的网页的链接就会有更高的权重。 PageRank的简化计算公式：

PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))
• PR(A) :网页A页的PageRank值；
• PR(Ti) :链接到A页的网页Ti的PageRank值；
• C(Ti) :网页Ti的出站链接数量；
• d :阻尼系数，0<d<1， 通常设为0.85

PageRank可以通过结合链接权重的向量矩阵的提归计算而获得（关于PageRank的深入分析，我在方便的时候会另外写一篇文章介绍）。

随机冲浪模型：

PageRank可以被理解为用户的一个行为模型。我们假设一个随机的网站浏览者”random surfer”给以一个随机的网页，他会继续点击网页中的链接直到他厌倦了而从新开始浏览一个新的随机的网页。PageRank可以理解为某个网页被随机访问的概率。而阻尼系数d则是随机访客不顺着网页的链接继续浏览下去，而从新开始一个随机冲浪的概率。对有一些网页，可能会人为的改变它的阻尼系数， 这样就可以阻止一些作弊网站误导Google而获得较高的PageRank的可能性。

你也可以这样自觉理解PageRank：一个高PageRank的网页是那些有很多网页指向的网页，或者是有一些重要网页指向的网页。Google假定，如果一个网页被很多其他不同的网页引用，就说明这个网也值得一看。另外，如果一个网页为yahoo这样的网站指向，也通常值得一看。

链接描述文本（anchor text）

Google对连接描述文字进行了特殊的处理。大多数的搜索引擎都是把链接文本和它所在的页面相关联，而Google还把链接文本和它指向的文档相关联。这样做的原因是链接描述往往提供了一个对被指向的网页更准确地描述。

除了PageRank和链接描述以外，Google还采用了一些其它的特性：首先，Google记录了所有关键字的位置信息（hits），它在搜索中充分的使用了关键字的相关性分析。其次，Google记录了一些视觉信息，比如字体的大小等等。大字以及加粗的字体比网页中的其它字体有更高的权重。

另外，Google认为，不是直接呈现给访问者的的文本信息都可能被烂用， 并用以误导搜索引擎。所以Google对metadata的文本给以较小的重视。

系统结构分析：

Google的整体系统结构如图所示：Google-Architecture-Overview

先由URLserver发送一系列的URL地址让网站爬虫crawlers去采集。网页采集后交给存储服务器Store server。存储服务器压缩网页内容后存放到信息仓库repository。所有的新的网页都被赋予一个docID。 索引功能由索引器indexer 和排序器sorter来执行完成。Indexer读取repository的文件，并将其转换为一系列的关键字排序，称为命中hits。Hits记录了关键字，出现在文件的位置，字体的相对大小和字母的大小写。Indexer然后将这些hits放到一系列的桶barrels中，建立了部分排序的好了的正向索引。Indexer还分离出网页中的所有链接，将重要的信息存放在Anchors文件之中。这个文件包含的信息可以确定链接的指向和链接的描述文本。

URLresolver读取Anchors文件并将相对URLs转换为绝对URLs，并依次放到docIDs中。它再将链接的描述文本放到正向索引，并将docIDs与链接的描述文本相对应。同时，它也产生一个链接links和docIDs相对应的数据库。这个links数据库将被用于计算所有网页的PageRanks。

然后，排序器sorter从barrels中取得按docID排序的网页，再将其按照wordID产生一个反向索引。Sorter还在反向索引产生一个wordIDs及其偏移的列表。一个叫做DumpLexicon的程序将这个列表结合搜索引擎的词库再产生一个可以被搜索器searcher使用的新的词库Lexicon。由网页服务器构成的搜索引擎Searcher利用这个新的词库配合反向索引和PageRanks来回答查询。

命中列表Hit Lists

命种列表Hit Lists记录了一系列的关键字出现在一个网页中的信息，包括在网页中的位置，字体的相对大小和字母的大小写。Hit Lists占用了正向和反向索引里的绝大部分的空间。

命中分为两类：特别命中fancy hits 和普通命中plain hits。fancy hits包括了在URL, 标题, anchor text, or meta tag出现的关键字， 所有在其它位置出现的关键字均为plain hits。一个plain hit由大小写位1 bit， 字体大小3bits和用来表示关键字在网页的位置所组成12位bits信息(所有位置大于4095的均表志为4096)。Forward-Reverse-Indexes

正向索引：

正向索引由64个桶barrel组成。每个barrel存放了一个特定范围的wordID’s。如果一个网页包含的关键字属于某个barrel范围，这个docID就记录到这个特定的barrel之中。docID与wordID’s以及这些关键字的命中列表hit lists一起记录在这个barrel中。

反向索引

反向索引与正向使用相同的barrels， 唯一的区别是反向索引由排序器sorter处理。对每一个有效的wordID， 词库lexicon中包含了指针指向具体的barrel。 它指向由docID组成的doclist列表，以及他们的所对应的命中列表hit lists。这个doclist代表了那个单词在所有文件中所出现的列表。

Google采用了两组反向索引inverted barrels。 一组包含了标题和anchor hits，另一组则包含所有的hits。 这样，google先检查第一组short barrels， 如果返回的匹配结果不够多，然后再查询第二组long barrels

Google查询流程如下：

1. 解析查询关键字
2. 转换关键字为wordIDs
3. 在短桶short barrels中寻找每个关键字在doclist的起点
4. 扫描这个doclists直到有个网页与查询全部匹配
5. 计算这个网页的查询排名Rank
6. 如果在短桶short barrels doclist列表已经查完，寻找每个关键字在长桶long barrels doclist的起点，重复第4步
7. 如果还没有查完doclist，重复第4步
8. 将匹配的网页根据计算出的rank排序，并返回前k个查询结果。

Google的排名系统

Google包含了比其它搜索引擎更多的网页信息。每一个hit list包含了位置，字体，大小写信息。另为Google还参考了anchor text以及网页的PageRank。 没有一个单一的因素会对搜索结果的排序产生太大的影响。

让我们来看一下单个关键字的查询：Google先查看对应于这个单词的网页的命中列表hit list。Google区分每个hit由几种不同的类型 （标题, anchor, URL, 大字体, 小字体等等）, 每一种类型都有自己的类型权重type-weight。 这些type-weights 组成一个由类型向量。 Google计算每一种类型的命中记数，然后这些命中记数又转换为计数权重Count-weights。计数权重开始以线性增加，然后很快就逐渐停止，这样太多的命中记数就会没有作用。Google在将Count-weights和type-weight相乘计算出网页的IR score。 最后这个IR score与PageRank相结合得到最终的搜索排序结果。

对于多关键词的搜索，计算方法就比较复杂一些。现在多个命中列表必须要全部扫描，这样对那些出现在文章中靠近的hits就比那些分开较远的hits有更高的权重。 那些相接近的hits被匹配到一起，然后计算出这些相匹配的hits的相关度proximity。相关度是基于这些hits出现在文章中的距离决定的，并被分为10个不同的值，分别表示为短语匹配（phrase match)到根本不匹配（not even close)。命中计数不仅计算每种类型，而且还计算每个类型和他们的相关度匹配。 每个类型和相关度配对有一个type-prox-weight权重。这个记数器被转换为计数权重。然后这个计数权重于与类型相关权重type-prox-weights相乘得到文章的IR score。当然最后是IR score与PageRank相结合得到最终的搜索排序结果。

最后的话

整理这篇文章的目的是为了让自己更好地了解Google搜索引擎，同时也希望能够帮助大家对Google的工作原理有一个大致的了解。如果你看了我的文章还是不太明白，英文原文可以在这里找到。 http://infolab.stanford.edu/~backrub/google.html。

转载请注明：转载自蒋海明的网络创业营销博客http://www.jianghaiming.com

7 Comments »