递归N路合并/差异算法用于目录树？

Question

递归N路合并/差异算法用于目录树？

4

有哪些算法或Java库可以进行目录的N路递归差异/合并？

我需要能够生成许多相同文件的文件夹树列表，并且具有许多包含相似文件的子目录。我希望能够使用2路合并操作尽快消除尽可能多的冗余。

目标：

- 找到之间有许多相似文件的目录对。 - 生成短列表，其中列出了可以通过2路合并同步以消除重复项的目录对 - 应该递归运行（可能存在更高级别目录的嵌套重复项） - 运行时间和存储应为O（n log n），其中n为目录和文件的数量 - 应能够使用嵌入式DB或页面到磁盘以处理比内存容量更大的文件（100,000+）。 - 可选：在文件夹之间生成祖先和更改集 - 可选：按它们可以消除的重复项数量对合并操作进行排序

我知道如何使用哈希在大约O（n）空间中查找重复文件，但是我不知道如何从此处转换为在文件夹及其子文件夹之间查找部分重叠集合。

编辑：一些澄清

棘手的部分是“完全相同”内容（否则哈希文件哈希将起作用）和“相似”（将不起作用）之间的差异。基本上，我想在一组目录中馈送此算法，并使其返回可以执行的2路合并操作，以便尽可能减少重复项且冲突尽可能少。它实际上是构造了一个祖先树，显示哪些文件夹是归属于对方的。

最终目标是让我将许多不同的文件夹合并为一个共同的树。例如，我可能有一个包含编程项目的文件夹，然后将其中一些内容复制到另一台计算机上进行工作。然后我可能会将一个中间版本备份到闪存驱动器上。除非我可能有8或10个不同的版本，具有略有不同的组织结构或文件夹名称。我需要能够逐步合并它们，以便我可以选择如何在每个阶段中合并更改。

这实际上与我打算使用我的实用程序所做的事情（将来自不同时间点的各种分散备份汇集在一起）几乎相同。我认为如果我能做对，我可能会将其发布为一个小型开源实用程序。我认为相同的技巧可能对比较XML树很有用。

- BobMcGee

定义“许多相似的文件”。您想要删除与另一个文件夹完全相同的文件夹吗？还是您只想在所有文件夹中删除重复项？如果是前者，请查看哈希树。如果是后者，我认为使用哈希表存储文件并没有问题。 - BlueRaja - Danny Pflughoeft

嗯，也不完全是。让我澄清一下：我想找到与其他文件夹具有相似内容和相似子文件夹的文件夹。我已经在问题中编辑了更多信息。手动完成这个任务的问题在于，最后我有超过30万个文件（部分组织形式），3万个子目录和400 GB的原始数据。 - BobMcGee

我不知道，但避免这种情况的工具应该是分布式版本控制（git、hg等）。 - Jason Orendorff

另外，请注意在桌面电脑上，一百万个文件名可以轻松存储在内存中，因此不需要使用外部数据库。 - Jason Orendorff

我想强调一下，我完全理解您正在寻找什么，您试图解决的问题，并且如果有一个好的解决方案，我会非常高兴。我已经思考这个问题有一段时间了，如果有一个好的解决方案，它将给我的生活带来快乐。您是否致力于Java？我正在使用node.js / javascript工作，并可能构建类似的东西。 - rob

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jason Orendorff · Accepted Answer

似乎最好只处理文件名和大小（如果您发现它们可靠的话），以避免读取所有这些文件并对它们进行散列或差异比较。以下是我的想法:

加载文件系统中的所有数据。它很大，但可以适应内存。
生成一张相似度得分候选目录对列表。对于在两个树中都出现的每个目录名称，为共享该名称的所有目录对得分1分。对于文件名称在两个树中都出现（但不频繁到无意义的程度）的每个文件，为包含该名称文件的所有目录对得分1分。如果两个文件完全相同，则获得额外得分。如果该文件名在其他地方没有出现，则额外得分。每次得分时，还要给所有祖先对一些得分，因此如果a / x / y / foo.txt与b / z / y / foo.txt相似，则对偶(a / x / y，b / z / y)和(a / x，b / z)和(a，b)都会得分。
可选择性地丢弃得分太低的对，并且仔细检查其他对。到目前为止，我们只考虑了目录相似的方法。再次查看，并惩罚显示没有共同祖先迹象的目录对。（一般的方法是计算两个目录可能具有的最大分数，如果它们都具有所有文件并且所有文件均相同，则拒绝该对，如果实际实现了该可能分数的仅为一小部分，则拒绝该对。但可能最好采用一些便宜且启发式的方法，或者完全跳过此步骤。）

选择得分最高的候选目录对。输出它。从竞争中淘汰这些目录及其所有子目录。重复进行。

选择正确的数据结构留给读者作为练习。此算法不尝试查找具有不同文件名的相似文件。您可以使用类似rsync算法的东西在大型文件集上执行此操作，但我不确定您是否需要它。此算法不会认真尝试确定两个文件是否实际相似。它只为相同文件名得分1分，并为相同大小和时间戳得到额外分数。您当然可以对它们进行差异分析以分配更精确的分数。我认为这样做并不值得。