在Tree目录结构中查找历史操作的算法

我遇到了一个有趣的问题。有一个目录树让呼叫T在Tree目录结构中查找历史操作的算法

现在在目录结构中有3个操作是允许

1. Add a file or another directory under some parent directory 
2. Remove a file or another directory 
3. Modify that is move a file/directory from one parent directory to another.

现在你在任何顺序上的目录T执行上述3个操作。该操作将提供另一个目录结构，我们称之为T'。

的问题是，如果你有T和T'将能够找到最低顺序操作S其转化T到T'的。

例如

T = 
root/ 
---- a/ 
     --- file1.txt 

T' = 

root/ 
---- a/ 

S = {Delete root/a/file1.txt} 

Another example 

T = 
root/ 
---- a/ 


T' = 

root/ 
---- a/ 
     ---file1.txt 

S = {Add root/a/file1.txt}

来源

2017-09-30 Avishek Bhattacharya

请你详细说明你的问题.... – krpra

我不知道你想要什么阐述。在一个目录中，你可以改变文件，删除/添加等，之后，以前的目录从旧状态转换为新状态。问题是要找到可以更改为新状态的最小操作集合 –

@Krpa我已经添加了一个示例 –

我们可以深度上同时两棵树，并在文件层面上，我们可以使用校验和检查两个文件是相同的优先搜索。如果所有文件都被重命名，并且n是目录中文件的数量，那么文件级别的操作可以是O（n^2），为了获得更好的性能，我们可以在每个目录级别维护一个清单，并对每个捕获的文件进行校验和（文件操作需要被修改并且会更加复杂，但如果我们不想经常这样操作，这不是必需的）。如果一个目录被移动，这可以产生更多的输出，在这种情况下，我们可以为每个目录计算累积校验和类似的东西，并保存它以便稍后进行级别遍历。在稍后进行级别遍历时，我们可以优化输出。（只是一个想法）

来源

2017-09-30 13:46:04 user8700406

在Tree目录结构中查找历史操作的算法

回答

相关问题