algorithm - Copyscape 使用什么算法进行文本比较？

Question

所以我一直在寻找一种算法来比较文本内容，我发现这个名为 Copyscape 的网站有一个非常方便的工具用于比较文章 (link)。它似乎在检测 2 个文本文档之间的相似性值(按百分比)方面做得很好。我想知道他们在该工具中使用了哪种算法，或者类似的算法？提前致谢。

Answer 1

我不确定 copyscape 剽窃是如何运作的。但是如果你让我实现一个。

我将从 - 定义“剽窃”开始？ content-1 和 content-2 几乎相似。让我们说 >80% 是相同的。即 content-1 被 20% 更改为 content-2。

现在，让我们尝试解决:将 content-1 转换为 content-2 的成本(更改次数)是多少？这是 DP(动态规划世界)中众所周知的问题 Levenshtein distance或 EDIT Distance问题。标准问题讨论的是字符串距离，但您可以轻松地将其修改为单词而不是字符。此外，您可能需要跟踪所有更改 @ line #，两个内容上的单词位置。

现在，上述问题将为您提供从 content-1 到 content-2 的Least no.of changes for conversion。使用 content-1 的总长度，我们可以轻松计算出从 content-1 到 content-2 的更改百分比。如果低于固定阈值(比如 20%)，则宣布剽窃。此外，借助行# 上的辅助信息，两个内容上的单词位置 - 您可以显示所做的更改。