网络爬虫在爬完网页后需要计算网页之间的相似度以进行排序等步骤，如何快速计算文本之间的相似度呢？
- 最Brute-force的方法是逐字比较字符是否相同，然后统计结果
- 更好一点的办法可以计算文本间的编辑距离，这是一个很好的办法，但是在文本很长，数据量很大时，时间和空间复杂度还是非常可观的
- 对文本进行分词，抽取特征向量（一般使用TF-IDF，Iterm Frequency-Inverse Document Frequency），然后通过两个特征向量之间的余弦夹角来衡量两个文本的相似度，这种算法几何意义明确，计算复杂度也不是很高，是一种非常好的算法
- 如果需要处理海量数据，就需要采用一些降维技术，本文中的Simhash算法就适合于计算海量文本相似度的场景
Simhash介绍
Simhash是一种局部敏感的哈希算法（locality sensitive hash，LSH），采用了降维技术，将高维的特征向量降低到固定个bit位中。使用Simhash算法计算文本相似度的流程如下：
- 将一个 f 维的向量 V 初始化为0；f 位的二进制数 S 初始化为0；
- 对每一个特征：用传统的 hash 算法对该特征产生一个 f 位的签名 b。
- 对 i=1 到 f：如果 b 的第 i 位为1，则 V 的第 i 个元素加上该特征的权重；否则，V 的第 i 个元素减去该特征的权重。
- 如果 V 的第 i 个元素大于0，则 S 的第 i 位为1，否则为0；
- 输出 S 作为签名。
这个算法相当于随机产生了f个n维超平面，每个超平面将向量v所在的空间一分为二，v在这个超平面上方则得到一个1，否则得到一个0，然后将得到的f个0或1组合起来成为一个f维的签名。如果两个向量u, v的夹角为θ，则一个随机超平面将它们分开的概率为θ/π，因此u, v的签名的对应位不同的概率等于θ/π。所以，我们可以用两个向量的签名的不同的对应位的数量，即汉明距离，来衡量这两个向量的差异程度。