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

Question

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

我们用的是中文，“相似”的意思是记录有最相同的内容，可能是80%-100%是相同的。每条记录不会太大，大约2k-6k字节

score 3 · Accepted Answer

3

于 2010-11-09T07:00:21.937 回答

score 1 · Accepted Answer

这个答案是一个非常复杂的类（最坏的情况是五次，预期的情况是四次验证您的数据库，然后是四次/三次添加记录，）所以它不能很好地扩展，不幸的是没有我现在能想到的更好的答案。

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

编辑：对不起，我误读了文档，difflib 只是二次的，而不是三次的。使用它而不是其他算法。

score 1 · Accepted Answer

1

看看 shngle-min-hash 技术。这是一个可以帮助您的演示文稿。

于 2010-11-02T14:11:04.303 回答

score 0 · Accepted Answer

我用来做类似事情的一种方法是通常基于单词统计构建搜索索引，然后使用新项目，就好像它是针对该索引的搜索一样 - 如果搜索中顶部项目的分数太高高那么新项目太相似了。毫无疑问，可以使用一些标准的文本搜索库来实现这一点，尽管如果它只有几千条记录，那么构建自己的记录就很简单了。

4 回答 4