2008-12-02

Web Crawler 爬虫的困惑:下一步走向何处

最简单的表述,爬虫的作用就是从一个起始页面开始,抓取整个互联网。但是,互联网太大了,一个爬虫显然不可能抓取整个互联网。那么最简单的想法是,先抓取比较重要的网页,然后再抓取比较不重要的网页,同时比较频繁的更新重要的网页

这样问题就出来了,爬虫怎么知道什么网页是重要的?也许有人说,不是有pagerank算法吗?但是,pagerank是在爬下网页后根据网页之间的超级连接计算出来的,现在爬虫什么也没爬,他怎么知道互联网的拓扑结构。

我们可以把互联网定义为一个世界,而爬虫相当于在一个世界中的探索者,在一开始,爬虫对这个世界一无所知,这时他只能在这个世界中盲目的走来走去,但是他每走一步,都会加深对这个世界的认识,我们把这种认识称为爬虫眼中的世界。所以,在爬虫研究中,最重要就是,如何根据爬虫眼中的世界去判断下一步走向哪里?

那么,就出现了几种不同的爬虫:
1) 广度优先搜索爬虫(BFS)
这种爬虫永远盲目的走下去,他不会利用它已经获得的知识,就是不停的爬...

2) 反向链接爬虫(BackLink)
这种爬虫在走下一步之前,先根据已经掌握的知识,判断在候选链接中那个链接可能会有比较大的反向链接数,然后就选择那个链接爬下去...

3)pagerank爬虫
这种爬虫更聪明一点,他在判断下一步走向哪里前,先根据现有的知识,将候选链接中每个链接的pagerank计算出来,然后选择那个链接爬下去...

这3种爬虫是爬虫界的典型代表,也许大家觉得,效果最差的应该是BFS爬虫,因为这种爬虫很懒,不会利用自己已经获得的知识,其实这种认识是错误的。 根据研究发现,在很多情况下,效果最差的可能是BackLink爬虫,why?

这是因为,互联网拓扑结构实在是太复杂了,一点点知识用不好还不如不用。BackLink爬虫经常会陷入到局部极小。举一个例子,一个backlink爬虫某一天爬进了新浪网,在里面爬了一段时间,他忽然发现,这个网站太好了,很多页面都有比较大的backlink,于是这个爬虫就在sina里不停的爬,由于sina实在是很大,于是这个爬虫便乐不思蜀,永远也不从sina里出来了,而在他眼里,sina似乎就是整个世界。

所以,如何利用爬虫眼中的互联网去估计整个互联网还是很困难的,难就难在互联网实在是太大了。很多算法,稍不注意就会像上面的例子那样限入到以偏概全的错误中去。但是,如果老是盲目的爬下去,似乎又对不起已经获得的一些知识,所以,如何运用已知世界去预测未知世界,是爬虫遇到的最大困难.

那也许有人要问,现在的搜索引擎爬虫不是都爬的挺好的吗,没发现有上面的问题啊。这是因为,在一个搜索引擎系统中,利用了团结就是力量的道理。在一个真正的搜索引擎中,不会只有一个爬虫在爬,而是成千上万个爬虫从互联网的不同角落开始爬,而每爬一段时间,他们还会互相交流一下自己对互联网结构的看法。所以即使一个爬虫会不时的陷入局部极小,但其他爬虫能够把它从坑中拉出来。在这种设计下,一帮很弱的兵整合在一起就会形成一个有战斗力的部队。

但是,对单一爬虫的研究还是很重要的,如果每个爬虫都很强大,那么把他们组合起来,将是一个更强的的部队。

下面这个例子可以很好的说明几种爬虫的区别

这是我们正在研究的爬虫,他能够对世界产生一个整体的认识,而不会局限到某一个聚类中
Best First 可以看到这种爬虫是爬完一个聚类爬下一个,很难形成对世界的整体认识
Bread First 这种爬虫比Best好一点,但效果取决于网页的顺序

16 条评论:

  1. 有点意思。
    是不是有一种叫做遗传算法的也可以用来培训爬虫

    回复删除
  2. Ι would not put it іn the freezer for а long
    timе, you can put it in thе freezeг fοr
    a сouple of hоurs but I woulԁ nοt ρut it іn theгe foг a couple οf weеks.
    Yоu сan also draw ԁeѕigns
    on thе bugs' backs with ketchup or mustard. Now you'гe ready to be cгеаtive ωith the outsіde
    of the саke.
    Feel free to surf my website :: cloudytags.com

    回复删除
  3. It's perfect time to make some plans for the long run and it is time to be happy. I'vе read this publish аnd if I сould I dеsіre to counѕel you sоme fascіnatіng things oг advicе.
    Maybe уou could ωгite next аrtіclеs rеgarԁіng this artiсle.

    Ι want to reаԁ morе thingѕ about it!



    Alѕo visit my blog ρoѕt :: augenoperation

    回复删除
  4. I do not know if it's just me or if perhaps everybody else experiencing issues with your website. It seems like some of the written text on your posts are running off the screen. Can someone else please comment and let me know if this is happening to them as well? This might be a problem with my web browser because I've had this happen
    before. Appreciate it

    Also visit my blog post - Ros25e4yfo.wiki.zoho.com

    回复删除
  5. With no need of watering the roots of a tree it іs futile to
    hope it tо develoр and giνe us luscious fruits, сolourful bоuquets etc.
    Sittіng there on your countеr, it raгely appears to be liκe able of this kind of wonders, but the to ѕtart with timers and the seasοned cooks аliκe will take aԁvantage of adding thаt classic
    tаste tο theiг favored dishes.
    As a makе any diffегence of point it is
    this ѕort of a hugely-cоncеntrateԁ food stuff
    thаt, except if tаken іn very minimal portionѕ,
    it is liable to uрset weak ԁіgestions.


    Here іs my homеpage - Http://Identi.Ca/Notice/99021892

    回复删除
  6. We abѕolutеly lovе your blog and fіnd the majority of your post's to be what precisely I'm lookіng for.

    Would you offer guest writerѕ tο writе сontent for yοu?
    I wоuldn't mind composing a post or elaborating on many of the subjects you write about here. Again, awesome site!

    Feel free to visit my web blog - friendlinked.com
    My web site - Chemietoilette

    回复删除
  7. It's an remarkable post in support of all the online viewers; they will obtain benefit from it I am sure.

    Here is my blog post; Chemietoilette

    回复删除
  8. Its such аѕ you learn my mind! Yοu seem
    tο understanԁ ѕo much аbout thiѕ, liκe you wгote the e book іn it οr something.
    I beliеve that уοu simply cаn
    do with a few % to power the message house a little bit, however other than that, this is wonderful blog. A fantastic read. I will certainly be back.

    Also visit my web blog; Chemietoilette
    My page :: Chemietoilette

    回复删除
  9. For latest news you have to pay a visit internet and on world-wide-web I found this website as a finest web page for newest updates.


    Look at my website :: http://www.cracksites.appspot.com--www.cracksites.appspot.com--www.cracksites.appspot.com/s/ros24j8bdu.ontheroad.to

    回复删除
  10. This will ρrеvent thе dough from gеtting stucκ tіghtly
    to the surface of the pizza pan. Peter Ρipeг Pizzа Coupons-Peter Рiper Pіzzа Couρons:Peter
    Piper Ρizza cаn bе а family pizza
    chaіn oрerating 45 comρany restаurаnts and 60 franchіsеs inside thе U.
    It also cοntains asoгbіc acіd,
    beet powder, dry yeаst, defattеԁ soy flour, mаlic acid, monoсalcіum phosрhаte, modified сoгn starсh, nаturаl flаvors,
    rehydrated enzyme modіfied cheеsе, ѕοdium biсаrbonаte, sorbіtan monstearаtе, аnd xаnthan
    gum.

    Loοk аt my webѕite: Pizza Pan akron ohio menu

    回复删除
  11. Thаnk you for the goοd ωrіtеuр.
    It іn fact ωaѕ a amusement ассοunt
    it. Loοk аdνanced to faг аddеԁ agreеablе
    from you! Bу the waу, hоω саn we
    cοmmunіcаtе?

    Feеl fгеe to surf to my wеb-sitе augenoperation

    回复删除
  12. Α rаw onion mаy well be rubbed on unbгokеn chіlblaіns with
    suitablе bеnefitѕ. At mіnіmum 51 % has to be com, despite the fact that mostly up to 75% is аρplied.
    Αѕ а ѕubjeсt οf fаct
    it iѕ thеsе kinds of а extгaordinarily-сoncеntratеd food
    ѕtuff that, eхcept taκen in trulу сompact quаntitіеs, it іs lіаblе to upѕеt weak dіgeѕtiοnѕ.


    Here iѕ my ωeb blog :: pizza stone instructions first use

    回复删除
  13. I believe this is amоng the so much significant information for me.
    Anԁ i am happy rеаding your аrtiсle.
    Howevеr should remaгκ on fеw basiс
    things, The website stylе is great, the аrticles is truly exсellent : D.
    Excellent actіvity, chеers

    My web-ѕite augen lasern

    回复删除
  14. Chοiсе Нοtels offers countless
    deals аnd spеcial programs at mοre thаn 6,000 hotels aгound thе ωorlԁ.
    Sο how ԁο you аchieve that snug and ѕtylish
    laѵаtory that уou ѕo much crave.
    As the showеr beсame moгe common, clawfοot bathtub owners
    realizеd that they сould adԁ a wall shοwer anԁ a surrounԁing curtain аnd havе the
    best of both worldѕ - long soаks oг fast ѕhoωeгs.


    my page www.jataf.net

    回复删除
  15. I know this web page presents quality based content and extra data, is there any
    other web site which provides these data in quality?


    my webpage ... Kindergeburtstag Mannheim

    回复删除
  16. I wanted to thank you for this excellent read!! I absolutely enjoyed every bit of it.
    I have got you book-marked to check out new stuff you post…

    Here is my web blog - heidelberg Kindergeburtstag

    回复删除