给定两个标识符序列，如何找到将第一个标识符序列转换为第二个序列的最小操作序列。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