两种方式的比较:
这里先引入一个概念: 抽屉原理
假设我们要寻找海明距离3以内的数值,根据抽屉原理,只要我们将整个64位的二进制串划分为4块,无论如何,匹配的两个simhash code之间 至少 有一块区域是完全相同的,如下图所示:
由于我们无法事先得知完全相同的是哪一块区域,因此我们必须采用存储多份table的方式。在本例的情况下,我们需要存储4份table,并将64位的simhash code等分成4份;对于每一个输入的code,我们通过精确匹配的方式,查找前16位相同的记录作为候选记录,如下图所示:
让我们来总结一下上述算法的实质: 假定我们最大判重海明距离为MAX_HD 1、将64位的二进制串等分成MAX_HD+1块 2、PUT操作:调整上述64位二进制,将任意一块作为前16位,总共有MAX_HD+1种组合,生成MAX_HD+1份table 3、GET操作:采用精确匹配的方式在MAX_HD+1份table中查找前16位,若找不到,说明不重复,做PUT操作;若找到了,则对剩余链做海明距离计算。 4、如果样本库中存有2^34 (差不多10亿)的哈希指纹,则每个table返回2^(34-16)=262144个候选结果,大大减少了海明距离的计算成本
为何要分桶? 两个字符串通过SimHash码和海明距离比较好判断是否相似,假设计算海明距离的时间为基本操作时间。如果有海量的数据,一一比较计算的次数为 1 + 2 + 3 + ......+ n ,时间复杂度为 O(n^2) 级别。这样的时间复杂度肯定是不能接受的。
构建索引
将SimHashCode添加到索引
查询与索引库中比较的最近的海明距离
其中 bit[n] = 2^n ,索引降低比较时算法时间复杂度的方法是 将SimHashCode 比特位分成8段
其实这里也是用上了抽屉原理的,各位看官自己思考下吧。
分词 -->另写一篇博客说明
需要说明的一点: 分词的时候需要去掉停用词等噪音词,分词是该算法特征抽取的关键一步。