目录树的递归N路合并/diff算法？
哪些算法或Java库可用于进行目录的N路递归差异/合并？
我需要能够生成一个文件夹树列表，其中有许多相同的文件，并且有许多类似文件的子目录。我希望能够使用双向合并操作，以尽快消除尽可能多的冗余。
目标：
duplicates
- Should
- 查找在它们之间有许多类似文件的目录对。
- 生成简短的目录对列表，这些目录对可以与双向合并同步，以消除递归操作(在目录和文件的数量上可能嵌套较高级别的(100,000+).
- Optional:时间和存储应该是O(n log ))，
- 应该能够使用嵌入式DB或页面到磁盘处理比适合内存(100,000+).
- Optional:更多的文件，从而生成一个祖先和在folders
H212<之间设置的更改集。/code>
可选:根据可以删除
的复制数对合并操作进行排序
我知道如何在粗略的O(n)空间中使用散列查找重复的文件，但我不知道如何从这个到找到文件夹和它们的子文件夹之间的部分重叠集。
编辑:一些澄清棘手的部分是“完全相同的”内容(否则哈希文件哈希会工作)和“相似”(这将不会)之间的区别。基本上，我想在一组目录中输入这个算法，并让它返回一组我可以执行的双向合并操作，以便尽可能减少重复，尽可能少的冲突。它有效地构建了一个祖先树，显示哪些文件夹是从彼此派生出来的。
最终的目标是让我把一堆不同的文件夹合并到一个普通的树中。例如，我可能有一个文件夹保存编程项目，然后将其某些内容复制到另一台计算机上。然后我可以备份和中间版本的闪存盘。除了我可能有8或10个不同的版本，有稍微不同的组织结构或文件夹名称。我需要能够将它们一步一步地合并起来，这样我就可以选择如何在每一步合并变更。
这实际上或多或少是我打算用我的实用程序做的事情(把来自不同时间点的一堆分散的备份集合在一起)。我想，如果我做得对，我可以发布它，就像一个小型的开源工具一样。不过，我认为同样的技巧对于比较XML树可能是有用的。
回答 1
Stack Overflow用户
发布于 2010-02-03 16:45:45
如果您发现文件名和大小(如果您发现它们是可靠的)，则应该只处理文件名和大小(如果您发现它们是可靠的)，以避免读取所有这些文件以及散列或散列它们。
以下是我的想法。
- 从文件系统加载所有数据。
- 列出了一个具有相似分数的候选目录对的列表。对于出现在两棵树中的每个目录名，对于所有共享该名称的目录对，得分为1分。对于出现在两棵树中的每个文件名(但并不是常常没有意义)，对于包含具有该名称的文件的所有对目录，都要得到1分。如果两个文件相同，则加分。如果文件名不出现在其他地方，则加分。每次你给点，也给所有祖先对一些点，这样如果a/x/y/foo.txt类似于b/z/y/foo.txt，那么对points.
- Optionally，、
(a/x/y, b/z/y)、(a/x, b/z)和(a, b)都会舍弃分数太低的所有配对，然后仔细检查其他对。到目前为止，我们只考虑了目录相似的方式。再看一遍，惩罚那些显示出没有共同祖先迹象的目录对。(这样做的一个一般方法是，如果两个目录都有所有的文件，并且它们都是相同的，则计算这两个目录可能拥有的最大分数；如果实际实现了可能的分数的一小部分，则拒绝这两个目录。但是，最好是做一些廉价和启发式的事情，或者跳过这个步骤，entirely.) - Choose是得分最高的候选目录对。输出它。从争用中删除这些目录及其所有子目录。重复，
选择正确的数据结构是一个练习。
该算法不尝试寻找具有不同文件名的相似文件。您可以使用类似rsync算法的方法在大型文件集中这样做，但我不确定您是否需要它。
该算法不严重尝试确定两个文件是否实际上是相似的。对于相同的文件名，它只得到1分，对于相同的大小和时间戳，它只得到加分。你当然可以给他们分配一个更精确的分数。我怀疑这是否值得。
https://stackoverflow.com/questions/2185734
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号