Search Engine_从网络爬虫到PageRank算法

今天开始研究搜索引擎——2011_12_12,不知道能坚持到什么时候？？

 

要研究搜索引擎，我觉得必须要简单的了解如何获取网页和最简单的网页排名算法——PageRank算法。

 

一、Spider程序

 

蜘蛛、爬虫、机器人或者其它的别的名字，这些东西是搜索引擎的基础。这些程序会在网络上巡逻，在网络中的各个网页中穿梭，将收集到的网页内容（文本、链接等等）存储到数据库中，作为搜索引擎工作的“原材料”。

 

我们知道，一个网页通常会包含多个外部网页的链接地址（如，你从新浪首页可以链接到淘宝的页面），而这些外部链接本身也是网页，也会包含多个外部网页的链接地址，以此循环...

 

一个重要的理论是：从有限个网页出发，重复上面的过程，最终会遍历网络上的大多数（99%以上）网页。

 

当爬虫程序开始运行时，会得到多个网站地址作为必要的种子输入（baidu、google等大型搜索引擎一般会以重要的门户网站为输入，如yahoo！）。

 

下面是一个爬虫程序工作原理的简述。PS：自己画的，很简洁很简洁哦

 

 

 

 

Spider程序的扩展：

 

1、网络爬虫程序检索网页时到底在干什么？？

 

如果仅仅理解成“阅读”网站可能会有些不妥。

 

首先，爬虫程序会向web服务器站点发送请求，这跟普通用户是一样的。但是与普通用户不同爬虫程序只关心网页中的文本信息（包括大部分的HTML代码）。为什么会关心HTML源代码？？这个后面会提到

 

2、网页本身可不可以拒绝爬虫程序的进入

 

Absolutely可以！

 

事实上，我们可能碰到的主要问题是，由于网络延时或者系统过载等原因，网页并不能及时回应爬虫程序的。如果在爬虫程序的耐性时间（假设是3秒，这堆大多数网页来说，是很宽裕的），网页没有做出正确的回应，那么爬虫程序会重定向至别的网站。

 

对于访问失败的网页，爬虫还是可能返回的。但是，如果多次失败，便会彻底放弃。之后，排名会下降。

 

这意味着什么？如果网页包含了大量的图片，加载速度本身就很慢，就需要有某种手段不让爬虫程序查看这些网站。

 

PS：顺便吐槽下我们学校的教务管理系统，据说是国防科大做的？？这么烂？？

 

 

3、爬虫程序都有哪些？？

 

下面是一些常见的搜索引擎爬虫：

 

Google：Googlebot

 

baidu : baiduspider

 

MSN：MSNbot

 

Yahoo！：Yahoo SLURP or简称SLURP

 

Ask：Teoma

 

Alta Vista ：  Scooter

 

了解部分搜索引擎是必要的，因为除了那些正规程序的爬虫程序外，还会有一些恶意的爬虫也会进入你的网页。如果不知道这些恶意程序的名字，就不能正确及时的阻止这些恶意程序。

 

 

 

二、PageRank算法

 

一个显而易见的理由：我们知道，对于依赖关键词的搜索引擎来说，如google和baidu，通过Spider程序收集到的网页数量是一个天文数字。据google的官方文章，2002年这一数字就达到了20亿，可想而知经过网络飞速发展近10年后的今天这一数字是多么的惊人。另一个需要注意的问题是，大多数的非专业搜索用户提问由仅仅1~4个单词构成。这两者之间的矛盾让人们在很早之前就意识到了一个有效的搜索排名的重要性，好让用户得到也仅仅得到想要的答案。

 

而PageRank，就是最初人们想要的排名算法。

 

在传统情报检索理论中，引文分析方法是确定学术文献权威性的重要方法之一，即根据引文的数量与质量来确定文献的权威性。根据这一理论，被高中课本引用的热力学第一定律的权威性肯定大过本人刚才灵机一动随口说的热力学第x定律，我就是随口说的，就没人知道！！

 

PageRank算法借鉴了这种思想：一个网页的“权威性”与这个网页被链接的数量和质量直接相关。这样就可以利用网络自身的超链接结构给所有的网页确定一个重要性的等级数（PR值）：当从网页A链接到网页B肘，就认为 网页A投了网页B一票。，增加了网页B的重要性。

 

下面举一个例子：

假定一个由A、B、C、D组成的网络，网页A中链接到了B、C，网页B链接到了A、C，网页C链接到了A、B、D，网页D链接到了A。

 

考虑A，由于A被所有网页所链接，那么PR（A ） = PR（B ）+PR（C）+PR（D）

 

又由于B链接到了2个网页，而网页不能投2次票，那么只有将B的票数一分为2，C、D同理，那么PR（A ） = PR（B ）/2+PR（C）/3+PR（D）

 

即：PR（A ） = PR（B ）/L（B）+PR（C）/L（C）+PR（D）/L（D），L（x）为网页x的内部链接数。

 

然后，所有这些被换算为一个百分比再乘上一个系数d。由于下面的算法，没有页面的PageRank会是0。所以，Google通过数学系统给了每个页面一个最小值1 − d。

 

即PR（A） = 【PR（B ）/L（B）+PR（C）/L（C）+PR（D）/L（D）】*d + 1 - d， d被称为阻尼系数（damping factor)，值为0.85

 

解决了么？？没有！！因为在计算PR（A）时，PR（B）等值还不知道。这就好像是一个鸡生蛋还是蛋生鸡的问题：计算一个PR值还要考虑别的PR值，陷入了死循环。

 

对这个问题，PageRank算法的发明人Larry Page，同时也是Google的创始人之一，通过计算证明出，对所有网页随机给定一个PR值，重复有限多次上面的计算，结果会趋近理论值。即PageRank算法具有回归性。

 

对上面的算法，我发现计算投票时，往往还要考虑到“投票人”本身的“票数”。即本身属于“重要”网站的投票投的票权值较高，就好像现在比尔盖茨说的话比我说的话可信度要高一样。同时，当一个网站投的票数很多时，对于每个票的价值会降低。我们校长单独夸我的效果明显比夸中南大学所有的学生的效果好！！

 

 

未完待续！！！！

 

下面还将有的内容：实际PageRank算法要解决的问题，影响Google PageRank的因素（网络排名“作（河蟹）弊”），PageRank相关算法、PageRank的不足之处

 

编辑本段

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

评论

2 楼 白粥若水 2012-02-04  

xiaoluobo6666 写道

其实。。。在看pageRank时。。。总是会想，假如一个网站，没有外部链接引用，那不就是无法通过搜索引擎搜索到了？可是，实际中，当一个网站没有外部链接，而我仅仅是搜索其对应域名的拼音时，玩玩还能搜到对应的网站。。。pagerank不是万能的。。。

对的，PageRank算法是很基本的算法，单纯应用Pageank算法结果乐观。事实上，实际中总是多种算法一个使用。现在的搜索算法或多或少与Pageank算法有关系

1 楼 xiaoluobo6666 2011-12-13  

其实。。。在看pageRank时。。。总是会想，假如一个网站，没有外部链接引用，那不就是无法通过搜索引擎搜索到了？可是，实际中，当一个网站没有外部链接，而我仅仅是搜索其对应域名的拼音时，玩玩还能搜到对应的网站。。。pagerank不是万能的。。。