給定兩個標識符序列，如何找到將第一個標識符序列轉換爲第二個序列的最小操作序列。Diff的兩個序列標識符
操作可以是：
注插入的標識符：標識符是唯一的，不能在序列中出現兩次
示例：
Sequence1 [1, 2, 3, 4, 5]
Sequence2 [5, 1, 2, 9, 3, 7]
Result (index are 0 based) :
- Remove at 3
- Move from 3 to 0
- Insert '9' at 3
- Insert '7' at 5
謝謝！
先找到longest common subsequence。這將識別不會移動的元素：
[(1), (2), (3), 4, 5]
LCS的元素括在括號內。
瀏覽索引0中的兩個序列，記錄使序列相同所需的操作。如果第一個序列的當前項目不是LCS的一部分，請將其刪除，並標記之前的位置，以防需要稍後插入。如果當前元素是LCS的一部分，請將第二個序列中的元素插入它的前面。這可能是簡單的插入或移動。如果您要插入的項目位於原始列表中，請將其移動;否則，將其作爲插入。
這是一個使用你的例子的演示。大括號顯示當前的元素
[{(1)}, (2), (3), 4, 5] vs [{5}, 1, 2, 9, 3, 7]
1是LCS的成員，所以我們必須插入5。 5是按照原來的順序，所以我們記錄一招：MOVE 4 to 0
[5, {(1)}, (2), (3), 4] vs [5, {1}, 2, 9, 3, 7]
項目都是一樣的，所以我們進入到下一個：
[5, (1), {(2)}, (3), 4] vs [5, 1, {2}, 9, 3, 7]
同樣的數字是相同的 - 移動到下一個：
[5, (1), (2), {(3)}, 4] vs [5, 1, 2, {9}, 3, 7]
3是LCS的成員，所以我們必須插入9。原來的元素沒有9，所以這是一個簡單的插入：INSERT 9 at 3
[5, (1), (2), 9, {(3)}, 4] vs [5, 1, 2, 9, {3}, 7]
又一次的數字是相同的 - 移動到下一個：
[5, (1), (2), 9, (3), {4}] vs [5, 1, 2, 9, 3, {7}]
「4」是不是成員LCS的，所以它被刪除：DEL at 5
[5, (1), (2), 9, (3)] vs [5, 1, 2, 9, 3, {7}]
我們到達第一個序列的結尾 - 我們只需添加第二個序列的其他商品，TH第一個，注意先前刪除的清單。例如，如果7先前已被移除，那麼此時我們會將該刪除轉換爲移動。但由於原始列表沒有7，我們記錄了我們的最終操作：INS 7 at 5。
此度量稱爲Levenshtein distance或更準確地說Damerau–Levenshtein distance。
幾乎所有可能的編程語言都有實現，您可以使用它來解決您所描述的問題。
不完全 - Levenshtein距離沒有「移動」操作，它的核心動態規劃問題相同，但實現將有所不同 – BrokenGlass 2012-02-07 14:29:17
Damerau-Levenshtein允許移位。 – 2012-02-07 14:31:36
謝謝你的回答。做一個序列中唯一的標識符是否允許更快的算法？性能在這裏是一個真正的問題，因爲序列可以包含標識符的hunderds。 – 2012-02-07 14:45:00
太棒了！我能否利用序列中唯一的標識符來優化LCS算法？ – 2012-02-07 15:36:28
@NicolasRepiquet您可能會根據兩組之間交集的大小而定。如果交點很小，也就是說，不超過序列長度的70％，那麼可以解決僅由兩個序列的共同值組成的子序列的問題，以便實現2x加速。但是，你不能在LCS中獲得很多速度，因爲它需要在嵌套循環中準備整行數據，並且內循環的步驟'j'處的值取決於步驟' j-1'是正確的。 – dasblinkenlight 2012-02-07 15:53:18