大数据方法论之网页消重的Map-Reduce算法

以下内容已屏蔽图片优化访问速度
当你爬取了大量的网页,里面肯定有很多重复的内容,这些重复的内容需要去重来解决。


一个著名的算法就是SimHash算法。


[IMG]


通用的去重算法框架如图所示(图来自互联网)


对于一篇文档,首先要抽取出能代表这篇文章内容的特征,当然特征数目肯定是很多的,如果比较两篇文章的所有特征,太费时间了,所以要对特征进行一定的运算,称为文档指纹,指纹就像人的指纹一样,虽然信息量不大,相对比较容易相互比较,但是能够代表区分不同人的信息。最后就是基于指纹进行相似度计算,相似度大的,则为文档重复,相似度小的,则文档不重复。


[IMG]


对于SimHash来讲,计算方法如下:


1、分词,讲文本分词形成这个文章的特征单词。最后形成去掉停词之类的单词序列,并统计每个词出现的数目tf作为权重
2、hash,通过hash算法把每个词变成hash值,这里以8位hash值为例子。
3、加权合并,通过 2步骤的hash生成结果中的每一位,乘以权重,然后加起来,形成权值求和的向量
4、降维,把3步算出来的 向量变成 0 1 串,形成我们最终的simhash签名。 如果每一位大于0 记为 1,小于0 记为 0。


上面的指纹数目使用8位做简单的演示,真实的使用中往往使用64bits指纹, <= 3bit 不同算相似。


然而在64位中逐个比较,直到找出3个不同位来,计算量还是很大的,所以就有了如下的SimHash的索引结构。


[IMG]


将64位的二进制串等分成四块,每块16位,将所有的文章的simhash保存四份,分别保存在四个Table里面,在第一个Table里面,第一个16位在前面,第二个Table里面,第二个16位在前面,以此类推。


来了一篇新的文档的时候,也将64位分成四份,变成如图红色的四个序列。


首先采用精确匹配的方式查找前16位,如果在四个Table中都匹配不中,则说明至少有四位是不同的,已经不相似。


如果和其中一个Table比较中了,然后在Table中再进行比较。


下面我们来看如何使用Map-Reduce来解决这个问题。


假设:有1T非重复的已有网页集合 SimHashDb ,新来100万网页parse_text。


首先要做的事情是新来的100万网页内部去重,可以分成100个map任务,每个任务1万个网页。


对于每个网页求simhash为64位,然后将这个simhash加到四个Table里面,并且partition的时候,是根据四个table进行partiton的。


[IMG]
在Reduce的时候,有四个Table,所以是四个Reduce,每个Table的key是前16位,有相同的Table Key的都在一个list里面,在这个list里面比较是否差异超过3位,超过则false,不超过则true。


最终输出的是四个partition,每个partition里面都会记录每篇文章isdup为true还是false,为true,则说明100万以内就重复了,false则还需要进一步去重。


[IMG]


最后100万数据要和1T的数据进行去重了,这里的算法有一个小技巧,就是到底是100万把1T数据过一遍,还是1T数据把100万过一遍。


对于普通的算法,当然是1T变成某种索引结构放在那里,100万分别和1T去比较,但是map-reduce里面,如果这样会发现100万的并发度太低,并且并发的任务如果都去统一的1T里面去比较,相当于虽然任务分开了,但是有一个统一的瓶颈点,其实并没有分布式的去计算,虽然分成了100个任务,但是大家都去调用同一个url地址。


但是1T的数据是全量数据,是不可能加载到内存里面的,也不肯能有几个任务就复制成几份。


但是思路一旦反过来就可以了,我们让全量去过增量,因为增量是很小的,加载到内存或者复制多份代价都不大,而全量的数据量大,适合分任务去执行,能够并发的起来。




[IMG]


于是我们将全量1T进行split来分成map任务,64M一块,这样并发任务会很
多,大大提高的执行速度。


对于每个map任务,看到的都是增量的四个Table的全部。这64M的全量里面的文档放在增量的四个Table中进行比较。对于增量的文档,如果重复则标记true,否则为false.




[IMG]


Reduce的时候,处理的还是增量的部分,全量的只是过了一下,其实没有动,增量的部分相当于复制成了多份,在每个split里面进行比较,最后汇总的时候,有一个是重复的,则就为重复了。


不重复的部分汇总到全量里面去。
凌晨,一个人,脑出血 一个人靠不靠谱,闭环很重要! 滴滴又陷杀人案?被误伤的滴滴,隐藏着另一种现实 尬唱尬舞反串,没有年会,你都不知道自己能这么骚 谁还会救贾跃亭?
好看吗?
总执行时间0.0754554271697998,文章查询时间0.005576133728027344,分类查询时间0.06752896308898926,其他脚本0.00017070770263671875,模板渲染0.0021796226501464844