要判断两篇文章是否相同,我们可以使用文章的 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
文章相似度的检测主要分为两个部分:
- 哈希值的构建,也就是 simhash 的算法
- 查询系统,给定一篇文章,我们需要查询与他 hash 值类似的文章。
对于中文的 Simhash 计算,首先需要的是分词。但是,不同的分词软件,甚至不同的版本,可能产生截然不同的词,这也就会导致同一个文本计算出来的 Simhash 都不一样。考虑到算法的稳定性,分词并不是一个很好的方案,还不如直接用 3-gram.
工程实现
整个工程实现需要以下几个步骤:
- 文本预处理
- 倒排索引建立
- 查询索引建立 group
4.
参考
- http://matpalm.com/resemblance/jaccard_coeff/
- http://blog.csdn.net/c289054531/article/details/8082952
- 这篇文章一般,有很多谬误
- 唯一一篇讲明白了 LSH 原理的文章,如何从高位到低维映射的同时保留相似性
- https://github.com/1e0ng/simhash