Url去重学习

之前面试的时候被问到是否了解过url去重,当时就说了个没有,电话完了之后就感觉不太对劲,没有也得说点东西啊…其实当时想到了一种去重的方法,将采集到

的url使用md5加密存到数据库中,那么只需要比对md5就可以知道这个url有没有重复了,后来看了看去重的几种方法,感觉我当时想的好像也差不多…简直血亏..今天再系统的学习一遍有哪些去重方法吧。

数据库存储

适用于分布式爬虫,将url直接存到数据库中,爬取之前进行查询

Hash Table

哈希表在Python中的实现就是dict和set,都是用内存空间换时间的操作,每次爬取启动时新建一个哈希表，在爬取过程中将爬过的丢进去，后面每次爬一个 

url 的时候先在哈希表里检查一下是否已经存在这个值，如果已经爬过了就直接把任务丢弃掉。为了降低内存使用量,可以使用md5 sha1什么的将url先行加

密,能够有效的降低存储占用,同时可以借助 Redis 来实现分布式(scrapy也是采用的这种方法)

Bloom Filter

以上两种思路自己都能想到,这个名词就没听说过了,需要好好学习一下

这个东西叫做布隆过滤器,是由一个 bitmap 和若干个哈希函数构成的,它可以用来高速检查一个元素是否可能在集合中，并且空间占用要比上面的方法少很多，

但只能向 Bloom filter 里添加元素，却没法删除，并且随着里面的数据量增大，会有一定程度的误报。因此这是一个用错误率换时间和空间的方法

它的原理是将一个元素通过 k 个哈希函数，将元素映射为 k 个比特位,相比于hash table来说,只是增加了k个函数同时映射,在 bitmap 中把它们置为 

1。在验证的时候只需要验证这些比特位是否都是 1 即可,如果其中有一个为 0,那么元素一定不在集合里,如果全为 1,则很可能在集合里。（因为可能会有其

它的元素也映射到相应的比特位上）同时这也导致不能从 Bloom filter 中删除某个元素,无法确定这个元素一定在集合中。以及带来了误报的问题,当里面的

数据越来越多,这个可能在集合中的靠谱程度就越来越低。（由于哈希碰撞，可能导致把不属于集合内的元素认为属于该集合)

python中已经有大佬实现了第三方库,可以直接用了

利用Simhash做URL去重的实现方式

这个方法是从[这篇文章](http://docs.ioin.in/writeup/www.noblexu.com/_%E5%88%A9%E7%94%A8Simhash%E5%81%9AURL%E5%8E%BB%E9%87%8D%E7%9A%84%E5%AE%9E%E7%8E%B0%E6%96%B9%E5%BC%8F_/index.html)看到的

简单来说就是先对url做一个泛化,去除同类型的url,这在渗透测试的扫描器中是有一定的可取性的,因为同类型的url只需要扫描一次就够了,多余的扫描会浪费

大量的时间和性能

然后使用Google的Simhash算法,这个算法我之前在写bilibili答题机的时候用到过,但是效果不好,就放弃了,可能是应用场景的区别造成的吧。这个算法就是

计算两个字符串是否相似,具体应该是计算汉明距离判断的,这里就不做深入研究了,能用就可以。