Algorithmus zum Auffinden historischer Operationen in einer Baumverzeichnisstruktur

Question

Es gibt ein interessantes Problem, auf das ich gestoßen bin. Es gibt einen Verzeichnisbaum Aufruf lässt, dass T

nun in der Verzeichnisstruktur gibt es drei Operationen erlaubt sind

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. 

Jetzt Sie die oben genannten drei Operationen in beliebiger Reihenfolge auf das Verzeichnis T auszuführen. Diese Operationen werden eine andere Verzeichnisstruktur geben, rufen Sie sie T'.

Die Frage ist, ob Sie T haben und T' Lage wäre, die MinimumSequenz von Operationen S zu finden, die T zu T' umgewandelt.

Zum Beispiel

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} 

Answer 1

können wir Tiefensuche auf zwei Bäume gleichzeitig und auf Dateiebene können wir Prüfsumme, um zu überprüfen, ob zwei Dateien identisch sind. Die Operation auf Dateiebene kann O (n^2) sein, wenn alle Dateien umbenannt werden und n die Anzahl der Dateien in einem Verzeichnis ist. Für eine bessere Leistung können wir auf jeder Verzeichnisebene ein Manifest mit Prüfsummen jeder erfassten Datei führen geändert werden und wird komplexer, aber das ist nicht erforderlich, wenn wir diese Operation nicht häufig durchführen möchten). Dies kann viel mehr Ausgabe erzeugen, wenn ein Verzeichnis verschoben wird, in diesem Fall können wir eine kumulative Prüfsumme wie Sache für jedes Verzeichnis berechnen und sie für eine Ebenenreihenfolge-Traversierung später speichern. Während wir später eine Level-Order-Traversierung durchführen, können wir die Ausgabe optimieren. (Nur ein Gedanke)