algorithm - 近似编辑距离树 - 精确编辑路径

Question

我一直在寻找一种算法来有效地计算两棵树之间的编辑路径，该路径不必对应于最短编辑距离，但最好是相对较短的路径。

案例是我有两个目录树，由目录和文件组成，我想计算一系列删除、插入和重命名，将一个转换为另一个。

我尝试搜索 stackoverflow 和 wild web，但我只找到了计算最短编辑距离的算法，但它们都具有高比例因子。

所以我的问题是，当我不需要最佳距离时，是否有比“Zhang and Shasha”更有效的方法？

亲切的问候

Answer 1

有 Klein algorithm其表现略好于“Zhang and Sasha”，但出于实际目的，它在空间和时间上仍然具有非常高的复杂性。

有一个算法here这实际上是一种启发式方法，因为作者误用了术语 approximation . 它将问题简化为一系列最大加权集团，其中存在多个近似和启发式算法，即使是贪婪方法也可以在这里表现得相当好。

对于图是正确的，对于树也是正确的，因此您可以使用 graph kernel convolution approach .

如果您正在寻找现成的实现(非特定算法的实现，我猜是 Zhang 或 Klein)，您可以查看 here