Dateisystem als Baum darstellen und Diff berechnen

[The Gunner]

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.

 

[Krik]

Moin,

du hast da einen ganzen Stapel an Fragen losgelassen, die man leider nicht mit drei Sätzen beantworten kann.

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

Ich? Ja.
Je nach Anforderung würde ich vllt. sogar zwei oder mehr Bäume erstellen, die nach verschiedenen Prinzipien aufgebaut sind, aber Knoten und Blätter in dem jeweils anderen Baum/Bäumen ein entsprechendes Gegenstück haben. Auf welchen Baum dann am Ende zugegriffen wird, wird je nach Anforderung entschieden.

Wie kann solch ein Baum aufgebaut werden, so dass er dann die Ordner- und Filestruktur widerspiegelt?
[...]
ich habe aber mit der Implementation etwas Mühe.

Wo genau harkt es? Eigentlich ist es doch gar nicht so schwer:
Man macht eine Klasse "Knoten", die als Attribute eine Collection von Kindknoten und eine Referenz auf den Elternknoten hat, sofern vorhanden.

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

Das ist nicht so einfach zu beantworten, es hängt ganz von den Anforderungen ab.

Bei einem Dateisystem ist es vielleicht eine gute Idee, Eigenschaften eines Hash-Baums bzw. Merkle-Baums einzubauen. Vereinfacht gesagt, berechnet/hat jeder Knoten einen Hash, der sich aus den Kindknoten errechnet. Wenn man dann zwei Bäume auf Unterschiede vergleichen will, fängt man beim Hash des Wurzelknoten an und vergleicht ihn mit dem des anderen Baums. Passen sie nicht, wandert man Stück für Stück den Baum hinab - immer an den Ästen, wo die Hashes nicht passen - bis man den Grund der Unterschiede gefunden hat.
Der Algorithmus sollte eigentlich relativ fix sein. Der Baum ist es jedenfalls, aber der Hash-Algo kann beim Erstellen des Baums die Performance tüchtig drücken. Da sollte man auf einen einfachen Hash wie CRC zurückgreifen.
Ist der Baum erst mal erstellt, geht es recht fix, da man bei zB einer geänderten Datei nur die vielleicht 10 Hashes Richtung Wurzelknoten erneut berechnen muss. Das geht in Sekundenbruchteilen.


C#-Code oder Libs dafür kenne ich nicht. Aber das kann man auch sehr schnell selber bauen. Man braucht ja, wie geschrieben, nur eine Collection von Kindknoten sowie die Referenz auf den Elternknoten. Dazu noch ein paar Methoden, um auf diese Attribute zugreifen zu können und eventuell noch ein Feld für den Hash (falls du das einbaust). Das schaffst auch du in unter einer Stunde zu proggen.

 

[mastertier79]

@e-Laurin

so schauts aus

 

[The Gunner]

Wo genau harkt es? Eigentlich ist es doch gar nicht so schwer:
Man macht eine Klasse "Knoten", die als Attribute eine Collection von Kindknoten und eine Referenz auf den Elternknoten hat, sofern vorhanden.

Die Klassenstruktur des Baumes ist mir eigentlich klar. Mühe habe ich beim konkreten Aufbau des Baumes. D.h. Ich kann die Ordner- und Dateistruktur zwar rekursiv durchlaufen, aber wie baue ich da dann gleichzeitig den Baum korrekt auf?

Bei einem Dateisystem ist es vielleicht eine gute Idee, Eigenschaften eines Hash-Baums bzw. Merkle-Baums einzubauen. Vereinfacht gesagt, berechnet/hat jeder Knoten einen Hash, der sich aus den Kindknoten errechnet. Wenn man dann zwei Bäume auf Unterschiede vergleichen will, fängt man beim Hash des Wurzelknoten an und vergleicht ihn mit dem des anderen Baums. Passen sie nicht, wandert man Stück für Stück den Baum hinab - immer an den Ästen, wo die Hashes nicht passen - bis man den Grund der Unterschiede gefunden hat.
Der Algorithmus sollte eigentlich relativ fix sein. Der Baum ist es jedenfalls, aber der Hash-Algo kann beim Erstellen des Baums die Performance tüchtig drücken. Da sollte man auf einen einfachen Hash wie CRC zurückgreifen.
Ist der Baum erst mal erstellt, geht es recht fix, da man bei zB einer geänderten Datei nur die vielleicht 10 Hashes Richtung Wurzelknoten erneut berechnen muss. Das geht in Sekundenbruchteilen.

Das ist eine gute Idee, vielen Dank. Aber ist es eigentlich überhaupt nötig, dass ich das Dateisystem noch in einen tree parse? Denn das Dateisystem liegt ja schon in Ordnerstruktur vor und ich könnte einfach beide Dateisysteme rekursiv durchlaufen und vergleichen.

 

[Krik]

D.h. Ich kann die Ordner- und Dateistruktur zwar rekursiv durchlaufen, aber wie baue ich da dann gleichzeitig den Baum korrekt auf?

Du fängst im Wurzelverzeichnis an und gehst dann rekursiv die einzelnen Verzeichniselemente durch. Parallel erstellst du den Wurzelknoten des Baums, der auf das Wurzelverzeichnis zeigt. Dateien und Verzeichnisse wirfst du in die Collection. Dann gehst du in die einzelnen Unterverzeichnisse und im Baum über die Collection in den dazu passenden Unterknoten. Da erfasst du wieder alle Verzeichnisse usw. etc. pp.

Um aus den Verzeichnis(un)tiefen wieder hoch zu kommen, verwendest du Backtracking. Das kann man auch auf den Baum anwenden, allerdings musst du genau schauen, an welcher Stelle im Baum du dann hin musst. Das Dateisystem und die Collections sortieren eventuell unterschiedlich.
Aber im Prinzip kannst du alle Operationen, die du auf das Dateisystem ausführst, auch auf den Baum ausführen.

Das ist eine gute Idee, vielen Dank. Aber ist es eigentlich überhaupt nötig, dass ich das Dateisystem noch in einen tree parse? Denn das Dateisystem liegt ja schon in Ordnerstruktur vor und ich könnte einfach beide Dateisysteme rekursiv durchlaufen und vergleichen.

Man kann es schon so machen, wie du es vorgeschlagen hast.

Meine Idee mit dem Hash-Baum erlaubt dir allerdings, das Verschieben und Umbenennen von Daten zu erkennen. Wenn man zB ein ganzes Verzeichnis woanders hin verschiebt, bleibt dennoch der Hash gleich. Er ist dann nur an einer anderen Stelle im Baum und die gilt es dann zu finden (naiver Ansatz: alle Elemente im Baum durchsuchen). Benennt man das Verzeichnis allerdings um, ändert sich am Hash selber nichts, da der sich aus den Hashes der Kindknoten errechnet und nicht aus dem Namen (es sei denn du proggst das anders - geht ja auch).

Beim Namensvergleich und der Verschiebungserkennung solltest du allerdings alle vom Dateisystem erfassten Daten vorhalten (zB in Form eines Baums). Beide Operationen lassen sich nur teilweise in einem Rutsch gleichzeitig erledigen. Es werden hier eventuell mehrere Iterationen nötig und da ist es blöd, wenn man jedes Mal die Festplatte neu auslesen muss. Denke auch an die Hash-Generierung, die vermutlich in einem extra Schritt laufen wird und vielleicht auch parallel bei der Generierung des Baums laufen wird.

Der Baum selber verbraucht kaum Arbeitsspeicher. Und von letzterem haben heutige Rechner mehr als genug, du kannst da ruhig aus dem vollen schöpfen. Die Daten schon passend in einer selbstgewählten Struktur vorliegen zu haben, bringt dir später bei der Programmierung Vorteile. Die Struktur kannst du ja so anpassen, wie du es willst. Und da alles im RAM liegt, ist es auch noch sehr fix.

 

[The Gunner]

Vielen Dank. Ich probiere das einmal aus.

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?

 

[Darlis]

Du konvertierst einen DateTime zu einem String und diesen wieder zu DateTime. Den Sinn verstehe ich nicht.
Zum vergleichen von zwei DateTimes gibt es TimeSpan.

TimeSpan diff = newDateTime - oldDateTime;