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

Question

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

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

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

Answer 1

您面临的问题在信息检索领域被称为Near Duplicates Detection。

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

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

通常在面对近乎重复的内容时 - 然而，单词的顺序具有一定的重要性。为了处理它 - 在生成集合时s1-s2您实际上生成了 k-shingling 集合，而不是仅生成单词的集合。
在您的示例中，使用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-similarity 将是3/8。如果您使用相同的方法使用单个单词（k=1 shinglings），您将得到您想要的5/8- 但在我（和大多数 IR 专家）看来，这是更糟糕的解决方案。

这个过程可以很好地扩展以非常有效地处理大量集合，而无需检查所有对并创建大量集合。更多细节可以在这些讲义中找到（几个月前我根据作者的笔记做了这个讲座）。

Answer 2

比较两个文本的一个很好的算法是 tf-idf。它将给出两个文档之间的相似性。

1. calculate tf-idf for the document
2. calculate cosine similarity for two given text
3. the cosine similarity will indicate match between two documents.

这是在 Java 中计算 tf-idf 和余弦相似度的非常好的教程。将其扩展到 C# 会很简单。

Answer 3

在生物信息学中，有一种算法可以完成这项工作。它被称为Needleman-Wunsch，通常用于与核苷酸序列的全局序列比对。

使用此算法，您可以轻松计算两个字符串之间的一致性。你可以使用我的代码。但是此方法仅返回您必须自己计算一致性的对齐方式。