nlp

使用 Simhash 进行流式文本消重

要判断两篇文章是否相同,我们可以使用文章的 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