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

正文

请到「今天看啥」查看全文

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的索引结构。

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

请到「今天看啥」查看全文