5

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

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 实现它,但我猜该算法与语言无关。

4

1 回答 1

7

这确实存在,它被称为编辑距离。基本算法不记得编辑的类型,但很容易修改。

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

Hirschberg 的算法也可能有用。

于 2013-12-19T18:06:21.027 回答