点击上方“程序员大咖”，选择“置顶公众号”

关键时刻，第一时间送达！

以前在做漏洞Fuzz爬虫时，曾做过URL去重相关的工作，当时是参考了seay法师的文章以及网上零碎的一些资料，感觉做的很简单。近来又遇到相关问题，于是乎有了再次改进算法的念头。

首先，针对URL本身的去重，可以直接对整块URL进行处理。在参考网上的一些文章时，发现它们大多采用了 URL 压缩存储的方法。不过使用这些算法在数据量较大的时候，能大幅减小存储的空间：

基于磁盘的顺序存储。

基于Hash算法的存储。

基于MD5压缩映射的存储。

基于嵌入式Berkeley DB的存储。

基于布隆过滤器（Bloom Filter）的存储。

对于 URL 直接去重，主要涉及的是存储优化方面，对于本文不是重点，这里不再细说。

而对于 URL 逻辑上的去重，则需要更多地追求数据的可用性，这是做测试工作需要去考量的。

这里先给出 seay 文章中的相似度去重算法，大致是下面这样的：

def urlsimilar(url):        hash_size=199999        tmp=urlparse.urlparse(url)        scheme=tmp[0]        netloc=tmp[1]        path=tmp[2][1:]        query=tmp[4]        #First get tail        if len(path.split('/'))>1:            tail=path.split('/')[-1].split('.')[-1]            #print tail        elif len(path.split('/'))==1:            tail=path        else:            tail='1'         #Second get path_length        path_length=len(path.split('/'))-1        #Third get directy list except last        path_list=path.split('/')[:-1]+[tail]        #Fourth hash        path_value=0        for i in range(path_length+1):            if path_length-i==0:                path_value+=hash(path_list[path_length-i])%98765            else:                path_value+=len(path_list[path_length-i])*(10**(i+1))        #get host hash value        netloc_value=hash(hashlib.new("md5",netloc).hexdigest())%hash_size        url_value=hash(hashlib.new("md5",str(path_value+netloc_value)).hexdigest())%hash_size        return url_value

这段函数的大概作用是，最后它会根据算法返回一个hash值，这个hash值也就是该URL的hash相似度。如果两个URL计算出的hash值最后比较相等，我们则可以判断两个URL是具有较高的相似度的。

但是这个函数应该是seay举例时随手提出的（这里强调下，免得被喷，后文不再细说），只是简单做了demo，并没有进行细化检验。在比较粗糙的情况下，该算法确实能剔除一些简单的参数重复的情况，但一旦参数复杂或者url不规范，是不太能很好的进行去重的。

那么在针对URL获取的过程中，我们还可以做的小优化有哪些呢？

日期时间命名

首先，我们可以根据日期来去重。我们知道，在爬取一些Blog和和门户等系统时，经常会遇到以日期命名的目录。

这些目录大概归纳起来，存在类似下面的形式：

2010-11-11
10-11-11
20101111

当然，还有些文件会以时间+随机值命名，也可能是用unix时间戳命名，这些可能是根据上传和编辑时间来定义的。

笔者建议是，使用redis或者memcache之类等缓存型数据库，将其直接存储；或者在数据量较大的时候，考虑将其作临时存储，需要的时候再进行对比。

比如，一旦出现日期时间命名的目录或静态文件，我们可以考虑将其存储为下面的格式：

目录层级

命名格式

URL地址(或压缩过的hash值)

有人可能说，在前面seay提出的那个案例里，好像是可以解决类似日期相似度的问题。那我们先看看下面的例子，此处输出仍然基于上面那个函数：

print urlsimilar('http://www.baidu.com/blog/2010-10-11/')print urlsimilar('http://www.baidu.com/blog/2010-10-13/')print urlsimilar('http://www.baidu.com/blog/2010-9-13/')print urlsimilar('http://www.baidu.com/whisper/2010-10-11/')

输出结果如下：

110086
110086
37294
4842

我们可以看到，在普通情况下，确实于相同父级目录下，相似度算法是可以判断正确的。 但是一旦日期格式不规范，或者父级目录存在一定的差异，这里是不能很好的判断的。

当然，我们也可以通过机器学习来完成去重的工作。不过就简化工作而言，还是可以使用一些小Tips，根据规则匹配来做到。

静态文件的去重

我们知道，在爬取URL的过程中，也会遇到许多静态文件，如shtml、html、css等等。这些文件在大多数的情况下，是没有太大意义的。除非测试者倾向于使用“宁可错杀一百，绝不放过一个”的全量采集手法。

这时候，我们可以配置黑名单，建立文件后缀规则库进行过滤。

当然，在这些静态后缀的URL链接，也可能带上参数混淆的情况。 个人建议是，用于回调的json、xml等URL，里面可能储存敏感内容，尽量别动；其他类型的静态文件，仍然采取将参数分离的方式，最后对URL进行去重存储。

特定情况的过滤

在爬取特定网站时，我们可以预先做好配置，指定过滤一些目录和页面，以节省大量时间资源。

反过来，我们也可以指定只爬取指定目录下的页面，定向获取我们想要的内容。

敏感页面的感知

在前面seay提出的demo算法中，在这种情况下是有一定局限的。比如我们需要在敏感目录下，尽可能多的拿到文件信息。比如我们爬取到了后台管理目录，可能会遇到下面的情况：

print urlsimilar('http://www.baidu.com/blog/admin/login.php')print urlsimilar('http://www.baidu.com/blog/admin/manage_index.php')print urlsimilar('http://www.baidu.com/blog/admin/test.css')

输出结果如下：

40768
40768
40768

很明显有问题不是么？

当然，我们可以通过对敏感页面关键词进行监控；或者也可以指定后缀文件，进行白名单监控。

但是一旦这样做，而且还想采用前面的hash算法的话，大家自行定义的过滤函数的优先级，肯定需要大于该算法。并且，我们在这样做的过程中，也应该考虑过滤成本的问题，建议采用选择性启用。

高频敏感目录的优待

可能在爬取的过程中，部分爬虫是兼用了目录爆破的手段的。如果采用了这种手法并且匹配成功后，我们可以将该目录下的内容单独使用一份过滤规则，从而避免去重算法的误判。

响应页面的过滤

对于某些网站来讲，可能有不少页面因为链接是失效的，会被冠以404页面和50x错误。另外，在无权访问的时候，可能网站会做30x跳转和403目录限制。

这些页面没有实质性内容，在大多数时候是没有意义的，我们可以在配置文件里对需要爬取的这类页面做白名单，比如保留403页面，或者存取30x跳转前（后）的页面。

WAF（警告）页面过滤

某些网站可能被装上了WAF，在访问频率过快时，可能会得到一个WAF的警告页面。而在CMS本身就做了限制的情况下，会以20x的响应码展示一些没有不存在的页面。

当然，我们可以通过分布式换代理的方式，去解决部分这样的问题，这里先不多做讨论。

这时候，我们可以配置相应的次数阈值，如果某些页面出现的次数过多，可以将其标记为警告（WAF）页面，进而做出过滤处理。这里对某页面的识别，可以通过黑名单关键字标记；或者尝试计算页面hash值，比如下面这样：

content = urllib2.urlopen('http://www.test.com/').read()md5_sum = hashlib.md5()md5_sum.update(content)print md5_sum.hexdigest()

当然，我们在实际计算页面hash值和做关键字监控时，也可能由于反爬虫机制的存在（如添加随机值），需要适时调整相似度来计算hash值或者采用其他手段。当然这也会消耗更多的时间和机器资源。但某些特定的情况下，可能也会带来意想不到的收获。

无意义参数页面去重

我们在采集页面的过程中，同样有可能会遇到一些毫无意义的、高频出现的多参数页面。这类页面可能是回调页面，也可能是临时渲染的随机页面。

在这里，大家可以通过前面处理WAF（警告）的方法进行过滤。当然，使用前面的hash算法也是可以应对大部分情况的。毕竟网站的这类的URL有限，不必为了几种特型去消耗更多的资源，这样得不偿失。

JS代码中的URL

在我们提取js代码，也就是遇到ajax之类的交互情况时，可能会遇到需要拼接的GET请求，或者直接可以取用的POST请求。

这类的URL地址，最好是结合phantomjs等webkit，更方便地进行动态拼接。

它们会显得比较特殊，可能仅仅返回状态码，也可能会返回实质性的敏感内容。这种情况，就需要根据爬取者的要求，对爬取的过滤规则进行适应性调整。

总结

笔者这里旨在提出一些对相似URL去重的小优化，可能效果有限，也可能存在未尽人意之处。

欢迎大家提出建议，希望少一些爱喷的童鞋，多一点讨论的大牛，与诸君共勉。

• 来自：FreeBuf.COM-dawner

• www.freebuf.com/articles/others-articles/151173.html

• 程序员大咖整理发布，转载请联系作者获得授权

【点击成为安卓大神】

始发于微信公众号：程序员大咖