simhash-海量数据（文章、网页）场景下如何比较相似度

原贴：simhash

比较相似度一般的做法都是：
1.生成特征向量，（例1.对文章分词，然后给每个词算权重，权重作为向量，其中权重可以是词出现的次数；例2.对文档建hash）
2.计算向量之间的距离（欧氏距离、海明距离或者夹角余弦等等），这个对例2不太适用，因为传统hash中（例如md5），距离近不代表文档相似。

所以，我们有两个任务：
1.hash值的相似程度要能直接反映输入内容的相似程度；
2.最好避免两两计算距离（因为是海量数据）。

如何建立hash？

这个过程最终就是生成01表示的特征向量。稍微说明一下，这里建hash的时候，是类似词向量的做法，所以hash距离和真正的距离还是比较能正向相关的。

如何计算距离？

根据经验，一般向量是64位的话，海明距离在3以内的可认为相似度比较高。那么这里就需要计算距离，这里有个Trick：

本来海明距离只要把两个向量异或就行，但是，如何在海量的样本库中查询与其海明距离在3以内的记录呢？直观的想法一般是两种：
1.枚举出距离为3的所有可能，大概4万种，然后查询，时间复杂度比较高；
2.先预生成好这些可能，那么存储空间需要比原来大4万倍。

这里的Trick用了抽屉原理：只有3位不同，那么把这个向量等分为4块，每块16位，一定有一块是完全相同的。这个时候，只要对这4块每块建立一个索引即可。这样，需要计算距离的数据量就变成了原来的1/2^16.