nlp

使用 Simhash 进行流式文本消重

Posted on by 逸飞

要判断两篇文章是否相同，我们可以使用文章的 md5 来判断。但是，一般情况下，文章可能只是改动了一小部分，在搜索引擎中，这种情况是非常常见的，所以需要一种算法来检测相似的文章（near-duplicate)。Simhash 是一个相似度散列算法，也就是说内容相似的文本会产生近似的哈希值。Google 就使用 simhash 作为网页判重的标准。

Simhash 通常采用 64-bit 的数字来作为一个文章的代表，而当两个文章的哈希值差异小于等于 3 位的时候，也就是汉明距离小于等于 3 的时候。

simhash 计算过程

生成 shingle, n-shingling 就是把一个句子或者文章分成 n 个连续单词的组合，然后去重。

比如： the cat sat on the cat

第一步，分组： the cat, cat sat, sat on, on the, the cat
第二步，去重： the cat, cat sat, sat on, on the

文章相似度的检测主要分为两个部分：

  1. 哈希值的构建，也就是 simhash 的算法
  2. 查询系统，给定一篇文章，我们需要查询与他 hash 值类似的文章。

对于中文的 Simhash 计算，首先需要的是分词。但是，不同的分词软件，甚至不同的版本，可能产生截然不同的词，这也就会导致同一个文本计算出来的 Simhash 都不一样。考虑到算法的稳定性，分词并不是一个很好的方案，还不如直接用 3-gram.

工程实现

整个工程实现需要以下几个步骤：

  1. 文本预处理
  2. 倒排索引建立
  3. 查询索引建立 group

    4. 4.

参考

  1. http://matpalm.com/resemblance/jaccard_coeff/
  2. http://blog.csdn.net/c289054531/article/details/8082952
  3. 这篇文章一般，有很多谬误
  4. 唯一一篇讲明白了 LSH 原理的文章，如何从高位到低维映射的同时保留相似性
  5. https://github.com/1e0ng/simhash