arrays - 数组差异作为一系列 Action

Question

简而言之:我有两个可能不同的数组，我希望将差异/转换作为一系列“操作”(添加和删除)。也就是说，在一个基本示例中:

Current: [a, b, d]
Desired: [a, b, c, d]
Actions: Add c in position 2

基本上，说明是如何转换当前数组，使其具有与所需数组相同的成员和顺序。对于我的应用程序，每个更改都会触发更新 UI 等的事件，因此如果操作不是“冗余”的，那将是非常可取的:也就是说，上面的内容可能是 remove d, add c @ 2, add d @ 3，但这会在系统的其他地方引起大量不需要的处理。

也许作为另一个可能有助于说明的例子:

Current: [a, b, d]
Desired: [b, c, d, a]
Actions: remove a, add c @ 1, add a @ 3

我认为这是以前已经解决的问题，但是搜索它有点困难，因为“数组差异”没有给您正确的结果。

如果重要的话，我正在用 Javascript 实现它，但我猜该算法与语言无关。

Answer 1

这确实存在，它叫做 edit distance .基本算法不会记住编辑的种类，但很容易修改。

一种类型的编辑距离是 Levenshtein distance .此维基百科页面包含一些您可能会觉得有用的代码片段。

Hirschberg's algorithm也可能有用。