Dateisystem als Baum darstellen und Diff berechnen

MrTiger

Grünschnabel
Hallo

Ich habe zwei Dateisystem, welche jeweils Order und Dateien enthalten. Ich möchte nun beide Dateisysteme als Bäume darstellen damit ich dann die Differenz bilden kann und somit feststellen kann welche Dateien und Ordner unterschiedlich sind bzw. im einen Dateisystem vorhanden sind aber nicht im anderen. Ich habe das Dateisystem selber entworfen, hier ist es nur von Bedeutung, dass wir eine hierarichsche Struktur von Ordner und Dateien haben, welche jeweils einen Namen haben.

Was für einen Baum würdet ihr da verwenden? Einen normalen n-ary tree?

Wie kann solch ein Baum aufgebaut werden, so dass er dann die Ordner- und Filestruktur widerspiegelt? Also wie das theoretisch bei einem n-ary tree geht weiss ich, also die inneren Knoten sind Ordner, der jeweilige Inhalt des Ordners sind dann Kinder etc., ich habe aber mit der Implementation etwas Mühe.

Wenn ich nun beide Bäume habe dann könnte ich ja einen normalen tree Diff Algorithmus anwenden. Ich habe bereits früher einmal einen Diff Algorithmus für Bäume implementiert (Zhang & Shasha’s Algorithmus), allerdings sind diese Algorithmen für grosse Bäume sehr langsam. Da ein Dateisystem aber sehr viele Ordner und Dateien enthalten kann und somit die Bäume sehr gross werden können und die Differenz allerdings trotzdem schnell berechnet werden muss, wäre dies vielleicht nicht so geeignet.

Was könnte man denn sonst noch anwenden um die Differenz zu bestimmen oder sollte ich gar keinen Baum verwenden?

Ich werde es übrigens in C# implementieren, wenn da vielleicht jemand direkt eine library oder code kennt, den ich verwenden oder als Inspiration brauchen könnte, wäre mir sehr gehollfen.

Vielen Dank.
 
Zurück