我一直在寻找一种算法来有效地计算两棵树之间的编辑路径，该路径不必对应于最短编辑距离，但最好是相对较短的。
情况是我有两个目录树，由目录和文件组成，并且想要计算将一个转换为另一个的删除、插入和重命名序列。
我曾尝试搜索 stackoverflow 和 wild web，但我发现的只是计算最短编辑距离的算法，但它们都有很高的缩放因子。
所以我的问题是，当我不需要最佳距离时，有没有比“张和莎莎”更有效的方法？
亲切的问候
问问题
372 次
1 回答
0
有克莱因算法的性能略好于“张和萨沙”，但出于实用目的，它在空间和时间上仍然具有非常高的复杂性。
这里有一种算法实际上是一种启发式算法，因为作者误用了approximation一词。它将问题简化为一系列最大加权团，其中存在几种近似和启发式方法，即使是贪婪方法也可以在这里表现得相当好。
对图适用的对树也适用，因此您可以使用图核卷积方法。
如果您正在寻找现成的实现（未指定的算法，我猜是 Zhang 或 Klein），您可以在这里查看
于 2013-11-04T22:22:30.813 回答