Dateisystem als Baum darstellen und Diff berechnen

[MrTiger]

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.

[cloidnerux]

Deine Dateisysteme sind doch schon Baumstrukturen, du brauchst diese ja egt nicht nochmal einlesen.
Dann kannst du die Unterschied auch direkt linear-komperativ gestalten. Du holst dir die Liste an Ordner aus dem Stammverzeichnis und vergleichst diese, fehlt hier ein Ordner, sind alle Unterordner und Dateien auch unterschiedlich.
Dann noch alle Dateien miteinander vergleichen.
Dann in den ersten Ordner gehen, wieder überprüfen usw.
Du kannst so z.B einfach die zu überprüfenden Ordner als Pfad in eine Liste speichern.

Der Gesamtaufwand beträgt mindestens 3 Operationen(nicht Elementare) für jeden Ordner und Datei, daher wird mit wachsender Größe das vergleichen einfach etwas Zeit in Anspruch nehmen.

Willst du nur auf Strukturgleichheit prüfen, oder soll der Dateiinhalt auch gleich sein?

[Xin]

Ich sollte endlich Dedupe mal wieder ausgraben und mich wieder beteiligen, wenn ich denn mal Zeit hätte...

@MrTiger: Wenn Du Dich mit C++ anfreunden kannst... Dedupe

[MrTiger]

Ich danke euch.

C++ kommt nicht in Frage.

cloidnerux, du hast Recht, eigentlich muss ich nicht noch einmal einen Baum erzeugen. Ich dachte halt nur, dass es vielleicht schneller wäre.

Du kannst so z.B einfach die zu überprüfenden Ordner als Pfad in eine Liste speichern.

Du meinst also zuerst für alle Ordner aus dem Stammverzeichnis eine solche Liste machen bzw. je eine Liste für beide Dateisystem und dann die Liste überschreiben mit allen Unterordnern des ersten Ordners etc.?

Willst du nur auf Strukturgleichheit prüfen, oder soll der Dateiinhalt auch gleich sein?

Nur Strukturgleichheit, also anhand von den Dateinamen, aber nicht den Dateiinhalt vergleichen.

[MrTiger]

Ich habe noch ein kleines zusätzliches Problem. Ich würde gerne einen timestamp für Dateien und Ordner einführen. Man könnte ja einen timestamp wie folgt bekommen.

Code: Alles auswählen

 DateTime CurrentDate;
CurrentDate = Convert.ToDateTime(DateTime.Now.ToString("yyyyMMddHHmmssffff"));

Das Problem ist nun, dass ich die timestamps vergleichen möchte. Müsste ich da dann nach integer konvertieren? Oder wie macht man das?

[cloidnerux]

Das Problem ist nun, dass ich die timestamps vergleichen möchte. Müsste ich da dann nach integer konvertieren? Oder wie macht man das?

Im einfachsten Fall:

Code: Alles auswählen

if(dateTime1 == dateTime2)[...]

da die meisten Klassen aus den Standardbibliotheken die Equals()-Funktion überschreiben.

Du meinst also zuerst für alle Ordner aus dem Stammverzeichnis eine solche Liste machen bzw. je eine Liste für beide Dateisystem und dann die Liste überschreiben mit allen Unterordnern des ersten Ordners etc.?

Nein, es ging mir darum, sich zu merken welche Ordner man noch abklappern muss, um nicht rekursiv zu werden.
Wenn du die beiden Ordnerstrukturen vergleichst, dann interessieren dich ja nicht alle Ordner und Dateien, sondern nur die, die Unterschiedlich sind. Wenn du also im Vergleich unterschiedliche Dateien findest, kannst du diese als Unterschiedlich melden und danach ignorieren. Wenn du einen unterschiedlichen Ordner findest, so sind ja auch alle Unterordner sofort unterschiedlich zum anderen Dateisystem und du brauchst diesen nicht mehr Durchsuchen. Daher brauchst du in die Liste nur die gleichen Ordner eintragen und kannst weiter vergleichen.