我有两个树结构，它们代表目录结构在两个不同时间点的快照。在快照之间可能已经添加、删除或修改了目录。我需要同时走两棵树，并用两者之间的差异标记较新的节点——即将节点标记为新的、已修改的、已删除的、未更改的，添加任何已删除的节点，以便最终结果是两个快照的完整超集。
通常，这些树可能有大约 10 深但非常宽，包含数十万甚至数百万个节点。我想通过比较每个节点的哈希码来跳过大块的树，并且只在代码不匹配的地方继续递归。
有没有一种算法可以成为我的朋友？还有什么建议吗？
问问题
630 次
2 回答
1
想象一下将每棵树展开成一个排序的文件和目录列表。一种方法可以从每个展开的树中从该树的插入器中获取下一个输入。然后，我可以比较哈希码并跳过一棵树或另一棵树、注释删除和注释修改。
于 2010-01-15T23:20:53.120 回答
1
Lindholm、Kangasharju 和 Tarkoma 的论文“Fast and Simple XML Tree Differencing by Sequence Alignment”有一些提示：
1) rsync 做你感兴趣的事情。看看http://samba.anu.edu.au/ftp/rsync/rsync.html，看看 rsync --list 是否值得检查- 只做它听起来的样子。
2）一个技巧是将树层次结构变成一个序列，通过深度优先搜索遍历它，然后比较两个序列。然后可以通过使用滚动哈希 ( http://en.wikipedia.org/wiki/Rolling_hash ) 来实现您关于比较哈希码的想法。
我怀疑您最终会生成两个完整的序列，然后在它们之间运行一些等效的 diff 或 xdelta ，而不是尝试逐步完成这项工作。当某些子目录在树结构中移动很长一段距离时，完全增量的方法可能会出现问题。
于 2010-01-16T06:33:00.517 回答