网页爬虫及其用到的算法和数据结构

　　网络爬虫程序的好坏，很大程度上反映了一个搜索引擎的好差。不信，你可以随意拿一个网站去查询一下各家搜索对它的网页收录情况，爬虫强悍程度跟搜索引擎优劣基本成正比。

　　1.世界上最简单的爬虫——三行情诗

　　我们先来看一个最简单的最简单的爬虫，用python写成，只须要三行。

　　import requests url="http://www.cricode.com" r=requests.get(url)

　　上面这三行爬虫程序，就如下边这三行短诗通常，很干脆利落。

　　是好男人，

　　就应当在和妻子争吵时网络爬虫算法书籍，

　　抱着必输的态度。

　　2.一个正常的爬虫程序

　　上面哪个最简单的爬虫，是一个不完整的残障的爬虫。因为爬虫程序一般须要做的事情如下：

　　因此，一个完整的爬虫大约是这样子的：

　　import requests                       #用来爬取网页

　　from bs4 import BeautifulSoup         #用来解析网页

　　seds = ["http://www.hao123.com",      #我们的*敏*感*词*               

　　        "http://www.csdn.net",              

　　         http://www.cricode.com]

　　sum = 0                               #我们设定终止条件为：爬取到100000个页面时，就不玩了  

　　while sum < 10000 :     

　　    if sum < len(seds):          

　　        r = requests.get(seds[sum])          

　　        sum = sum + 1          

　　        do_save_action(r)         

　　        soup = BeautifulSoup(r.content)                         

　　        urls = soup.find_all("href",.....)                     //解析网页          

　　        for url in urls:               

　　            seds.append(url)                   else:          

　　                    break

　　3.现在来找碴

　　上面哪个完整的爬虫，不足20行代码，相信你能找出20个茬来。因为它的缺点实在是太多。下面一一列出它的N宗罪：

　　4.找了这么多茬后，很有成就感，真正的问题来了，学挖掘机究竟哪家强？

　　现在我们就来一一讨论里面找碴找出的若干问题的解决方案。

　　1）并行爬起问题

　　我们可以有多重方式去实现并行。

　　多线程或则线程池形式，一个爬虫程序内部开启多个线程。同一台机器开启多个爬虫程序，如此，我们就有N多爬取线程在同时工作。能大大降低时间。

　　此外，当我们要爬取的任务非常多时，一台机器、一个网点肯定是不够的，我们必须考虑分布式爬虫。常见的分布式构架有：主从（Master——Slave）架构、点对点（PeertoPeer）架构，混合构架等。

　　说道分布式构架，那我们须要考虑的问题就有很多，我们须要分派任务，各个爬虫之间须要通讯合作，共同完成任务，不要重复爬取相同的网页。分派任务我们要做到公正公平，就须要考虑怎样进行负载均衡。负载均衡，我们第一个想到的就是Hash，比如按照网站域名进行hash。

　　负载均衡分派完任务以后，千万不要以为万事大吉了，万一哪台机器挂了呢？原先委派给死掉的哪台机器的任务委派给谁？又或则哪天要降低几台机器网络爬虫算法书籍，任务有该怎样进行重新分配呢？

　　一个比较好的解决方案是用一致性Hash算法。

　　2）待爬取网页队列

　　如何对待待抓取队列，跟操作系统怎么调度进程是类似的场景。

　　不同网站，重要程度不同，因此，可以设计一个优先级队列来储存待爬起的网页链接。如此一来，每次抓取时，我们都优先爬取重要的网页。

　　当然，你也可以仿效操作系统的进程调度策略之多级反馈队列调度算法。

　　3）DNS缓存

　　为了防止每次都发起DNS查询，我们可以将DNS进行缓存。DNS缓存其实是设计一个hash表来储存已有的域名及其IP。

　　4）网页去重

　　说到网页去重，第一个想到的是垃圾邮件过滤。垃圾邮件过滤一个精典的解决方案是BloomFilter（布隆过滤器）。布隆过滤器原理简单来说就是：建立一个大的位字段，然后用多个Hash函数对同一个url进行hash得到多个数字，然后将位字段中这种数字对应的位置为1。下次再来一个url时，同样是用多个Hash函数进行hash，得到多个数字，我们只须要判定位字段中这种数字对应的为是全为1，如果全为1，那么说明这个url早已出现过。如此，便完成了url去重的问题。当然，这种方式会有偏差，只要偏差在我们的容忍范围之类，比如1万个网页，我只爬取到了9999个，剩下那一个网页，whocares！

　　5）数据储存的问题

　　数据储存同样是个挺有技术浓度的问题。用关系数据库存取还是用NoSQL，抑或是自己设计特定的文件格式进行储存，都大有文章可做。

　　6）进程间通信

　　分布式爬虫，就必然离不开进程间的通讯。我们可以以规定的数据格式进行数据交互，完成进程间通信。

　　7）……

　　废话说了那么多，真正的问题来了，问题不是学挖掘机究竟哪家强？而是怎么实现里面那些东西！：）

　　实现的过程中，你会发觉，我们要考虑的问题远远不止里面那些。纸上得来终觉浅，觉知此事要笃行！