在大型数据集中检测重复/相似的文本？

Question

我有一个包含数千条记录的大型数据库。每次用户发布他的信息时，我都需要知道是否已经有相同/相似的记录。有没有任何算法或开源实现来解决这个问题？

我们使用的是中国，什么“相似”指的是记录具有最相同的内容，可能是80％-100％是相同的。每个记录不会太大，大约2k-6k字节

Answer 1

http://d3s.mff.cuni.cz/~holub/sw/shash/

http://matpalm.com/resemblance/simhash/

Answer 2

这个答案是一个非常复杂的类（最糟糕的情况下，它是五重奏，预计它是四次验证您的数据库的第一次，然后四/立方米添加一个记录），所以它不能很好地扩展，遗憾的是我现在没有更好的答案。

该算法被称为Ratcliff-Obershelp algorithm，它在python的difflib中实现。该算法本身是立方时间最坏情况和二次预期。那么你必须为每个可能的记录对做到这一点，这是二次的。当添加记录时，当然，这只是线性的。

编辑：对不起，我看错文档，difflib只有二次，而不是三次。使用它而不是其他算法。我已经习惯了做同样的事情

Answer 3

一种方法是建立在平时的搜索索引基于词的统计数据，然后使用新的项目，如果它是针对索引的搜索 - 如果分数在顶部的项目搜索过高，则新项目太相似。毫无疑问，一些标准的文本搜索库可以用于这个，但如果它只有几千条记录，那么构建自己的记录是相当微不足道的。

Answer 4

看shngle分钟散列技术。这是一个presentation，可以帮助你。