共计 3411 个字符，预计需要花费 9 分钟才能阅读完成。
本文主要介绍余下的两种文本相似度的计算方式:
simhash + 汉明距离
minhash
simhash+ 汉明距离
simhash 是 google 用来处理海量文本去重的算法。simhash 就是将一个文档，最后转换成一个 64 位的字节，然后判断重复只需要判断他们的各个字节的距离是不是 <n（n 为自定义大小，一般取 3~5），就可以判断两个文档是否相似。
simhash 算法分为 5 个步骤：分词、hash、加权、合并、降维，具体过程如下所述：
分词给定一段语句，进行分词，得到有效的特征向量，然后为每一个特征向量设置 1 - 5 等 5 个级别的权重（如果是给定一个文本，那么特征向量可以是文本中的词，其权重可以是这个词出现的次数）。
hash 通过 hash 函数计算各个特征向量的 hash 值，hash 值为二进制数 01 组成的 n -bit 签名。
加权在 hash 值的基础上，给所有特征向量进行加权，即 W = Hash weight，且遇到 1 则 hash 值和权值正相乘，遇到 0 则 hash 值和权值负相乘。
合并将上述各个特征向量的加权结果累加，变成只有一个序列串。
降维对于 n -bit 签名的累加结果，如果大于 0 则置 1，否则置 0，从而得到该语句的 simhash 值，最后我们便可以根据不同语句 simhash 的海明距离来判断它们的相似度。
具体的流程图如下:
找到了一个例子来说明具体的步骤:
首先对文本内容进行分词，去掉一些停用词后，将剩余的词语 hash 编码，然后对应的每个词进行与权重相乘的方式得到每一个词的新的 hash 编码（权重采用的词的 tf-idf 的大小作为权重），然后进行 hash 对应位置进行合并，最后对合并后的 hash 进行降维操作。
得到的每一个文档的 simhash 均为等长的 hash 编码，所以可以用汉明距离快速的计算出 n 值的大小。例如，两篇文档的 simhash 分别为: 所以该两个文本的汉明距离为 3，若 n 取 5，则可以认为这两个文本是相似的。
minhash
minhash 推荐阅读博客:http://www.cnblogs.com/bourne… 文中下面内容将参照该篇博客讲解:
问题背景: 给出 N 个集合，找到相似的集合对，如何实现呢？直观的方法是比较任意两个集合。那么可以十分精确的找到每一对相似的集合，但是时间复杂度是 O(n2)。当 N 比较小时，比如 K 级，此算法可以在接受的时间范围内完成，但是如果 N 变大时，比 B 级，甚至 P 级，那么需要的时间是不能够被接受的。
上面的算法虽然效率很低，但是结果会很精确，因为检查了每一对集合。假如，N 个集合中只有少数几对集合相似，绝大多数集合都不等呢？那么根据上述算法，绝大多数检测的结果是两个结合不相似，可以说这些检测“浪费了计算时间”。所以，如果能找到一种算法，将大体上相似的集合聚到一起，缩小比对的范围，这样只用检测较少的集合对，就可以找到绝大多数相似的集合对，大幅度减少时间开销。虽然牺牲了一部分精度，但是如果能够将时间大幅度减少，这种算法还是可以接受的。接下来的内容讲解如何使用 Minhash 和 LSH 来实现上述目的，在相似的集合较少的情况下，可以在 O(n) 时间找到大部分相似的集合对。
minhash 降维原始问题的关键在于计算时间太长。所以，如果能够找到一种很好的方法将原始集合压缩成更小的集合，而且又不失去相似性，那么可以缩短计算时间。Minhash 可以帮助我们解决这个问题。举个例子，S1 = {a,d,e}，S2 = {c, e}，设全集 U = {a,b,c,d,e}。集合可以如下表示：
表 1 中，列表示集合，行表示元素，值 1 表示某个集合具有某个值，0 则相反（X，Y，Z 的意义后面讨论）。Minhash 算法大体思路是：采用一种 hash 函数，将元素的位置均匀打乱，然后将新顺序下每个集合第一个元素作为该集合的特征值。比如哈希函数 h1(i) = (i + 1) % 5，其中 i 为行号。作用于集合 S1 和 S2，得到如下结果：
这时，Minhash(S1) = e，Minhash(S2) = e。也就是说用元素 e 表示 S1，用元素 e 表示集合 S2。那么这样做是否科学呢？进一步，如果 Minhash(S1) 等于 Minhash(S2)，那么 S1 是否和 S2 类似呢？
结论：P(Minhash(S1) = Minhash(S2)) = Jaccard(S1,S2)
在哈希函数 h1 均匀分布的情况下，集合 S1 的 Minhash 值和集合 S2 的 Minhash 值相等的概率等于集合 S1 与集合 S2 的 Jaccard 相似度，下面简单分析一下这个结论。
S1 和 S2 的每一行元素可以分为三类：
X 类 均为 1。比如表 2 中的第 1 行，两个集合都有元素 e。
Y 类 一个为 1，另一个为 0。比如表 2 中的第 2 行，表明 S1 有元素 a，而 S2 没有。
Z 类 均为 0。比如表 2 中的第 3 行，两个集合都没有元素 b。
这里忽略所有 Z 类的行，因为此类行对两个集合是否相似没有任何贡献。由于哈希函数将原始行号均匀分布到新的行号，这样可以认为在新的行号排列下，任意一行出现 X 类的情况的概率为 |X|/(|X|+|Y|)。这里为了方便，将任意位置设为第一个出现 X 类行的行号。所以 P(第一个出现 X 类) = |X|/(|X|+|Y|) = Jac(S1,S2)。这里很重要的一点就是要保证哈希函数可以将数值均匀分布，尽量减少冲撞。
一般而言，会找出一系列的哈希函数，比如 h 个（h << |U|），为每一个集合计算 h 次 Minhash 值，然后用 h 个 Minhash 值组成一个摘要来表示当前集合（注意 Minhash 的值的位置需要保持一致）。举个列子，还是基于上面的例子，现在又有一个哈希函数 h2(i) = (i -1)% 5。那么得到如下集合：
所以，现在用摘要表示的原始集合如下：
从表四还可以得到一个结论，令 X 表示 Minhash 摘要后的集合对应行相等的次数（比如表 4，X=1，因为哈希函数 h1 情况下，两个集合的 minhash 相等，h2 不等）：X 符合次数为 h，概率为 Jac(S1,S2) 的二项分布。那么期望 E(X) = h Jac(S1,S2) = 2 2 / 3 = 1.33。也就是每 2 个 hash 计算 Minhash 摘要，可以期望有 1.33 元素对应相等。
所以，Minhash 在压缩原始集合的情况下，保证了集合的相似度没有被破坏。
LSH- 局部敏感哈希现在有了原始集合的摘要，但是还是没有解决最初的问题，仍然需要遍历所有的集合对,，才能所有相似的集合对，复杂度仍然是 O(n2)。所以，接下来描述解决这个问题的核心思想 LSH。其基本思路是将相似的集合聚集到一起，减小查找范围，避免比较不相似的集合。仍然是从例子开始，现在有 5 个集合，计算出对应的 Minhash 摘要，如下：
上面的集合摘要采用了 12 个不同的 hash 函数计算出来，然后分成了 B = 4 个区间。前面已经分析过，任意两个集合（S1，S2）对应的 Minhash 值相等的概率 r = Jac(S1，S2)。先分析区间 1，在这个区间内，P(集合 S1 等于集合 S2) = r3。所以只要 S1 和 S2 的 Jaccard 相似度越高，在区间 1 内越有可能完成全一致，反过来也一样。那么 P(集合 S1 不等于集合 S2) = 1 – r3。现在有 4 个区间，其他区间与第一个相同，所以 P(4 个区间上，集合 S1 都不等于集合 S2) = (1 – r3)4。P(4 个区间上，至少有一个区间，集合 S1 等于集合 S2) = 1 – (1 – r3)4。这里的概率是一个 r 的函数，形状犹如一个 S 型，如下：
如果令区间个数为 B，每个区间内的行数为 C，那么上面的公式可以形式的表示为：
令 r = 0.4，C=3，B = 100。上述公式计算的概率为 0.9986585。这表明两个 Jaccard 相似度为 0.4 的集合在至少一个区间内冲撞的概率达到了 99.9%。根据这一事实，我们只需要选取合适的 B 和 C，和一个冲撞率很低的 hash 函数，就可以将相似的集合至少在一个区间内冲撞，这样也就达成了本节最开始的目的：将相似的集合放到一起。具体的方法是为 B 个区间，准备 B 个 hash 表，和区间编号一一对应，然后用 hash 函数将每个区间的部分集合映射到对应 hash 表里。最后遍历所有的 hash 表，将冲撞的集合作为候选对象进行比较，找出相识的集合对。整个过程是采用 O(n) 的时间复杂度，因为 B 和 C 均是常量。由于聚到一起的集合相比于整体比较少，所以在这小范围内互相比较的时间开销也可以计算为常量，那么总体的计算时间也是 O(n)。
参考资料
http://www.cnblogs.com/bourne…
详细代码见 github。
