我们通过采集系统采集了大量的文本数据，但是文本中有很多重复的数据影响了我们对结果的分析。在分析之前我们需要对这些数据进行去重，如何选择和设计文本去重算法呢？常见的有余弦角算法、欧氏距离、杰卡德相似度、最长公共子串、编辑距离等，这些算法在比较文本数据不多的时候比较有用。如果我们的爬虫每天收集几千万条数据，我们如何高效地对这些海量的***数据进行合并和去重。最简单的方法是将待比对的文本与数据库中的所有文本进行比对。如果数据是重复的，它将被标记为重复。看起来很简单，我们来做个测试，拿最简单的两条数据，使用Apache提供的Levenshteinforloop，计算两条数据的相似度100w次。代码结果如下：Strings1="你妈妈叫你回家吃饭，请回家";Strings2="你妈妈叫你回家吃饭，请回家";longt1=System.currentTimeMillis();for(inti=0;i<1000000;i++){intdis=StringUtils.getLevenshteinDistance(s1,s2);}longt2=System.currentTimeMillis();System.out.println("耗时："+(t2-t1)+"毫秒");耗时：4266ms令人惊讶的是，计算需要4秒。假设我们每天需要比对100万次，则需要4秒来比对100万次的数据是否重复。即使一个文件是4秒，单线程一分钟也只能处理15个文件，一个小时只能处理900个文件，一天只能处理21600个文件。数量远不是一天100w，需要多少机器和资源才能解决。为此，我们需要针对海量数据场景的去重解决方案。经过研究，我们发现有一种叫做本地敏感哈希的东西。据说这个东西可以把文档降维到hash数，成对计算计算量。小多了。查了很多文档，看到google是用simhash做网页去重的。他们每天需要处理的文件是亿级的水平，大大超过了我们现在的文件水平。既然大哥有类似的app，那我们就试试吧。simhash是Charikar在2002年提出的，参考《Similarity estimation techniques from rounding algorithms》。介绍该算法的主要原理。为了便于理解，尽量不要使用数学公式。分为这几个步骤：1.分词，需要分词判断，形成本文的特征词。***形成一个去除噪声词并为每个词增加权重的词序列。我们假设权重分为5个级别（1~5）。例如：“美国“51区”员工声称里面有9个飞碟，他们见过灰色外星人”==>分词后变成“美国（4）51区（5）员工（3）claim(1)Inside(2))Yes(1)9planes(3)UFO(5)Zeng(1)saw(3)gray(4)alien(5)”,括号代表词中的重要性整个句子，数字越大越重要。2.哈希，将每个词通过哈希算法转化为一个哈希值。例如，“美国”通过哈希算法计算为100101，“51区”通过哈希算法计算为101011。这样，我们的字符串就变成了一串数字。还记得我文章开头说的吗，我们需要把文章变成数字计算来提高相似度计算的性能。现在是降维过程。3.加权。通过二步哈希生成结果，需要根据单词的权重组成一个带权数串。例如“美国”的哈希值为“100101”，通过加权计算为“4-4-44-44”；“51区”的哈希值为“101011”，通过加权计算为“5-55-555”。4.合并，把上面单词计算出的序列值加起来，变成只有一个序列串。比如“美国”中的“4-4-44-44”，“51区”中的“5-55-555”，每一位相加，“4+5-4+-5-4+54+-5-4+54+5”==”“9-91-119”。这里作为例子，只统计了两个单词，真正的计算需要对序列进行累加所有单词的字符串。5.降维，将第4步计算出的“9-91-119”变成01的字符串，形成我们最终的simhash签名。每一位大于0的记为1，小于0的记为0。***计算结果为：“101011”。整个过程的画面是：你可能会有疑惑。走了这么多步，好麻烦，不就是得到一个01字符串吗？我直接把这个文本作为字符串输入，用hash函数生成01值比较简单。事实上，情况并非如此。传统的hash函数解决的是生成唯一值的问题，比如md5、hashmap等，md5是用来生成唯一的签名串，只要多加一个字符，md5的两个数看起来就很不一样；hashmap也是一种用于键值对查找的数据结构，方便快速插入和查找。然而，我们的主要解决方案是文本相似度的计算。我们要比较的是两篇文章是否相识。当然我们降维生成的hashcode也是为了这个目的。看到这里大家就明白了，我们用的simhash即使把文章中的字符串改成01字符串，依然可以计算相似度，而传统的hashcode不行。我们可以做一个测试，两个只相差一个字符的字符串，“你妈妈叫你回家吃饭，回家回家”和“你妈妈叫你回家吃饭，回家”andgohomeLuo".通过simhash计算结果为：10000100101011011111111000001010110100010011111000010010110010111000010010101101011111100000101011010001001111100001101010001011通过hashcode计算为：11111111111111111111111111111111100010000011001101001110110111101010010001111111110010110011101大家可以看得出来，相似的文本只有部分01串变化了，而普通的hashcode却不能做到，这个就是局部敏感哈希目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认的比较好的算法。在simhash的发明者Charikar的论文中，没有给出具体的simhash算法和证明。“量子图灵”得到的证明是simhash是从随机超平面哈希算法演化而来的。现在通过这样的转换，我们将库中的所有文本都转换成simhash码，转换成long型存储，大大减少了空间。现在我们已经解决了空间问题，但是如何计算两个simhash之间的相似度呢？是比较两个simhash的01有多少不同？是的，事实上就是这样。我们可以通过汉明距离来计算这两个simhash是否相似。两个simhashes对应不同值的二进制值（01字符串）称为这两个simhashes的汉明距离。例子如下：10101和00110从第一个位置开始，第一个、第四个、第五个位置不同，汉明距离为3。对于二进制字符串a和b，汉明距离等于XORb运算（通用算法）的结果为1s。为了高效比对，我们预加载库中已有的文本，并将其转换成simhash码存储在内存空间中。先将一段文字转换成simhash码，然后与内存中的simhash码进行比对，100w次测试计算时间为100ms。速度大大提高。未完待续：1、当前速度提高了，但数据还在不断增加。如果未来数据发展到每小时100w，按照现在的100ms，一个线程每秒处理10次，每分钟60*10次，一小时60*10*60次=36000次，60*10*60*24=每天864000次。我们的目标是每天100w次，可以通过增加两个线程来完成。但是如果你想要一个小时100w次怎么办？你需要增加30个线程和相应的硬件资源来保证速度能够达到，所以成本也会上去。有没有更好的方法来提高我们比较的效率呢？2.通过大量测试，使用simhash进行大文本比对。比如500多字的效果就挺好的，距离小于3，基本上都差不多，误判率比较低。但是如果我们处理的是微博信息，最大是140个字符，使用simhash的效果就不是那么理想了。如下图，当距离为3时，就是一个折衷点。当距离为10时，效果已经很差了。但是，我们测试了很多看起来很相似的短文本的距离确实是10。如果距离为3，则不会过滤掉短文本中大量重复的信息。如果距离为10，长文本的错误率也很高。如何解决？原文链接：
