Google搜索引擎的工作原理
文章来源:台球桌
谷歌呈现给我们一幅由Jess Bachman(在WallStats.com工作)精心描绘的示意图,这张流程图展示了每天拥有3亿次点击量的Google搜索按钮背后搜索引擎在那不到1秒的响应时间内所进行的处理。在你点击Google搜索按钮后,在Google返回查询结果前那一眨眼的功夫里,Google是如何处理你的搜索请求的?这可是搜索巨人Google年赢利额高达200亿美元的杀手级应用,也是Internet首屈一指的商业和技术神话,大家肯定都想知道Google这棵摇钱树背后的秘密。
一、Google官方对其搜索技术的叙述
我们搜索技术的后端软件会在服务器侧触发一系列执行时间不到1秒的并行计算,Google问世前的传统搜索引擎的搜索结果严重依赖于关键词在页面上出现的频度,我们使用了200多个指标信号(其中包括我们拥有专利的PageRank页面等级加权算法)用来检查万维网的链接结构(佩奇和布林最初的想法是把万维网的链接结构用图论的有向无环图来建模)并决定网页的重要程度,我们假定一个网页的重要程度取决于别的页面对它的引用,就像学术论文中的引用指数一样,重要的论文总是会被很多其他论文引用。然后我们再根据搜索条件进行超文本匹配分析(对bot抓取的页面内容进行关键词倒排索引检索)确定跟搜索请求最相关的网页。综合最重要的网页和跟搜索请求最相关的网页两个方面,我们就能按重要程度和用户搜索请求相关程度把查询结果排序后呈现给我们的用户。
二、数据中心:Google用来索引世界的塔
Google的数据中心高度机密,我们能了解到的不多:
1. 在美国本土有19个以上的数据中心,其余17个数据中心分布在美国以外的世界各地。
2. 每个数据中心有50万平方英尺那么大,建造一个数据中心要花费约6亿美元。
3. Google数据中心是世界上最高效的设施之一,而且也非常环保,几乎没有
碳排放。
4. 数据中心使用50到100兆瓦的电力,由于需要冷却,通常建在便于用水的地方。
5. Google服务器安置在一个一组容得下1160台服务器的有房子那么大的标准集装箱容器中。
三、处理流程:
1. 你写博客、或在Twitter上推微博、更新站点等诸如此类往web上添加内容的操作
2. Google爬虫(一种作为搜索引擎构件的智能代理程序)抓取你网页的title和description、keyword等内容
(1) Google bots程序沿链接路径周游万维网,如果没有http路径到你的站点,你的站点将不会被索引
(2) 如果你在robots.txt中设置不许索引,Google bots程序将不会抓取你的网页
(3) 如果链接到你站点的html链接上有nofollow标签,Google bots将不会从这些链接路径周游到你的站点。
(4) Google也能通过blog软件或xml站点地图找到你的网站
(5) 从PageRank越高的网站链接到你的网站的链接越多,你的网站的PageRank就越高。
(6) Google爬虫将周游所有未标注为nofollow的链接
3. 一旦被Google爬虫访问到,网页几秒内就被索引了
(1) 网页内容被存储在一个倒排索引中
① 网页标题和链接数据被保存在一个索引中,用于广度优先搜索
② 网页内容保存在另一个索引中,以用于检索频率不高的长尾、个性化、深度优先搜索
(2) 当你用Google搜索时,你并没有在检索时时更新的万维网,而是在检索Google的缓存,Google定期更新其索引库,在Twitter实时搜索等的竞争下,Google的索引库更新周期趋短。
4. Google基于链接评估域名和网页的总体PageRank值。
5. 检查网页以防止作弊行为
(1) Google的搜索质量和反垃圾信息审查和优化算法
(2) 1万多远程测试用户评价搜索结果的质量
(3) Google征请用户对有PageRank讹诈嫌疑的垃圾信息进行举报
(4) Google接到 (美国)数字千年版权法案的通知,要求Google把盗版行为记录备案
6. 在对页面做了损害分析后,现在每个页面都有很多用于辅助用户搜索的数据片(比如检索关键词)反向引用着它
7. 用户发出搜索请求
(1)Google搜索质量工程师Patrick Riley:在大多数Google搜索中,你的搜索处于许多并行的控制过程或Google实验室的创新项目组过程中,可以说每一个查询请求都会参与一些Google的创意实验。
8. Google会用同义词匹配与你的搜索关键词语义相近的查询结果
9. 生成初步的查询结果
(1) 也许Google宣言能返回成千上万数量无限的查询结果,但一般只显示不到1000条的查询结果,出于“少则得,多则惑”的考虑。
(2) 对查询结果做本地化处理,本土站点在查询结果中优先出现
10. 对查询结果集按权威性和PageRank进行排序,重复的查询结果被剔除。
(1) Google根据关键词、广告类型、用户所处位置找出相关的被竞价拍卖的关键词广告
(2) 关键词广告必须遵守当地法律条文
① 广告业主的非法广告将被取缔
② 如果关键词的搜索流量过低或关键词广告点击量偏低,则会被自动禁用 ③ 出于商业策略,像亚马逊这样的客户会给予优惠折扣。
(3) 关键词相关广告按收益潜力(对关键词进行竞价拍卖后的广告质量不断进行评估)排序
(4) 对广告业主来说广告内容一般都是固定的,但有时使用动态关键词使关键词广告与搜索关键词相关度更高
①一些广告本身允许增加易变的附属信息,比如网站链接、电话号码、产品链接、地址等
(5) 当广告拥有了相当高的点击率,则会显示在搜索结果列表的上方,以使其更显眼。
(6) 其余的广告依序显示在相应的位置
11. 对查询结果进行过滤处理
(1) 对通常的查询(比如在Google首页上发出的搜索请求),Google会把相关的专题性垂直搜索结果(比如新闻、购物、视频、书籍、地图等)也加到返回的查询结果中
(2) 个性化方面:用户访问过的网站在查询结果列表中会更靠上
(3) 大量使用锚点的网站有可能被从查询结果中删除
(4) 搜索结果集的聚簇性:如果网页被其他高PageRank的网站引用,则网页的重要性会大大提高。
(5) 趋势分析:对搜索流量爆增或有大量新闻的搜索关键词,Google会在新的查询结果中增加额外的PageRank权值。(Google有反映关键词搜索流量的Google趋势专题页面)
(6) 同一个域名下的多个网页如果具有相同的PageRank会被归为一组。
12. 最终返回给浏览器端的用户一个人性化的、布局良好的、查询结果和广告泾渭分明的有机查询结果页面。
第二篇:Google搜索引擎工作原理简介
文章是基于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
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的整体系统结构如图所示:
先由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)。
正向索引:
正向索引由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.转换关键字为wordIDs3.在短桶short barrels中寻找每个关键字在doclist的起点4.扫描这个doclists直到有个网页与查询全部匹配5.计算这个网页的查询排名Rank6.如果在短桶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相结合得到最终的搜索排序结果。(编选:中国电子商务研究中心)
本文转载自中国电子商务研究中心:/detail--5129356.html