java - 用于区分内存对象的 Levenshtein Distance-like 算法？

Question

这里是 Java 8，尽管这个答案应该适用于任何语言。

我有一个问题，我需要比较对象，比如 Widgets ，并在它们之间产生一个“差异”:也就是说，一组步骤，如果遵循这些步骤，将转换一个 Widget (源)转换为另一个(目标)。

class Widget {
    // Properties and such.
}

class WidgetDiffer extends Differ<Widget> {
    List<Transformation> diff(Widget source, Widget target) {
        // The produced list will convert source to target, if executed
        // by some runtime.
    }
}

class WidgetTransformer extends Transformer<Widget> {
    @Override
    Widget transformSourceToTarget(Widget source, List<Transformation> transforms) {
        // Somehow, run 'transforms' on 'source', which *should*
        // produce an object with the same state/properties as
        // the original target.
    }
}

我知道 Levenshtein Distance字符串转换算法，但是:

• 这只是字符串，而不是 Widgets ;和
• 它只给你一个整数(将接收器变成目标所需的转换次数)，而我需要一个 List<Transformation>当由某些引擎执行时，将源转换为目标

我想知道是否有任何已知算法可以执行此类操作。这些算法有没有可能存在于某处的图书馆中？!？

Answer 1

我将其视为搜索问题。构造一个图，其中目标节点是所需的小部件，起始节点是要转换的小部件。每个步骤(图中的边)代表对小部件的一种可能转换(添加或删除属性)。构建图形后，运行带有路径提取的 DFS，您将获得将起始小部件转换为所需小部件所需的步骤(这也是所需的最少步骤)。