相似文档查找算法之 simHash 简介及其 java 实现 - leejun_2005的个人页面 - 开源中国社区

相似文档查找算法之 simHash 简介及其 java 实现 - leejun_2005的个人页面 - 开源中国社区

0人收藏此文章, 赞6 而 Google 的 simhash 算法产生的签名，可以满足上述要求。出人意料，这个算法并不深奥，其思想是非常清澈美妙的。 1、Simhash 算法简介 simhash算法的输入是一个向量，输出是一个 f 位的签名值。为了陈述方便，假设输入的是一个文档的特征集合，每个特征有一定的权重。比如特征可以是文档中的词，其权重可以是这个词出现的次数。 simhash 算法如下： 1，将一个 f 维的向量 V 初始化为 0 ； f 位的二进制数 S 初始化为 0 ； 2，对每一个特征：用传统的 hash 算法对该特征产生一个 f 位的签名 b 。对 i=1 到 f ： 如果b 的第 i 位为 1 ，则 V 的第 i 个元素加上该特征的权重； 否则，V 的第 i 个元素减去该特征的权重。  3，如果 V 的第 i 个元素大于 0 ，则 S 的第 i 位为 1 ，否则为 0 ； 4，输出 S 作为签名。 明确了算法了几何意义，使这个算法直观上看来是合理的。但是，为何最终得到的签名相近的程度，可以衡量原始文档的相似程度呢？这需要一个清晰的思路和证明。在simhash的发明人Charikar的论文中[2]并没有给出具体的simhash算法和证明，以下列出我自己得出的证明思路。 Simhash是由随机超平面hash算法演变而来的，随机超平面hash算法非常简单，对于一个n维向量v，要得到一个f位的签名(f<

Read full article from 相似文档查找算法之 simHash 简介及其 java 实现 - leejun_2005的个人页面 - 开源中国社区