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.

[flashpixx]

Ich würde keinen Baumvergleich machen, sondern ich würde direkt die Pfade des Baumes vergleichen. Der Pfad + Blattinformation muss eindeutig sein, d.h. darüber einen Hash bilden und dann prüfen, ob dieser Hash jeweils vorhanden ist. Wenn ich nicht irre müsste das Blätteranzahl * Hashfunktionslaufzeit + lineare Suche als Laufzeit haben (Pfade & Hashing macht z.B. EncFS).

Es ist die Frage was Du letztendlich machst, ob Du zwei Dateisysteme als "Snapshot" vergleichen willst, d.h. zu einem Zeitpunkt t beide Dateisysteme vergleichst oder ob Du eine Datei aus dem einen System in das andere übertragen willst und zunächst prüfst, ob auf dem Zielsystem die Datei vorhanden ist. Ich denke es wird von dem konkreten Problem abhängig sein, was da der beste Weg ist

[Gast runtimeterror]

So wie flashpixx das beschrieben hat habe ich das in Java schon mal implementiert: Ein HashSet<Path> für jeweils Baum A und B und dann mit Schnittmengen etc. die Unterschiede und Gemeinsamkeiten bestimmen. Sofern alles in den Arbeitsspeicher passt ist das sehr einfach implementiert und sackschnell!

[MrTiger]

Ich danke euch.

Ich würde keinen Baumvergleich machen, sondern ich würde direkt die Pfade des Baumes vergleichen. Der Pfad + Blattinformation muss eindeutig sein, d.h. darüber einen Hash bilden und dann prüfen, ob dieser Hash jeweils vorhanden ist. Wenn ich nicht irre müsste das Blätteranzahl * Hashfunktionslaufzeit + lineare Suche als Laufzeit haben (Pfade & Hashing macht z.B. EncFS).

Du meinst ich solle für jedes Blatt einen Hashwert berechnen? Wobei ein Blatt ja ein leerer Ordner oder eine Datei sein kann. Dann muss ich aber ja alle Hashwerte der Blätter des einten Baumes gegen alle Hashwerte der Blätter des anderen Baumes vergleichen.

Könnte ich nicht einfach beide Dateisystem rekursiv durchlaufen und vergleichen?

Es ist die Frage was Du letztendlich machst, ob Du zwei Dateisysteme als "Snapshot" vergleichen willst, d.h. zu einem Zeitpunkt t beide Dateisysteme vergleichst oder ob Du eine Datei aus dem einen System in das andere übertragen willst und zunächst prüfst, ob auf dem Zielsystem die Datei vorhanden ist. Ich denke es wird von dem konkreten Problem abhängig sein, was da der beste Weg ist

Ich möchte die Dateisysteme als Snapshot vergleichen, d.h. feststellen welche Ordner und Dateien im einten Dateisystem vorhanden sind aber nicht im anderen.

[Klotzkopp]

Dann muss ich aber ja alle Hashwerte der Blätter des einten Baumes gegen alle Hashwerte der Blätter des anderen Baumes vergleichen.

Nein, musst du nicht. Du musst nur beide Hashmaps durchlaufen und prüfen, ob der jeweilige Hash in der anderen Hashmap vorhanden ist. Dazu musst du gar nichts vergleichen, das ist ja der Vorteil von Hashmaps.

Ich möchte die Dateisysteme als Snapshot vergleichen, d.h. feststellen welche Ordner und Dateien im einten Dateisystem vorhanden sind aber nicht im anderen.

In deinem ersten Beitrag ging es auch noch darum, festzustellen, welche Dateien in beiden vorhanden, aber unterschiedlich sind.

Könntest du bitte mal klarstellen, was genau das Ergebnis deines Vergleichs sein soll?

- Brauchst du nur die Pfade der Dateien/Ordner, die nur in einem Dateisystem liegen?

- Brauchst du auch die Pfade der Dateien/Ordner, die unterschiedlichen Inhalt haben?

- Brauchst du auch die Pfade der Dateien/Ordner, die sich anderweitig unterscheiden (Zugriffdatum, Rechte, Attribute)?

Das Was muss klar sein, bevor du dir Gedanken über das Wie machen kannst.

[flashpixx]

Du meinst ich solle für jedes Blatt einen Hashwert berechnen? Wobei ein Blatt ja ein leerer Ordner oder eine Datei sein kann. Dann muss ich aber ja alle Hashwerte der Blätter des einten Baumes gegen alle Hashwerte der Blätter des anderen Baumes vergleichen.

Nein, das ist so falsch, die Blätter sind nicht zwingend eindeutig, wenn eine Datei in 2 Ordnern liegt bzw. ein Link benutzt wird. Da ein Dateibaum ein Graph ist und ein Pfad in einem Baum / Graph eindeutig ist, muss der Hash über den gesamten Pfad + Daten gebildet werden, damit die Eindeutigkeit bewahrt bleibt

Bezüglich der HashMaps möchte ich anmerken, dass das recht naiv ist, man kann auch ganz speziell die Hashkollisionen nutzen um ähnliche Datensätze bzw Duplikate zu finden. Verwendet man Locality-sensitive hashing - Wikipedia, the free encyclopedia mit der Basis einer Bernoulli Verteilung, dann müsste darüber auch eine 1-Nachbarschaft (der nächste Nachbar) abbilden lassen.

Bei entsprechend generischem Design sollte es mit dem LSH möglich sein, sowohl Duplikate, wie auch Ähnlichkeiten auf beliebiger Definition bestimmen zu können

Bearbeitet 4. Mai 2013 von flashpixx

[MrTiger]

Ok, langsam ist es klarer. Wie kann ich den Hash über einen Pfad + Datei bilden? Also ich mein jetzt im konkreten Fall von C#. Ist eine etwas blöde Frage, aber ich bin da gerade etwas verwirrt und habe mit Hashes noch nicht so Erfahrungen.

Brauchst du nur die Pfade der Dateien/Ordner, die nur in einem Dateisystem liegen?

Ja, genau das.

Bezüglich der HashMaps möchte ich anmerken, dass das recht naiv ist, man kann auch ganz speziell die Hashkollisionen nutzen um ähnliche Datensätze bzw Duplikate zu finden. Verwendet man Locality-sensitive hashing - Wikipedia, the free encyclopedia mit der Basis einer Bernoulli Verteilung, dann müsste darüber auch eine 1-Nachbarschaft (der nächste Nachbar) abbilden lassen.

Bei entsprechend generischem Design sollte es mit dem LSH möglich sein, sowohl Duplikate, wie auch Ähnlichkeiten auf beliebiger Definition bestimmen zu können

Wie lässt sich das denn in C# verwirklichen? Eine HashMap wäre ja bereits als Datenstruktur vorhanden.

[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.

 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?

[flashpixx]

Wie kann ich den Hash über einen Pfad + Datei bilden?

Du musst es in geeigneter Weise machen, es ist letztendlich abhängig von Deiner Datenstruktur und dem was die Programmiersprache bietet.

Wie lässt sich das denn in C# verwirklichen?

Lies den Wikipedia Artikel durch, die Grundzüge des Algorithmus ist dort beschrieben und in den Quellen ist auf weiterführende Literatur verlinkt. Auch hier gilt wieder, es ist abhängig von dem was die Programmiersprache bietet und der konkreten Datenstruktur.

[Gast runtimeterror]

Vergleiche von Objekten laufen fast immer über die Equals-Methode - so auch bei DateTime:

DateTime.Equals-Methode (DateTime) (System)

Dein Code-Beispiel sieht etwas abenteuerlich aus. Wofür die zweifache Konvertierung über die Zeichenkette?

Das hier sollte dasselbe machen:

DateTime CurrentDate = DateTime.Now;