Simhash算法及java实现.doc

- -

SimHash 算法及 Java 实现

传统的 算法只负责将原始容尽量均匀随机地映射为一个签名值，原理上相当于

伪随机数产生算法。产生的两个签名，如果相等，说明原始容在一定概率下是相等的；如

果不相等，除了说明原始容不相等外，不再提供任何信息，因为即使原始容只相差一个字

节，所产生的签名也很可能差别极大。从这个意义上来说，要设计一个  算法，对相

似的容产生的签名也相近，是更为艰难的任务，因为它的签名值除了提供原始容是否相等

的信息外，还能额外提供不相等的原始容的差异程度的信息。而 的 算

算法如下：

）将一个 维的向量 初始化为 ；位的二进制数 初始化为 ；

）对每一个特征：用传统的 算法对该特征产生一个 位的签名 。对 到

： 如果 的第 位为 ，则 的第 个元素加上该特征的权重； 否则，的第 

个元素减去该特征的权重。

）如果 的第 个元素大于 ，则 的第 位为 ，否则为 ；

）输出 作为签名。

2、算法几何意义和原理

- .可修编 .