algorithm - 高级序列比对

Question

假设以下剽窃生成模型:

抄袭者:1.删​​除部分文字2.重新排列部分文本3. 添加新文本。

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

此外，剽窃者会添加小错误(插入、替换和删除的比例很小)。

我们如何着手检测这种剽窃行为？

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

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

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

Answer 1

有许多算法可以为许多应用程序执行此操作。据我所知，他们主要做的(以及你想做的)是计算编辑距离: http://en.wikipedia.org/wiki/Edit_distance

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

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