理解 simhash（局部敏感映射）

看了一堆的资料，就这篇 @linecong 写的《理解 GOOGLE SIMHASH 算法原理》讲到点子上了。

让我们回到原点，我们想要干成个什么事呢？我们想要找到一种文本指纹，这种指纹满足这么些个条件：

• 确定性：只要文本相同，做出来的指纹就一定相同。不会今天这个样，明天那个样。
• 相似性：如果文本长得差不多，那么做出来的指纹也长得差不多。

当然，如果这种算法足够高效，那就更好了。

这里面有个问题：怎么评判文本的相似度呢？又怎么衡量指纹的相似度呢？呃~~这个问题先放一放。

我们先来看这样一种做法：假设我们要给「你妈妈喊你回家」做指纹。

1. 拆分文本成一组特征：「你」「妈妈」「喊」「你」「回家」。
2. 然后随便找个映射，把这组特征映射到 2 维平面上去。这样，我们就得到了一组向量。
3. 接着把这组向量加起来，这个向量就是指纹

我们先随便构造一张映射表吧：

特征	坐标
你	(1, 1)
妈妈	(1, -1)
喊	(1, -1)
回家	(-1, 1)

那么原文本就变成了：(1, 1) + (1, -1) + (1, -1) + (1, 1) + (-1, 1) = (3, 1) 。

现在，我们再做一句「你妈妈喊你妈妈」：(1, 1) + (1, -1) + (1, -1) + (1, 1) + (1, -1) = (5, -1) 。这两个向量的夹角大概是 30°，算是比较接近。

改进

现在，我们嫌算向量夹角太麻烦，改用「和向量所在象限」作为指纹。
因为「你妈妈喊你回家」的和向量 (3, 1) 位于第一象限，而「你妈妈喊你妈妈」的和向量 (5, -1) 位于第四象限，和「你妈妈喊你回家」的指纹「第一象限」毗邻。我们就认为这两句很相似。

缺陷

可能你已经发现了这种算法的缺陷：这样算出来的指纹其实和「特征组的顺序」是没有关系的，因为向量的加法满足交换律。不过它倒是能满足「同样的文本生成的指纹一定相同」这点。这个问题是怎么解决的呢？

答案是「不用解决」，用同样的特征向量组合出同样、且「有意义」的句子，这种概率实在太小了：

%w[你 妈妈 喊 你 回家].permutation.to_a.uniq.map { |e| puts e.join }

排列	有意义？
你妈妈喊你回家	√
你妈妈喊回家你	×
你妈妈你喊回家	×
你妈妈你回家喊	×
你妈妈回家喊你	√
你妈妈回家你喊	×
你喊妈妈你回家	√
你喊妈妈回家你	×
你喊你妈妈回家	√
你喊你回家妈妈	×
你喊回家妈妈你	×
你喊回家你妈妈	×
你你妈妈喊回家	×
你你妈妈回家喊	×
你你喊妈妈回家	×
你你喊回家妈妈	×
你你回家妈妈喊	×
你你回家喊妈妈	×
你回家妈妈喊你	√
你回家妈妈你喊	×
你回家喊妈妈你	×
你回家喊你妈妈	√
你回家你妈妈喊	×
你回家你喊妈妈	√
妈妈你喊你回家	×
妈妈你喊回家你	×
妈妈你你喊回家	×
妈妈你你回家喊	×
妈妈你回家喊你	×
妈妈你回家你喊	×
妈妈喊你你回家	√
妈妈喊你回家你	×
妈妈喊回家你你	×
妈妈回家你喊你	×
妈妈回家你你喊	×
妈妈回家喊你你	×
喊你妈妈你回家	√
喊你妈妈回家你	×
喊你你妈妈回家	×
喊你你回家妈妈	×
喊你回家妈妈你	×
喊你回家你妈妈	√
喊妈妈你你回家	×
喊妈妈你回家你	×
喊妈妈回家你你	×
喊回家你妈妈你	×
喊回家你你妈妈	×
喊回家妈妈你你	×
回家你妈妈喊你	√
回家你妈妈你喊	×
回家你喊妈妈你	×
回家你喊你妈妈	×
回家你你妈妈喊	×
回家你你喊妈妈	×
回家妈妈你喊你	×
回家妈妈你你喊	×
回家妈妈喊你你	×
回家喊你妈妈你	×
回家喊你你妈妈	×
回家喊妈妈你你	×

去重以后 60 种，有意义的勉强 11 种，18% 的概率。随着文本的增长，我敢打包票，有意义的概率呈指数衰减。

回到算法

现在再去看算法，就一清二楚了吧。懒得写了……

对了，原算法里面，每个特征向量是要乘一个权重的。

---

论文原文在这。但不推荐去看。

强烈推荐大家仔细去读读 @linecong 那篇《理解 GOOGLE SIMHASH 算法原理》。里面提出的「 simhash 其实是「随机超平面算法」的变种」以及「「随机超平面算法」为何能够描述文本相似程度」等内容让人惊叹😱 原来还可以辣么简单、辣么美！！！