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.

Projekt erstellen

• IdeaIC starten
• Menü: File - New - <Project>
• 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.

Programmoptionen

Usage: ddouble [<options>] [<file1> [<file2>...]]
  Find files with the same content in directory trees.
  <fileN>: a directory or a shell file pattern like '*.txt'
    or both like /home/*.txt

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")

pubspec.yaml

Wir verwenden drei externe Pakete, path für Behandlung von Dateinamen und args für die Auswertung von Programmargumenten und 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:

name: dgrep
description: A program for searching dublicates (files with the same content).
version: 0.1.0

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

Die Quellcodedateien

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

• Die Datei helper.dart: kleine Hilfsfunktionen, die sonst nirgens hinpassen (Ü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, die 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 search_engine_test.dart: testet die Klasse SearchEngine
• Die Datei helper_test.dart: testet die Funktionen.

Programm compilieren

Linux

• Terminal öffnen

gdev ddouble
dcompile ddouble
</code>
Danach gibt es die Datei <code>/usr/local/bin/ddouble</code>.
Dieses Programm kann in der Eingabeaufforderung gestartet werden.
<pre>ddouble /home/Bilder

Windows

• 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"