本人认为hash算法的本质就是以小的东西代替大的东西，并满足代替之前的某种关联，从而达到简化运算，进而提高性能的目的。simhash的输入是一个向量，输出是一个f位的签名值。方便起见，假设输入的是一个文档的特征集合，每个特征有一定的权重。比如文档的特征为n维，每一个特征向量对应一个f位的签名b（这个可以做传统的hash算法产生），那么即产生了b1，b2，b3，....等签名。备注：每一个特征的权重分别为w1,w2,w3，，，，那么：

向量V(f维)<--0,  S(f位的二进制数)<--0：
for i<--1 to f
         if b(i)(b的第i位)==1
                  v(i)+w                (其中b为特征向量，v(i)为v的第i维，w为b的权重)
         else
                 v(i)-w
for i<--1 to f
        if v(i)>0
                 S(i)=1
        else
                 S(i)=0
return S


这个算法实际上很简单，根据最开始的前面b1，b2，，，，等，V=w1b1+w2b2+....+wnbn,所以v的每一位都是w的代数差，非0加运算，零为减运算，最后得到一个f维的v向量，再做0-1标准化，即v>0置为1，其他的置为0，得S=(0,1,0,0,....,1)


lsh算法即为位置敏感hash，与一般的hash函数不同的是具有位置敏感性，也就是散列前的相似点经过hash后，也能够在一定程度上相似，并且具有一定的概率保证。这个特性非常重要，应用的地方非常多。例如图像搜索，信息检索中，在这些应用中，我们首先需要对数据进行预处理，处理出来的数据往往都是高维向量，而我们想要的搜索也好检索也好，无非是根据一个向量找一个或者多个相似的向量，这种相似性很多地方体现为距离的接近性，也就是两个高维向量的距离。因此，lsh算法的关键在于两个函数，一个是距离函数，一个是hash函数，距离可以是欧式空间距离也可以是其他度量空间的距离，距离函数选取的好坏直接影响到hash前后的敏感性。hash的选取是一个难点，除了已知的几种方法本人感觉还没有什么好的办法，这种可能主要是通过实验来测定，诸位有什么想法也可以和我互相交流。
上面提到的lsh的应用实际就是knn邻近查询，传统的knn查询中的算法主要是基于空间树的界分法，比如kd-tree,vp-tree，这种方法对于低维度的数据来说具有很大的优势，处理迅速方便，通过三角形原理能够减少一半的搜索量，搜索结果也很精确，但是一旦数据超过某个维度，这种方法反而不如线性搜索来的快，因为分支的交集太多了。
lsh的算法原理是如维度无关的，所以不会出现上面的问题，唯一的就是索引结构可能臃肿了，目前有很多人专注提出基于lsh的优化算法。

发这个帖让我很蛋疼，总是提交的时候字体突然变成斜体了，好几次这样，然后写那个伪代码的时候，b(i),v(i),s(i),实际上小括号都是中括号[],你问为啥不写中括号，无奈啊，每次写完提交过后中括号就不见了，还试过了用加代码的方式，发现特别难看还是算了，大家将就着看吧，变字体是莫名其妙的，

Gass_314 发表于 2012-6-18 12:00
发这个帖让我很蛋疼，总是提交的时候字体突然变成斜体了，好几次这样，然后写那个伪代码的时候，b(i),v(i), ...

中括号不显示的原因是，可能有些代码，比如隐藏代码，多媒体代码是用中括号的，所以就识别了。
用加代码的方式感觉还好，就是有点小，难看倒不难看，呵呵。

看不太明白

哪里有问题？

封贴必回，回帖又不会怀孕

封贴必回，回帖又不会怀孕

技术贴 不错