algorithm - 如何检测文本文档中的重复项并返回重复项的相似度？

Question

我正在写一个爬虫从一些网站获取内容，但是内容可以重复，我想要避免这种情况。所以我需要一个函数可以返回两个文本之间相同的百分比来检测可能重复的两个内容示例:

• 文本 1:“我正在编写一个爬虫”
• 文本 2:“我正在编写一些文本爬虫来获取”

比较函数会将文本 2 返回为相同文本 1 的 5/8%(其中 5 是文本 2 相同文本 1 的字数(按词序比较)，8 是文本 2 的总字数)。如果删除“某些文本”，则文本 2 与文本 1 相同(我需要检测情况)。我该怎么做？

Answer 1

您正面临一个在Information Retrieval 领域中已知的问题作为近似重复检测。

已知的解决方案之一是使用 Jaccard-Similarity 用于获取两个文档之间的差异。

Jaccard 相似度基本上是 - 从每个文档中获取单词集，让这些集合为 s1 和 s2 - jaccard 相似度为 |s1 [intersection ] s2|/|s1 [联合] s2|.

通常在面对几乎重复的情况时——然而单词的顺序有一定的重要性。为了处理它 - 在生成集合 s1 和 s2 时 - 你实际上生成了 k-shinglings 的集合，而不是只有单词的集合。
在您的示例中，k=2，集合将是:

s1 = { I'm write, write a, a crawler, crawler to }
s2 = { I'm write, write a, a some, some text, text crawler, crawler to, to get }
s1 [union] s2 = { I'm write, write a, a crawler, crawler to, a some, some text, text crawler, to get } 
s1 [intersection] s2 = { I'm write, write a, crawler to }

在上面，jaccard 相似度将为 3/8。如果您使用相同方法使用单个单词，(k=1 shinglings) 您将获得所需的 5/8 - 但在我(和大多数 IR 专家)看来，这是更糟糕的解决方案。

这个过程可以很好地缩放以非常有效地处理大量集合，而无需检查所有对并创建大量集合。更多详细信息，请参阅 these lecture notes (我几个月前根据作者的笔记做了这个讲座)。