谷歌搜索引擎产品的工作原理研究

　　1 下载--构建网络爬虫

　　1.1 图遍历算法的取舍

　　从理论上讲，广度优先搜索（BFS）和深度优先搜索（DFS）算法的时间复杂度都是 O（n + e），不同的算法爬下整个静态网页的内容所用的时间是相同的。但在现实生活中，时间有限，互联网时刻变化。所以应该考虑有限时间里尽可能多的爬下最重要的网页，一个网站中最重要的网页应该是它的首页以及首页所连接的页面，BFS 明显优于 DFS.但实际的网络爬虫都是由很多服务器组成的分布式系统，这些下载服务器和网络服务器建立通信需要额外时间，这时就需要用到 DFS 以避免握手次数过多。

　　1.2 提取URL并做出URL表

　　有些页面的 URL 以文本形式存储在页面中，有明显标识；而有些时候需要模拟浏览器运行才可以提取到页面中隐含的 URL.但在互联网这张大图上，一个页面可能被多个页面所指向，遍历时，为了防止一个网页被重复下载，这时就需要一个哈希表做记录，即遇到一个网页，首先查找判断 URL 是否在表中，若存在直接跳过，若不存在，下载页面并将这个页面的 URL 存入哈希表中。但是如果同时有上千台服务器一起下载网页，为了避免不同服务器重复判断一个 URL,要注意存储哈希表的服务器的通信问题。第一，调度系统要明确每台下载服务器的分工，减少 URL 的重复判断次数；第二，尽可能使用批处理，每次向哈希表发送一批询问和更新一批内容，减少通信次数。

　　2 索引--布尔代数

　　索引是基于数据库的，数据库的 SQL 查询背后的基本原理是布尔运算，支持各种复杂的逻辑组合，而今天的搜索引擎即是把用户输入的自然语言查询转换成布尔代数。最简单的索引结构就是一串很长的二进制数，这个数的位数代表有多少网页，每一位对应一个页面，1 代表这个页面中有这个关键字，0 代表没有。比如查询“宠物沐浴液”,关键字“宠物”对应的二进制数是 100011010000000…，表示第一、第五、第六、第八个页面包含这个关键字；关键字“沐浴液”对应的二进制数是011010010000000…，要筛选出同时包含“宠物”和“沐浴液”网页时，只需将这两个数进行布尔运算 AND,结果为 000010010000000…，可知第五、第八个页面满足要求。综上，互联网搜索引擎的索引是一张大表，每一行是一串二进制数字，表示包含某个关键词的页面序号。

　　3 排序--网页质量的度量

　　PageRank 的核心思想：一个页面用户访问的越多质量越高，而用户在浏览网页时主要通过超链接进行页面跳转，因此我们需要通过分析超链接组成的拓扑结构来推算网页被访问的频率。其中，指向这个网页的其他页面本身也有一个自己的权重。一个网页的 PageRank值应该来源于所有指向这个网页的其他页（X1,X2,…，.Xk）的权重（Y1,Y2,…，.Yk）之和，即

　　对矩阵 A 按行切分 10 份，对矩阵 B 按列切分 10 份。每个结果的计算量都是最后结果的十分之一，用 10 倍的空间复杂度缩短 10 倍的时间复杂度。MapReduce 即是把一个大任务分成多个子任务，分布到不同的计算机中计算，最后再将中间结果合并成最终结果。

　　4 结语

　　在搜索引擎中，给定一个特定查询，有关网页的排名大致由相关性和网页本身质量所确定。但是任何搜索产品给出的结果都不完美，排名靠前的不一定是高质量的，而是商业气息很浓的。针对 PageRank 算法会出现很多卖链接的网站，解决办法主要用到余弦定理和图论中的 Clicque 算法。即便是有好的算法来衡量网页质量和查询相关性，但搜索反作弊仍旧是一个长期的任务，需要不断的消除“噪音”,才能提高搜索引擎的质量。