Projekt ddouble

Zielsetzung

Wir wollen unsere erworbenes Wissen und unsere Komponente Datei file_supplier.dart anwenden.

Ein nettes Problem ist die Suche von Dateiduplikaten, also von Dateien, die vom Inhalt her gleich sind, aber entweder verschiedene Namen haben oder in verschiedenen Unterverzeichnissen liegen.

Algorithmus

Wir durchlaufen alle Dateien eines Verzeichnisses, merken uns Kenndaten jeder Datei. Bei jeder neuen Datei überprüfen wir die Gleichheit mit allen vorigen Dateien.

Das klingt nach nicht lösbar, jede Datei mit jeder zu vergleichen: Bei einer Million Dateien wären das eine Billion Vergleiche, was "unendlich" lange dauert.

Der Trick liegt in den Daten, die wir uns für jede Datei merken:

• Die Dateigröße: Dateien können nur gleich sein, wenn die Größe übereinstimmt
• Ein Hashwert für den Inhalt: Ein Hashwert bildet den Inhalt einer Datei auf eine Zahl ab. Wir wählen als Hash-Algorithmus MD5, da ist die Zahl 128 Bit groß, also 128/8=7 Byte. Hashalgorithmen sind so gewählt, dass es extrem unwahrscheinlich ist, dass verschiedene Inhalte den gleichen Hashwert bekommen. Uns soll das als Gleichheitskriterium reichen.

Zur weiteren Beschleunigung berechnen wir zwei Hashwerte, einen für den Startblock, die ersten 4-kByte des Inhalts, den zweiten für den ganzen Inhalt. Jeder Hashwert wird aber nur berechnet, wenn er gebraucht wird.

Daraus ergibt sich folgender Algorithmus (in einer Pseudosprache):

// Über alle Dateien des Dateibaums:
for (var file in allFilesInFileTree()) {
  // Gibt es schon Dateien mit gleicher Größe?
  if processedFiles.hasKey(file.size) {
    // Den Hashwert für den ersten Block berechnen:
    file.hashStart = calcHashStart(file);
    // Alle Dateien mit dieser Größe abklappern:
    for (var file2 in processedFiles[file.size]) {
      // Gibt es schon einen Hashwert für den ersten Block?
      if not file2.hasHashStart {
         // Nein, dann berechnen
         file2.hashStart = calcHashStart(file2);
      }
      if file.hashStart == file2 {
        // Gibt es schon einen Hashwert für den ganzen Inhalt?
        if not file2.hasHashFull {
          // Nein, dann berechnen
          file2.hashFull = calcHashFull(file2);
        }
        // Gibt es schon einen Hashwert für den ganzen Inhalt?
        if not file.hasHashFull {
          // Nein, dann berechnen
          file.hashFull = calcHashFull(file);
        }
        if file.hashFull == file.hashFull {
          // Duplikat gefunden
        }
      }
    }
  }
  // Datei
  processedFiles.add(file);
}

Dieser Algorithmus hat folgende Eigenschaften:

• Jede Datei wird nur mit alle vorhergenden Dateien gleicher Größe verglichen.
• Der Vergleich zweier Dateien ist nur der Vergleich von Zahlen, wenn auch großen.
• Sowohl der Hashwert für den Startblock als auch der für den ganzen Inhalt wird höchstens einmal pro Datei berechnet.