The Anatomy of a Large-Scale Hypertextual Web

wangfans

4.4网站索引

解析——任何被设计来解析整个互联网的解析器都必须处理大量可能的错误。从HTML标签里面的错别字到一个标签里面上千字节的0，非ASCII字符，嵌套了几百层的HTML标签，还有大量超乎人想象的错误和“创意”。为了达到最快的速度，我们没有使用YACC产生CFG（context free gramma，上下文无关文法）解析器，而是用flex配合它自己的栈生成了一个词法分析器。开发这样一个解析器需要大量的工作才能保证它的速度和健壮。

wangfans

为文档建立桶索引——每一个文档解析过后，编码存入桶里面。每一个单词被内存里的哈希表——词典转化成一个wordID。词典哈希表新加的内容都被记录在一个文件里。单词在被转化成我wordID的时候，他们在当前文档中的出现会被翻译成命中列表，并写入正排桶(forward barrels)中。建立索引阶段的并行操作主要的困难在于词典需要共享。我们并没有共享整个词典，而是在内存里保存一份基本词典，固定的1千4百万个单词，多余的词写入一个日志文件。这样，多个索引器就可以同时运行，最后由一个索引器来处理这个记录着多余单词的小日志文件。

wangfans

排序——为了产生倒排索引，排序器取出各个正排的桶，然后根据wordID排序来产生一个标题和锚命中的倒排桶，和一个全文的倒排桶。每次处理一个桶，所以需要的暂存空间很少。而且，我们简单地通过用尽可能多的机器运行多个排序器做到排序的并行化，不同的排序器可以同时处理不同的桶。因为桶并不能全部放在主存里面，排序器会根据wordID和docID将它们进一步分割成可以放在内存里面的桶(basket)。接着，排序器将每个桶载入内存，排好序，把内容写入短的倒排桶和完整的倒排桶。

wangfans

排序——为了产生倒排索引，排序器取出各个正排的桶，然后根据wordID排序来产生一个标题和锚命中的倒排桶，和一个全文的倒排桶。每次处理一个桶，所以需要的暂存空间很少。而且，我们简单地通过用尽可能多的机器运行多个排序器做到排序的并行化，不同的排序器可以同时处理不同的桶。因为桶并不能全部放在主存里面，排序器会根据wordID和docID将它们进一步分割成可以放在内存里面的桶(basket)。接着，排序器将每个桶载入内存，排好序，把内容写入短的倒排桶和完整的倒排桶。

wangfans

排序——为了产生倒排索引，排序器取出各个正排的桶，然后根据wordID排序来产生一个标题和锚命中的倒排桶，和一个全文的倒排桶。每次处理一个桶，所以需要的暂存空间很少。而且，我们简单地通过用尽可能多的机器运行多个排序器做到排序的并行化，不同的排序器可以同时处理不同的桶。因为桶并不能全部放在主存里面，排序器会根据wordID和docID将它们进一步分割成可以放在内存里面的桶(basket)。接着，排序器将每个桶载入内存，排好序，把内容写入短的倒排桶和完整的倒排桶。

wangfans

4.5搜索

搜索的目标是高效地返回高质量的结果。很多大型的商业搜索引擎在效率方面看起来都有很大的进步。所以我们更专注于搜索结果的质量，但是我们相信我们的解决方案只要花一点精力就可以很好的应用到商业的数据上。Google的查询评估流程如图4。

wangfans

为了限制响应时间，一旦某个数量(现在是40,000)的匹配文档被找到，搜索器自动跳到图4中的第8步。这意味着有可能返回次优的结果。我们现在在研究新的方法来解决这个问题。在过去，我们根据PageRank值排序，有较好的效果。

wangfans

1.解析查询（Query）。
2.把单词转化成wordID。
3.从每个单词的短桶文档列表开始查找。
4.扫描文档列表直到有一个文档匹配了所有的搜索词语。
5.计算这个文档对应于查询的评分。
6.如果我们到达短桶的文档列表结尾，从每个单词的全桶(full barrel)文档列表开始查找，跳到第4步。
7.如果我们没有到达任何文档列表的结尾，跳到第4步。
8.根据评分对匹配的文档排序，然后返回评分最高的k个。

wangfans

4.5.1评分系统
Google比典型的搜索引擎维护了根多的web文档的信息。每一个命中列表（hitlist）包含了位置，字体和大小写信息。而且，我们综合考虑了超链接文本命中和页面的PageRank值。把所有的信息综合成一个评分是很困难的。我们设计了评分函数保证没有一个因素有太大的影响。首先，考虑简单的情况——一个单词的查询。为了对一个单词的查询计算文档的分值，Google首先为这个单词查看这个文档的命中列表。

wangfans

Google将命中分为不同类型（标题，锚，URL，普通文本大字体，普通文本小字体，……），每一种类型都有自己的类型权重值（type-weight）。类型权重值构成一个由类型寻址（indexed）的向量。Google数出命中列表中每种类型命中的数量。每个数量转化成一个数量权重（count-weight）。数量权重开始随着数量线性增长，但是很快停止增长，以保证单词命中数多于某个数量之后对权重不再有影响。我们通过数量权重向量和类型权重向量的点乘为一个文档算出一个IR分数。最后这个IR分数与PageRank综合产生这个文档最终的评分。