algorithm - 将文件树转换为另一个文件树的最短操作序列

Question

给定两个文件树 A 和 B，是否可以确定将 A 转换为 B 所需的最短操作序列或操作序列？

一个操作可以是：

当 A 和 B 在相同文件夹结构中具有相同内容（或相同大小相同 CRC）和相同名称的相同文件时，它们是相同的。

这个问题让我困惑了一段时间。目前我有以下基本想法：

计算一个数据库：
- 存储文件名及其 CRC
- 然后，找到所有没有子文件夹的文件夹，并根据它们包含的文件的 CRC 计算 CRC，并根据它们包含的文件的总大小计算大小
- 提升树为每个父文件夹创建一个 CRC
使用具有数据库 A 和数据库 B 的以下循环：
- 计算 A ∩ B 并从两个数据库中删除此交集。
- 使用内连接在 A 和 B 中查找匹配的 CRC，首先是文件夹，按大小排序
- 当有结果时，使用第一个结果移动文件夹或文件（如有必要，可能创建新文件夹），从两个数据库中删除结果的源行。如果有移动，则更新 db A 中新位置父文件夹的 CRC。
- 然后删除数据库 A 中引用的所有文件和文件夹，并创建数据库 B 中引用的文件和文件夹。

但是，我认为这确实是一种次优的方法。你能给我什么建议？

谢谢！

score 6 · Accepted Answer

这个问题是树编辑距离问题的一个特例，找到一个最优解（不幸的是）已知是 NP 难的。这意味着对于一般情况，可能没有任何好的、快速和准确的算法。

也就是说，我链接的论文确实包含一些关于近似算法和在问题的受限情况下工作的算法的很好的讨论。您可能会发现讨论很有趣，因为它阐明了解决此问题时实际出现的许多问题。

希望这可以帮助！感谢您发布一个很棒的问题！

score 3 · Accepted Answer

您可能想查看树编辑距离算法。我不知道这是否会巧妙地映射到您的文件系统，但它可能会给您一些想法。

score 1 · Accepted Answer

要做的第一步是确定需要创建/重命名/删除哪些文件。

哈希映射中剩余的文件是必须创建的文件。这应该是解决目录结构之后的最后一步。

在解决了文件差异之后，它变得相当棘手。如果没有有效的最佳解决方案来解决这个问题（NP-complete/hard），我不会感到惊讶。

困难在于问题本身并不能自然地细分。您所做的每一步都必须考虑整个文件树。我会再考虑一下。

编辑：似乎研究最多的树编辑距离算法只考虑创建/删除节点和重新标记节点。这并不直接适用于这个问题，因为这个问题允许移动整个子树，这使得它变得更加困难。“更容易”的编辑距离问题的当前最快运行时间是O(N^3). 我想这个的运行时间会明显变慢。

有用的链接/参考

score 1 · Accepted Answer

对目录执行相同的操作，删除 A 中但不在 B 中的目录，并在 B 中添加但不在 A 中的目录。

您通过校验和/大小进行迭代，以确保您不必两次访问文件或担心删除稍后需要重新同步的文件。我假设您正在尝试使两个目录保持同步而无需进行不必要的复制？

总体复杂度为 O(N log N) 加上读取所有这些文件及其元数据所需的时间。

这不是树编辑距离问题；它更像是一个列表同步问题，恰好生成一棵树。

score 0 · Accepted Answer

唯一重要的问题是移动文件夹和文件。重命名、删除和创建是微不足道的，可以在第一步中完成（或者在完成后更好地在最后一步完成）。

然后，您可以将此问题转换为问题，即转换具有相同叶子但拓扑不同的树。

我认为如果您忘记文件夹的名称而只考虑文件和拓扑，那么您应该接近最佳或最佳。