我已经实现了Zhang 和 Shasha 的算法来计算两棵树之间的最小编辑距离。一切正常，我对当前的运行时间非常满意。
现在我还想生成一个突出显示更改/删除/插入节点的差异。根据他们的论文，很自然地要求生成计算距离的映射，并且根据本演示文稿的最后一张幻灯片，似乎可以从最后的森林距离表和树距离表中轻松提取映射。不幸的是，我还没有弄清楚确切的规则。
任何额外的描述将不胜感激。非常感谢！
问问题
481 次
1 回答
3
好的，我终于自己弄清楚了。为了生成两棵树的节点的最佳映射，分别有 m 和 n 个节点，您需要在森林表中进行一些回溯。
对于 (m, n) 森林距离表中以 (m, n) 开头的每个字段 (x, y)，请执行以下操作：如果通过将字段 (x', y') 和编辑相加得到最小值/删除/插入成本，然后记下映射，到当前森林距离表的字段(x', y')。另一方面，如果通过将当前森林距离表中的字段 (x', y') 和树距离表中的字段 (tx, ty) 相加得到最小值，则转到字段 (x' , y') 从当前的森林距离表 AND 到对应于树 (tx, ty) 的森林表的字段 (tx, ty)。您现在需要分别在两个林表中继续回溯并从这两个表中收集映射。
于 2013-08-01T16:22:51.177 回答