高级序列比对

Question

假设以下抄袭的生成模型：

抄袭者： 1. 删除文本的一部分 2. 重新排列文本的一部分 3. 添加新的文本。

例如，如果ABCD是原始文本(A、B、C和D可以是段落或一堆句子)，输出可以是DEAFCG，其中E、F和G是添加的附加文本。

此外，抄袭者会以较小的概率添加小错误(插入、替换和删除)。

我们如何检测这种抄袭实例？

到目前为止，我已经尝试使用最长公共子序列方法。它会检测到一组匹配的线性文本。在上面的示例中，它将检测到D或AC(取决于它们的长度)

我需要的是：处理此问题的有原则的方法。任何对现有文献的引用都将非常有帮助。对于想法的伪代码也很好。不要提供代码。

这既不是作业问题，也不是面试问题。我将我的实际问题简化成了这个玩具问题。

- ElKamina

---

根据您一些敏锐的回答，我想如果您在提问，那肯定是一个具有挑战性的问题！这里有一篇您可能看过的文章 - http://en.wikipedia.org/wiki/Plagiarism_detection - גלעד ברקן

Answer 1

有许多算法可用于各种应用程序的此类操作。据我所知，它们主要做的事情（也是您想要做的）是计算编辑距离： http://en.wikipedia.org/wiki/Edit_distance

根据 http://en.wikipedia.org/wiki/Levenshtein_distance#Relationship_with_other_edit_distance_metrics， 有许多略有不同的不同算法：

例如，最长公共子序列处理添加和删除但不处理替换； Damerau-Levenshtein距离还考虑了替换以及相邻字符的转置。

- maditya

---

我已经实现了使用编辑距离的最长公共子序列，但它无法处理重定位（例如 ABC 到 CAB）。 - ElKamina

据我所知，编辑距离有不同的算法，处理不同的情况（例如替换、转置）。 - maditya

但这是大规模的转置。A、B、C是大段或一堆句子，而不是一个字母。 - ElKamina

在这种情况下，我唯一能建议的想法是采用某种分层方法。例如：（1）通过将整个段落哈希化为唯一值来对输入字符串进行标记化，因此现在您拥有由这些标记（其中每个标记实际上代表整个段落）组成的字母表；（2）对标记序列执行最长公共子序列/编辑距离/任何其他操作。 - maditya

@maditya 唯一的问题是，在这些段落内部也可以进行更改，因此哈希值可能不匹配。而且可能是整个段落、句子或句子的一部分被重新排列，这就更复杂了。 - Bernhard Barker