Simhash and MinHash

发表于

最近学习了两种LSH (Locality-sensitive Hashing) 的算法: SimHash和MinHash. 在这里总结一下。

SimHash

故事的背景是如何从海量的数据（比如网页）中挑选出相似的数据。

  1. 对每个数据提取\(n\)个带有权重的\(feature\). 那么可以得到：

    \[\{ f_{1}, f_{2}, … , f_{n} \}\]

    每个\(feature\)都会有自己的\(weight\), 即

    \[\{ w_{1}, w_{2}, ... , w_{n} \}\]

  2. 选取一种Hash function, 对每个feature进行运算，\(h_{i} = hash(f_{i})\). 可以得到:

    \[\{ h_{1}, h_{2}, … , h_{n} \}\]

    每一个\(h_{i}\)都是固定长度的bytes. 一般为64bits或者128bits.

  3. 对每个\(h_{i}\)的每位bit进行加权运算。比如有：

    \[\{ h_{1}=1010, h_{2}=1100 \}, \{w_{1}=2, w{2}=4 \}\] \[h_{1}* w_{1} + h_{2}*w_{2} => (2)(-2)(2)(-2) + (4)(4)(-4)(-4) => (6)(2)(-2)(-6) => 1100\]

    得到的结果1100就是这个数据的指纹\(s_{i}\). 对所有的指纹进行汉明距离的计算，可以将汉明距离少于等于3的两个\(s\)视为相似。

那么现在的问题就转化为：对于给定的\(s_{i}\), 如何在大量的64bits的指纹集合\(S\)中，快速找到汉明距离不超过3的。

  1. 对于集合\(S\)中的每个指纹（64bits），分成4段，每一段的长度为16bits. 对其建立索引。 (可以想象成将\(S\)整个复制成4份，对于每份分别建立索引：对第一份就first 16bits建立索引。对第二份就second 16bits建立索引。以此类推。)

  2. 对于给定的指纹\(s\)，同样将其分成4段。如果要找出找到汉明距离不超过3的\(s'\)，则可以肯定的一点是“在这4段中，至少有一段 \(s\)与\(s'\)是一样的”。

  3. 分别对\(s\)的4段指纹片段进行索引查找。找到之后对剩下的48bits的指纹进行汉明距离的计算，将距离少于3的返回存为就结果。

  4. 将4段不同的指纹片段的查找结果汇总、去重，即为最后答案。

如果是最naive的方法挨个比较的话，复杂度为\(O(n*m)\). \(n\)为数据个数，\(m\)为指纹长度。这里可视为\(n=2^{64}, m=64\). 在采取的上面的方法后，复杂度降为\(O(4* log(2^{m/4}) * n^{\frac{3}{4}} * \frac{3}{4} * m ) = O(n^{\frac{3}{4}} * m^2)\)

MinHash

TODO:Doc it.