汉明距离
《海量数据相似度计算之simhash和海明距离》介绍了simhash的原理。 你应该感受到了算法的魅力。 但是，随着业务的发展，simhash的数据也急剧增加，每天100w的话，10天就变成1000w。 插入一个数据后，需要比较1000w次的simhash，但计算量相当大，在普通PC上比较1000w次的汉明距离需要1.8 s才能与300ms、5000w数据进行比较。 相似度的计算并不太慢，似乎还处于秒级。 给大家算账就知道了。
随着业务的发展，每小时需要处理100w次，1小时为3600 *1000=360w毫秒，一次相似度比较最多可消耗360w/100w=3.6毫秒。 300ms慢还是慢！ 1.8S慢吗，太慢了！ 大多数情况下，考虑的是升级、增加机器，但也有仅靠增加机器无法解决的情况。 增加机器并不能在短时间内解决问题，是否需要考虑分布式、客户预算和解决问题的允许时间？ 脑子里要相信人类的智慧是无限的。 沏茶，听听轻音乐。 )宇宙的大小，宇宙之外有什么，程序员无论有什么问题都很难倒下吗？
除了客户提出的一些建议外，我还将总结一些技术问题。
1、每小时需要比较100w次。 这意味着每个数据与simhash库的数据比较必须为3.6毫秒。
2、同一时刻发行的两个文本即使重复也只剩下一个。
我想留三两天的数据比较重。 根据目前的订单和未来的增长情况，两天时间大概在2000w — 5000w之间。
4、短文本和长课文都要重。 经过测试较长的文本使用simhash效果较好，短文本使用simhash的准备程度不高。
现在，估算一下存储区域的大小，在JAVA中，存储simhash需要64位=8 byte的原始lang类型，在Object对象的情况下需要额外的8 byte，所以尽可能节约地使用原始lang 假设增长到最大的5000w数据，则5000 w *8byte=400000000 byte=40000000/(1024 * 1024 )=382 Mb，因此普通PC服务器可以支持此大小。 这样就解决了第三个问题。
比较5000w次如何减少时间？ 其实这也是寻找的过程。 想想以前学过的检索算法吧。 顺序检索、二分检索、二叉排序树检索、索引检索、mldqb检索。 但是，我们比较的不是数字是否相同，而是汉明距离。 以前的算法不太通用，但解决问题的过程都是共通的。 和以前一样，不使用公式，而使用编程猴子大家都理解的方式。 还记得JAVA里有HashMap吗？ 查找key的值时，通过传递key可以立即返回value。 这个据说检索速度最快的数据结构是如何实现的呢？ 让我们看看hashmap的内部结构：
java hashmap内部结构
如果需要得到与key对应的value，经过这些计算后传递到key，计算key的hashcode，需要得到7个位置。如果知道还有几个与7个位置对应的value，就在找到v72之前，一直传递到链表其实通过这样分析，如果我们的hashcode设定不充分，hashmap的效率也未必高。 参考这个算法，设计我们的simhash检索。 按顺序找是绝对不行的。 是否可以像hashmap一样，首先通过键-值对减少顺序比较次数？ 请看下图：
大规模simhash算法的优化
存储：
1 .将64位simhash code拆分为4个16位二进制代码。 (图上的红色16位)
2、分别具有四个16位二进制码，查找当前对应位置是否存在元素。 (放大的16位)
3、对应位置没有元素，如果有直接添加到链表中的对应位置，则直接添加到链表的末尾。 (图中的S1 — SN ) ) ) ) ) ) ) ) ) )图中的S1 — SN ) ) ) ) ) ) )图中的S1 — SN ) ) ) ) ) ) )
搜索：
1 .将要比较的simhash code分成4个16位二进制代码。
2、每个都有四个16位二进制代码，查找simhash集合中相应的位置是否有元素。
2、有要素时，取出链表按顺序查找比较，直到simhash小于一定大小。 整个过程完成。
原理：
参考hashmap算法，找到可以hash的key值。 因为我们使用的simhash是局部敏感mldqb，所以该算法的特征是类似的字符串只有各个位数不同。 现在，您可以推断至少16位simhash相同的两个相似的文本。 具体选择16位、8位、4位，大家根据自己的数据测试选择，比较的位数越小越准确，但空间越大。 分为4个16位段的存储空间是单独simhash存储空间的4倍。 以前计算出的5000w数据为382 Mb，放大到4倍的1.5G左右，还可以接受：)
通过这样计算，我们的simhash搜索过程都变成了1毫秒以下。 hash效果这么厉害吗？ 让我来计算一下。 原本是5000w次的顺序比较，现在是减少了2的16次方比较，前面的16位变成了hash检索。 按照后面的顺序比较的个数是多少？ 2 ^ 16=65536，5000 w/65536=763次。 实际链表比较的数据也只有763次！ 所以效率大幅提高了！
目前，第一点下降到3.6毫秒，完成了5000w数据相似度的比较。 另外，即使同一时刻发送的文本重复，与短文本的相识度比较如何解决也只能留下一条。 其实上面
的问题解决了，这两个就不是什么问题了。之前的评估一直都是按照线性计算来估计的，就算有多线程提交相似度计算比较，我们提供相似度计算服务器也需要线性计算。比如同时客户端发送过来两条需要比较相似度的请求，在服务器这边都进行了一个排队处理，一个接着一个，第一个处理完了在处理第二个，等到第一个处理完了也就加入了simhash库。所以只要服务端加了队列，就不存在同时请求不能判断的情况。
simhash如何处理短文本？换一种思路，simhash可以作为局部敏感mldqb第一次计算缩小整个比较的范围，等到我们只有比较700多次比较时，就算使用我们之前精准度高计算很慢的编辑距离也可以搞定。当然如果觉得慢了，也可以使用余弦夹角等效率稍微高点的相似度算法。
通过 采集系统 我们采集了大量文本数据，但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复，如何选择和设计文本的去重算法？常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用，如果我们的爬虫每天采集的数据以千万计算，我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复。看起来很简单，我们来做个测试，就拿最简单的两个数据使用Apache提供的 Levenshtein for 循环100w次计算这两个数据的相似度。代码结果如下：
String s1 = "你妈妈喊你回家吃饭哦，回家罗回家罗" ; String s2 = "你妈妈叫你回家吃饭啦，回家罗回家罗" ; long t1 = System.currentTimeMillis(); for (int i = 0; i < 1000000; i++) { int dis = StringUtils .getLevenshteinDistance(s1, s2); } long t2 = System.currentTimeMillis(); System. out .println(" 耗费时间： " + (t2 - t1) + " ms ");耗费时间： 4266 ms
大跌眼镜，居然计算耗费4秒。假设我们一天需要比较100w次，光是比较100w次的数据是否重复就需要4s，就算4s一个文档，单线程一分钟才处理15个文档，一个小时才900个，一天也才21600个文档，这个数字和一天100w相差甚远，需要多少机器和资源才能解决。
为此我们需要一种应对于海量数据场景的去重方案，经过研究发现有种叫 local sensitive hash 局部敏感mldqb 的东西，据说这玩意可以把文档降维到hash数字，数字两两计算运算量要小很多。查找很多文档后看到google对于网页去重使用的是simhash，他们每天需要处理的文档在亿级别，大大超过了我们现在文档的水平。既然gddsc也有类似的应用，我们也赶紧尝试下。simhash是由 Charikar 在2002年提出来的，参考 《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理，为了便于理解尽量不使用数学公式，分为这几步：
1、分词，把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重，我们假设权重分为5个级别（1~5）。比如：“ 美国“51区”雇员称内部有9架飞碟，曾看见灰色外星人 ” ==> 分词后为 “ 美国（4） 51区（5） 雇员（3） 称（1） 内部（2） 有（1） 9架（3） 飞碟（5） 曾（1） 看见（3） 灰色（4） 外星人（5）”，括号里是代表单词在整个句子里重要程度，数字越大越重要。
2、hash，通过hash算法把每个词变成hash值，比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字，还记得文章开头说过的吗，要把文章变为数字计算才能提高相似度计算性能，现在是降维过程进行时。
3、加权，通过 2步骤的hash生成结果，需要按照单词的权重形成加权数字串，比如“美国”的hash值为“100101”，通过加权计算为“4 -4 -4 4 -4 4”；“51区”的hash值为“101011”，通过加权计算为 “ 5 -5 5 -5 5 5”。
4、合并，把上面各个单词算出来的序列值累加，变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”，“51区”的 “ 5 -5 5 -5 5 5”， 把每一位进行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的，真实计算需要把所有单词的序列串累加。
5、降维，把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串，形成我们最终的simhash签名。 如果每一位大于0 记为 1，小于0 记为 0。最后算出结果为：“1 0 1 0 1 1”。
整个过程图为：
simhash计算过程图
大家可能会有疑问，经过这么多步骤搞这么麻烦，不就是为了得到个 0 1 字符串吗？我直接把这个文本作为字符串输入，用hash函数生成 0 1 值更简单。其实不是这样的，传统hash函数解决的是生成唯一值，比如 md5、hashmap等。md5是用于生成唯一签名串，只要稍微多加一个字符md5的两个数字看起来相差甚远；hashmap也是用于键值对查找，便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算，要比较的是两个文章是否相识，当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了，我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的，而传统的hashcode却不行。我们可以来做个测试，两个相差只有一个字符的文本串，“你妈妈喊你回家吃饭哦，回家罗回家罗” 和 “你妈妈叫你回家吃饭啦，回家罗回家罗”。
通过simhash计算结果为：
1000010010101101111111100000101011010001001111100001001011001011
1000010010101101011111100000101011010001001111100001101010001011
通过 hashcode计算为：
1111111111111111111111111111111110001000001100110100111011011110
1010010001111111110010110011101
大家可以看得出来，相似的文本只有部分 01 串变化了，而普通的hashcode却不能做到，这个就是局部敏感mldqb的魅力。目前Broder提出的jadcc算法和Charikar的simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明，“量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的。
现在通过这样的转换，我们把库里的文本都转换为simhash 代码，并转换为long类型存储，空间大大减少。现在我们虽然解决了空间，但是如何计算两个simhash的相似度呢？难道是比较两个simhash的01有多少个不同吗？对的，其实也就是这样，我们通过海明距离（Hamming distance）就可以计算出两个simhash到底相似不相似。两个simhash对应二进制（01串）取值不同的数量称为这两个simhash的海明距离。举例如下： 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。对于二进制字符串的a和b，海明距离为等于在a XOR b运算结果中1的个数（普遍算法）。
为了高效比较，我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code，然后和内存里的simhash code 进行比较，测试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，长文本的错误率也非常高，如何解决？
simhash_hammingdistance