高級序列比對

Question

承擔抄襲以下生成模型：

剽竊者： 1.刪除部分文字 2.重新排列文本 3.添加新文本的部分。

Ex。如果ABCD是原始文本（A，B，C和D可以是段落或一堆句子），則輸出可以是DEAFCG，其中E，F和G是附加文本。另外，剽竊者會添加小錯誤（插入，替換和刪除率較低）。

我們該如何去檢測這個剽竊事件？

我到目前爲止所做的：嘗試使用最長的公共子序列方法。它檢測到一組線性匹配的文本。在上面的例子中，它會檢測到D或AC（取決於它們的長度）

我需要：處理這個問題的原則性方法。任何對已有文獻的引用都會非常有幫助。任何想法的僞代碼也很好。沒有代碼請。

這既不是家庭作業，也不是面試問題。我把我的實際問題簡化成了這個棘手的問題。

Answer 1

對於許多應用程序來說，有很多這樣的算法。據我所知，他們主要是做（和你想要做什麼）是計算編輯距離： http://en.wikipedia.org/wiki/Edit_distance

有一些稍微不同的不同算法，根據 http://en.wikipedia.org/wiki/Levenshtein_distance#Relationship_with_other_edit_distance_metrics：

eg最長的公共子序列處理添加和刪除而不是替換; Damerau-Levenshtein距離也考慮到替代以及相鄰字符的換位。