java Levenshtein类距离算法，用于区分内存对象？

Question

这里是Java8，不过这个答案应该适用于任何语言

我有一个问题，我需要与对象进行比较，比如说，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

如果小部件只是按键->；价值袋比问题很简单

下面是一个JavaScript（可以将其用作Java实现的伪代码）版本

function diff(src, target) {
  var result = [];
  for(var key in src) {
    if(key in target) { 
      if(src[key] !== target[key]) {
        result.push({op:"update", name:key, value:target[key]});
      }
    } else {
      result.push({op:"delete", name:key});
    }
  }
  for(var key in target) {
    if(!(key in src)) {
      result.push({op:"add", name:key, value:target[key]});
    }
  }
  return result;
}

console.log(JSON.stringify(diff({}, {a:1, b:2, c:3})));
console.log(JSON.stringify(diff({a:1, b:2, c:3}, {})));
console.log(JSON.stringify(diff({a:1, b:2, c:3}, {b:20, c:30, d:40})));

O（srcPropCount*lookupTargetProp+targetPropCount*lookupSrcPropCount）

唯一的操作是添加新属性、更新现有属性和删除属性

Answer 2

我认为这是一个搜索问题。构建一个图，其中目标节点是所需的小部件，开始节点是要转换的小部件。每一步（图中的边）代表一种可能的小部件转换（添加或删除属性）。一旦构建了图形，运行带有路径提取的DFS，您将获得将启动小部件转换为所需小部件所需的步骤（这也是所需的最小步骤数）