Bearbeiten von „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):
<pre>// Ü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);
}
</pre>
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.
@@ Zeile 58: / Zeile 58: @@
 * 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ü: <code>File</code> - <code>New</code> - <Project>
-* Linke Spalte: <code>Dart</code>
-* Dart-SDK:
-** Windows: c:\dart-sdk
-** Linux: ~/dart-sdk
-* Es erscheint eine Listbox, dort <code>Console-Application a command-line application sample</code> anklicken
-* <code>Next</code>-Button
-* Project name: <code>ddouble</code>
-* Project loction:
-** Linux: <code>~/dev/ddouble</code>
-** Windows: <code>c:\dev\ddouble</code>
-* <code>Finish</code>-Button
-Damit ist das Projekt names <code>ddouble</code> erstellt.
-* Herunterladen der Datei [https://github.com/flutter-tutorial-de/dart-programming/raw/main/resources/ddouble.zip ddouble.zip] und diese im Projektverzeichnis (<code>c:\dev\ddouble</code> oder <code>~/dev/ddouble</code>) entpacken.
-= Programmoptionen =
-<pre>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")
-</pre>
-== pubspec.yaml ==
-Wir verwenden drei externe Pakete, <code>path</code> für Behandlung von Dateinamen und <code>args</code> für die Auswertung von Programmargumenten und <code>crypto</code> für
-die Prüfsummenberechnung.
-Dazu kommt das externe Paket für Unittests <code>test</code> und die Unterstützung für die Quellcodeanalyse <code>pedantic</code>
-Die Datei <code>pubspec.yaml</code> muss deshalb so aussehen:
-<pre>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
-</pre>
-== Die Quellcodedateien ==
-Durch das obige Entpacken der Zip-Datei gibt es folgende Dateien im Verzeichnis <code>lib</code>:
-* 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 <code>DoubleFinder</code>, die die Suche organisiert.
-Zu jeder obigen Datei gehört eine Datei, die die Unittests enthält. Per Konvention wird einfach ein <code>_test</code> an den Namen angehängt.
-* Die [[Datei search_engine_test.dart]]: testet die Klasse <code>SearchEngine</code>
-* Die [[Datei helper_test.dart]]: testet die Funktionen.
-= Programm compilieren =
-== Linux ==
-* Terminal öffnen
-<pre>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
-</pre>
-== Windows ==
-* Eingabeaufforderung starten
-* <code>gdev ddouble</code>
-* <code>dcompile ddouble</code>
-Danach gibt es die Datei <code>c:\dev\bin\ddouble.exe</code>
-Dieses Programm kann in der Eingabeaufforderung gestartet werden.
-<pre>ddouble -r "main" "c:\Bilder"
-</pre>