查找大树结构中相同的目录树

Question

我有一个大型的目录树结构约10年的文件存档，在较大的树中的不同位置有多个较小的尝试副本。由于缺乏一致的备份策略和备案策略（基本上都属于我自己的错误），该树逐渐发展成为这种结构。

我正在寻找一种方法来在较大的树中找到相同的树木副本，这样我就可以删除我不需要的副本，让我更近一步地清理这个大混乱。

我以为我可以编写一个脚本来构建树中的文件数据库，这样我就可以编写另一个脚本来查找相同的树，从而删除树中最深层嵌套的树副本。

但是，我不知道如何在数据库设计和使用什么样的算法来有效比较这些树来找到相同的副本方面做得最好。

回顾一下，这是树的样子：

备份/文件夹1/ 备份/ somecomputer /库/文件夹1 备份/ othercomputer /文件夹1 ...

没有保证树是“完整的” - 可能是树相似，但只有树的一个副本包含大多数文件和子目录。所以这是关于找到最“完整”的树。

如果任何人有任何其他想法如何解决这个问题或有效地清理这样的混乱的结构，而不会超过每个单独的文件，我会非常感激！

由于 乙

Answer 1

也许使用后缀树数据结构，以找到最长共同子串 - 甚至可能与从而代表一个相似性度量不同。

根据层次结构的每个文件/目录在新树中的一个节点的意义上创建反映现有层次的新树。

为您打造树：使用的FileFilter和降序因为这是一个目录型的每个条目可能递归exapmple：

在新树中创建从根其路径到该节点的每个节点。将该路径作为密钥导入Map中，其中键是路径，值是新树中的节点引用。

然后，您可以针对此映射的keySet使用后缀树算法来查找共享通用后缀的条目 - 这些条目恰好是可以删除的条目。

这需要照顾相同的子树。后缀树也允许识别“未命中” - 即。如果路径中有一个或多个链接在两个路径之间存在差异。