搜索和网页排名的数学原理

一、布尔代数和搜索引擎

搜索引擎是每天都在使用的一种工具，它是一门非常复杂的技术，实现一个搜索引擎并非易事。但是，技术是分为术和道两种的，具体的做事方法是术，做事的原理和原则是道。

不谈搜索引擎的术，但可以说说它的道。

搜索引擎的原理相对于它在技术上的实现，就非常简单了。建立一个搜索引擎大致需要做这几件事：自动下载尽可能多的网页；建立快速有效的索引；根据相关性对网页进行公平准确的排序。

1、布尔代数

布尔代数起源于二进制。中国的阴阳学说是二进制的雏形，而二进制作为一个计数系统，是在公元前2-5世纪由印度学者完成的。17世纪，莱布尼兹完善了二进制计数系统，并用0和1表示它的两个数字，成为我们今天使用的二进制。1854年，布尔（英国19世纪的一名中学数学教师）的《思维规律》一书向向人们展示了如何用数学的方法解决逻辑问题。

布尔代数运算的元素只有两个：1（true,真）和0（false,假），基本运算规则有与（and）、或（or）、非（not)三种。那么布尔代数和搜索有什么关系吗？

无论是Google还是百度，其搜索的基本原理都是基于布尔代数的。假设搜索一篇关于原子能应用的文献，但并不像知道如何造原子弹。对于用户输入的每个人关键字，搜素引擎要判断文献中是否包含这个关键字，若有，则给此篇文献一个逻辑值—真(1或true），反之给一个逻辑值假—（0或false），对应的查询语句就变成了“原子能and应用and(not 原子弹)”，则搜索结果中符合要求的文献必须同时满足这三个要求。根据布尔代数的运算规则，每一篇文献对于这三个条件都有一个true或者false的答案，根据这个答案就能算出文献是否是满足要求的。

2、索引

搜索引擎可以根据布尔代数去寻找需要的结果，但是，它是怎么在零点零几秒的时间内找到成千上万的搜索结果的？显然，如果是扫描文本，计算机扫描速度再快也不能做到。这就需要建立索引了。

Google曾经有一道面试PM的考题：如何向你的奶奶解释搜索引擎？如果从技术层面回答，基本被pass。好的回答是拿图书馆的索引卡片类比。每个网站就如图书馆的一本书，网页就是书本的某一页的内容，我们可以利用索引卡片或者页码迅速找到需要的书本或者书本某一页的信息。

一个简单的索引结构是用一个很长的二进制数表示某个关键字是否出现在每篇文献中，有多少篇文献，就有多少位数，每一位对应一篇文献，1代表有对应的关键字，0代表没有。对于关键字”原子能“，其可能的二进制表示是0100100011000001…..，”应用”可能对应的二进制表示是0010100110000001…，对二者进行布尔运算AND。结果是0000100000000001…，表示第五篇和第十六篇满足要求。计算机做布尔运算是非常快的，现在最便宜的微机在一个指令周期内做32位布尔运算，一秒钟可以进行数十亿次以上。

二、网页排名技术

对于不部分查询，搜素引擎都会返回成千上万条结果，那么应该如何排序，把用户最想看到的结果排在前面呢？这个问题很大程度上取决于搜索引擎的质量。对于一个特定的查询，搜索结果的排名取决于两组信息：网页质量和这个查询与每个网页的相关信息性。

  1、网页质量：PageRank

PR的数学模型是Google的创始人拉里佩奇和谢尔盖布林发明的。在互联网上，如果一个网页被很多其它网页所链接，说明它收到普遍的承认和信赖，那么它的排名就高。这是PR的核心思想。友情链接的交换就很好的说明了这一点。对于不同网页的链接，PR是区别对待的：即网页排名高的网站贡献的链接权重大。那么网页权重怎么计算的呢？

有x1、x2、x3、x4四个网页只想网页Y，四个网页对应的权重分别是0.001、0.01、0.02、0.05，则网页Y的PR=0.001+0.01+0.02+0.05=0.081。PR算法的计算就是线性代数中矩阵相乘。

2、网页和查询的相关性

度量网页和查询的相关性，一个简单的方法就是用关键词在网页中出现的总词频。例如，一个查询中包含N个关键字w1,w2,w3…，他们在一个特定网页中出现的词频分别是TF1,TF2,TF3…，（TF：Term Frequency的缩写）那么，查询和这个网页的相关性就是

TF1+TF2+TF3+…

但是对于对确定网页主题没有用处的词，称之为停止词，如的、是、中、地等，其权重为0。所以在信息检索中，使用最多的权重是”逆文本频率指数”（Inverse Document Frequency,缩写为IDF），数学公式是log(D/Dw)(w是下标)，D表示全部的网页数。假设中文网页数D=10亿，停止词‘的”在所有网页中出现，其出现的次数Dw=10亿，那么它的IDF=log(10亿/10亿)=log(1)=0。“原子能”在200万个网页中出现，即Dw=200万，所以它的权重IDF=log(500)=8.96,”应用“在5亿个网页中出现，则它的IDF=log(2)=1。利用IDF，相关行的计算公式就由词频的简单求和变成了加权求和，即：

TF1*IDF1+TF2*IDF2+TF3*IDF3+…

利用这种方式计算出来的权重比例分配就很客观了，准确的估算关键字和网页之间的相关性了。

参考书籍：《数学之美》

原文首发：http://www.ido321.com/1338.html

下一篇：DOM笔记（八）：JavaScript执行环境和垃圾收集