Table of Contents Zielsetzung Algorithmus Projekt erstellen Programmoptionen pubspec.yaml Die Quellcodedateien Programm compilieren Linux Windows

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.

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

Nun erscheint der Aufwand, jede Datei mit allen anderen zu vergleichen, nahezu unmöglich: 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. Dieses Kriterium soll uns 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. Zur Arbeitserleichterung wird der zweite Hashwert 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 allen vorhergehenden Dateien gleicher Größe verglichen.
• Der Vergleich zweier Dateien ist nur der Vergleich von Zahlen, auch wenn diese sehr groß sind.
• Sowohl der Hashwert für den Startblock als auch der für den ganzen Inhalt wird höchstens einmal für jede Datei berechnet.

• IdeaIC starten
• Menü: File - New -
• Linke Spalte: Dart
• Dart-SDK:
  • Windows: c:\dart-sdk
  • Linux: ~/dart-sdk
• Es erscheint eine Listbox, dort Console-Application a command-line application sample anklicken.
• Next-Button
• Project name: ddouble
• Project loction:
  • Linux: ~/dev/ddouble
  • Windows: c:\dev\ddouble
• Finish-Button

Damit ist das Projekt names ddouble erstellt.

• Herunterladen der Datei ddouble.zip und diese im Projektverzeichnis (c:\dev\ddouble oder ~/dev/ddouble) entpacken.

Examples:
 ddouble
 ddouble -V2 /opt/*.png /home
<option>:
-h, --help             Show the command description
-b, --block-length     length of a block for hashing
                       (defaults to "8388608")
-s, --start-length     length of the start block (used for the first hash value)
                       (defaults to "4096")
-x, --excluded         A regular expression for files to skip, e.g. ".*.(bak|sic)"
-X, --excluded-dirs    A regular expression for directory to skip, e.g. "test|.git|.config
-V, --verbose-level    0: no additional info 1: summary 2: detail 3: loop 4: fine
                       (defaults to "2")

Wir verwenden drei externe Pakete: path für Behandlung von Dateinamen, args für die Auswertung von Programmargumenten sowie crypto für die Prüfsummenberechnung.

Dazu kommt das externe Paket für Unittests test und die Unterstützung für die Quellcodeanalyse pedantic.

Die Datei pubspec.yaml muss deshalb so aussehen:

environment:
  sdk: '>=2.10.0 <3.0.0'

dependencies:
  args: ^1.6.0
  path: ^1.7.0
  crypto: ^2.1.5

dev_dependencies:
  pedantic: ^1.9.0
  test: ^1.15.7

Durch das obige Entpacken der Zip-Datei gibt es folgende Dateien im Verzeichnis lib:

• Die Datei helper.dart: kleine Hilfsfunktionen, die sonst nirgends hin passen (Übernahme aus Projekt dgrep).
• Die Datei file_supplier.dart: Ein Generator, der Dateinamen aus einem Dateinamen liefert (Übernahme aus Projekt dgrep).
• Die Datei double_finder.dart: die Klasse DoubleFinder, welche die Suche organisiert.

Zu jeder obigen Datei gehört eine Datei, die die Unittests enthält. Per Konvention wird einfach ein _test an den Namen angehängt.

• Die Datei double_finder_test.dart: testet die Klasse DoubleFinder.

• Terminal öffnen

gdev ddouble
dcompile ddouble

Danach gibt es die Datei /usr/local/bin/ddouble. Dieses Programm kann in der Eingabeaufforderung gestartet werden.

ddouble /home/Bilder

• Eingabeaufforderung starten
• gdev ddouble
• dcompile ddouble

Danach gibt es die Datei c:\dev\bin\ddouble.exe Dieses Programm kann in der Eingabeaufforderung gestartet werden.

ddouble -r "main" "c:\Bilder"