logo标签列表

转换文件树到另一个的最短操作序列

algorithmedit-distancefiletree
17
给定两个文件树A和B，是否有可能确定将A转换为B所必需的最短操作序列或短操作序列？
操作可以是：
  1. 创建一个新的空文件夹
  2. 创建一个带任何内容的新文件
  3. 删除文件
  4. 删除空文件夹
  5. 重命名文件
  6. 重命名文件夹
  7. 将一个文件移动到另一个现有文件夹中
  8. 将一个文件夹移动到另一个现有文件夹中
当A和B拥有相同的文件、相同的名称、相同的文件夹结构以及相同的内容（或相同大小的CRC）时，它们是相同的。
这个问题已经困扰了我一段时间。目前我有以下基本想法：
  • 计算数据库：
    • 存储文件名和它们的CRC
    • 然后，查找所有没有子文件夹的文件夹，并从它们包含的文件的CRC计算CRC以及从它们包含的文件的总大小计算大小
    • 向上升级树以使每个父文件夹都有一个CRC
  • 使用具有数据库A和数据库B的以下循环：
    • 计算A∩B并从两个数据库中删除此交集。
    • 使用内部连接在A和B中查找匹配的CRC，首先是文件夹，按大小降序排列
    • 当有结果时，使用第一个结果进行文件夹或文件移动（必要时可能创建新文件夹），从结果的源行中删除并从两个数据库中删除。如果有移动，则在db A中更新新位置的父文件夹的CRC。
    • 然后删除数据库A中引用的所有文件和文件夹，并创建引用的数据库B中的文件和文件夹。
然而我认为这真的是一种次优的方法。你能给我什么建议吗？
谢谢！
也许Unison或rsync可以做到这一点。 - whoplisp
在一般情况下，这可能非常困难。特别是如果你强制要求一个文件夹中的两个文件夹/文件不能在任何给定时间包含相同的名称。 - tskuzzy
@tskuzzy：当然有这个限制...在实际应用中，使用这种算法可以很好地减少第三方中介存储的远程备份时的数据传输。 - Benoit
5个回答
6
这个问题是树编辑距离问题的一个特殊情况，寻找最优解是NP难问题（不幸的是）。这意味着一般情况下可能没有好的、快速和准确的算法。
话虽如此，我提供的论文包含了几个近似算法和在问题受限情况下工作的算法。您可能会发现这些讨论很有趣，因为它们阐明了实际解决这个问题时出现的许多问题。
希望能对您有所帮助！感谢您发布这个棒极了的问题！
这并不是一个特殊情况；更多的是一个相关问题，因为允许的编辑方式不同，并且叶节点和非叶节点之间有区别。 - tskuzzy
@tskuzzy- 你说得对，允许的编辑方式确实不同，但我认为你可以通过让每个目录将其文件视为叶节点来区分叶节点和非叶节点。也许我对此有所错误？ - templatetypedef
我的意思是树形编辑距离不区分“文件夹”和“文件”。例如，它可能会将一个节点插入到文件中。 - tskuzzy
3
你可能想要查看树编辑距离算法。我不知道这是否能够很好地映射到您的文件系统，但它可能会给您一些思路。 https://github.com/irskep/sleepytree（代码和论文）
1

  1. 枚举B中所有文件及其关联的大小和校验和；按大小/校验和排序。

  2. 枚举A中所有文件及其关联的大小和校验和；按大小/校验和排序。

  3. 现在，进行有序列表比较，执行以下操作：

    a. 对于A中存在但B中不存在的每个文件，删除它。

    b. 对于B中存在但A中不存在的每个文件，创建它。

    c. 对于A和B中的每个文件，将遇到的尽可能多的文件从A重命名为B，然后将其余部分复制到B。如果要覆盖现有文件，请将其保存到单独的列表中。如果在该列表中找到A，则将其用作源文件。

对于目录也是同样的操作，删除A中没有的目录并添加B中没有的目录。

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

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

这不是树编辑距离问题; 它更像是一个生成树的列表同步问题。

1

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

  • A) 创建Tree A文件的哈希映射
  • B) 遍历Tree B文件
  • B.1) 如果哈希映射中存在一个相同（名称和内容）的文件，则保持不变
  • B.2) 如果内容相同但名称不同，请将文件重命名为哈希映射中的名称
  • B.3) 如果哈希映射中不存在该文件内容，则删除它
  • B.4) （如果1、2、3中的某一个为真）从哈希映射中删除该文件

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

在文件差异已经解决后，它变得相当棘手。如果没有有效的最优解决方案来解决此问题（NP完全/难）也不会让我感到惊讶。

困难在于该问题不自然地细分。每个步骤都必须考虑整个文件树。我会再想想的。

编辑：看起来最研究的树编辑距离算法只考虑创建/删除节点和重新标记节点。这对于此问题并不直接适用，因为该问题允许移动整个子树，使得它变得更加困难。目前"更容易"的编辑距离问题的最快运行时间是O(N^3)。我想这个问题的运行时间会明显较慢。
有用的链接/参考资料： 《一种用于树编辑距离的最优分解算法》 - Demaine、Mozes、Weimann
0

唯一的非平凡问题是移动文件夹和文件。重命名、删除和创建是平凡的，可以在第一步（或最后一步）完成。

然后，您可以将此问题转化为通过转换树来解决问题，两者具有相同的叶子但不同的拓扑结构。

  1. 您决定从某个文件夹/桶中移动哪些文件，哪些文件留在文件夹中。决策基于源和目标中相同文件的数量。

  2. 您将相同的策略应用于在新拓扑结构中移动文件夹。

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

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接