你在这里

浅谈Google的搜索引擎与奇妙的信息指纹-读《数学之美》有感

数学之美,成长吧啊,www.czbaa.com,数学

阅读《数学之美》

所有的搜索引擎,包括Google搜索引擎,由三部分组成,分别是下载、索引和排序。下载是把世界上所有网页都下载下来,当你搜索关键词的时候,他只需要把你搜集到的含有关键词的网页提取出来而不用先下载再提取。索引指建立快速有效的索引。我们知道,网页数量是难以想象的巨大,比如说在1千亿个网页中,搜索一个关键字“电子商务”,我们可能得花费好几十天的时间,所以我们必须建立快速有效的索引。显而易见,这个过程就类似图书馆找书。至于排序,还是上面的例子,如果我们找到100个关于电子商务的网页,我们有可能把每个网页都浏览到;但通常的搜索得到的是100“页”甚至还更多“页”的网页,我们会看到第1页、第二页……但我们不可能读完100页,能读到第10页就已经相当不错了。因此排序至关重要。

这三部分都是由简单的数学原理作为支撑的。

先说下载:整个互联网可以用“图”来表示,结点代表“网页”、“网站”,弧代表“链接”。比如河北工业大学,你点开网页,还会有很多别的链接,如管理学院、计算机学院……,你点开管理学院,会有各个系,如信管系、电子商务系……。也就是说互联网有很多层次。Google搜索引擎的下载部分应用了数学中“图论”的知识。利用图论的算法,如深度优先遍历、广度优先遍历等,自动访问并下载每一个网页。

再说存储问题:下载完之后如何存储呢?需要解决两个问题,一是如何存储才能在下载前知道当前网址信息已存不需要下载?举个简单例子,比如你下载了河北工业大学网址,但管理学院网址有可能链接回河北工业大学,这个时候第二次碰到河北工业大学,就不应重复下载了。二是以什么形式存储才能缩小规模?比如河北工业大学这一网址算是短的;但是我们知道,网址越靠下级,字符串就越长。将网址字符串存为数字,计算机很容易实现。但是有100个字符串,影射为100个数字,那么平均下来,全世界的数据,需要2000多个服务器,规模非常之大。也就是说光是存网址就需要2000台服务器。换言之:在搜索的时候,我们必须从2000台服务器中去找需要的东西。这个太复杂了!速度上太慢。如此,必须缩小存储规模。一个办法是对网页进行编码。比如说河北工业大学,可以编码为300401。但是问题是,它无法解决上述第一个问题。也就是在下载网址之前,不能够预先知道该网站是否已经下载过。我们必须有一个方法使网址自动对应一个数。有人说,将河北工业大学对应为“hebut”,这也有新的问题—重名,这种方法的重名概率非常大。人们发明了一个信息指纹的方法,它完美的解决了上述两个问题。其做法可以简单描述为:我们先把河北工业大学转化成数字,多长的数字都没关系,比如说转化为100位数,怎么把它转化为信息指纹呢?用伪随机数产生器。其做法就是将一个数做“×”、“÷”、取整等运算,产生一个数,这个数就是指纹。

最早的伪随机数生成器算法是由冯•诺依曼(计算机之父)提出来的,它的方法非常简单,将一个数的平方掐头去尾取中间。比如371^2=137641,去掉头尾为3764.我们用3764代替河北工业大学,下次在遇到河北工业大学,它的编码方式是固定的,依旧为3746,从数据库上查找是否已存3764,如果没有,就继续下载。大家肯定想,很可能有两个不同网址的信息指纹是一样的。当然,Google采用的不是冯的方法,因为该方法还是有一定的重合概率,并不是很随机。然而数学上完全可以证明:伪随机数产生器产生的伪随机数出现重复的概率非常小,并且对伪随机数直接作加减乘除等运算得到的结果出现重复的概率也是非常小的。信息指纹简单粗暴的解决了网址重名的问题。

现实中我们很多时候要比较集合是不是一样,所谓一样,就是所包括的元素是否一样。如何比较{“北京”、“中关村”、“地铁”}与{ “中关村”、“北京”、“地铁”} 是否一样?

如何比较?最直接的办法就是对这个集合的元素一一做比较,这个方法计算的时间复杂度非常高的;稍微好一些的办法是将两个集合的元素分别排序,然后顺序比较,但还不是很好。实际上是每个词都有它的信息指纹—--数字,只需要将这些数相加,只要相加的和相等,那这两个集合就一样,简单吧!不管是加减乘除如何运算,伪随机数重复的概率都非常小。如果是数学的话,数加和的概念,在古埃及的时代也有类似应用。比如说抄写,我写了一本书,当时没有打印机,只能人工抄写,抄写第一遍错两个字,十遍之后可能文章就面目全非了,所以就必须要检验。怎样校验呢?

犹太人为了抄写圣经的时候不犯错,把每个字母对应一个数字,然后把每一行和每一列的数字都取和,就形成校验码,抄写后对比行和列的校验码能够大幅度降低抄写错误。这跟前面说过的信息加和判断集合是否相同,一个道理。书中说到,人类在应用上有了很大进步,但是各种东西,最根本的“道”一直是一样的。比如做翻译,一定要有信息的冗余,这是过去古埃及罗塞塔石碑(石碑上用三种语言记载了托勒密五世登记的诏书,1822年其中的古埃及象形文字被破译)给我们的启示。做自然语言处理,一定要有信息的冗余和对照。虽然“术”发生了很大的变化,这个“道”一直没有变化。奇妙吧!

接着讲搜索引擎的事情。之前讲到索引了。索引是干什么的?索引就是搜索一个关键词的时候,你得知道哪几个网页和你相关,把相关网页提取出来。Google建立了一个网页-关键词的0-1矩阵。我们知道,关键词都是有词料库的,网页含有这个关键词,就用1表示;如果不含有该词,就用0表示。还是前面的例子,如果搜索{ “中关村”、“北京”、“地铁”},他找到这些网页,做一个“与”运算,结果矩阵中,三者全为1的网页才是目标网页。这即为布尔逻辑。

最后是排序。排序用的PageRank。在这一部分需要解决两个问题。第一:呈现高质量网页(PageRank);第二,呈现相关网页(相关性)。PageRank完全改变了之前的做法。先不管相关性问题,解决第一个问题:比如说有100个网页,这100个网页中,给他们排序。网页重要性的依据主要有两点:链接该网页的数量与链接该网页的网站的质量。数量很好统计,那质量呢?Google提出的PageRank解决了这个问题:给不同网站的链接打分,网页质量越高,打分越高,反之,网页质量低,打分就低。但是你如何确定这个网页质量是高还是低呢?而且网页之间是相互引用的,存在“鸡生蛋还是蛋生鸡”的问题。具体做法呢?有一个小例子,可以形象的说明佩奇排序的运算过程:

 三兄弟分 30 颗豌豆。起初每人 10 颗,他们每次都要把手里的豌豆全部平均分给自己喜欢的人。下图表示了三兄弟各自拥有的初始豌豆数量,以及相互喜欢的关系(箭头方向表示喜欢,例如老二喜欢老大,老大喜欢老二和老三)。

就这样,让游戏一直进行下去。直到他们手中的豌豆数不再变化为止。

 

 

那么这个游戏到底是否可以结束呢,如果可以,最终的结果又是什么样的?在此我们用电脑模拟了这个过程,得出的结果是:老大和老二的盘子里各有 12 颗豌豆,而老三的盘子里有 6 颗豌豆。这时候无论游戏怎么进行下去,盘子里的豌豆数量都不会再变化。如果把豌豆的数量看作这个分数值(可以不是整数),把孩子们看作网页,佩奇排序就不难理解了。 来源:http://blog.sciencenet.cn/blog-545103-849391.html