Harald Halm, Olaf Zurth

Bei intensiver Nutzung eines Computers kann es schon einmal vorkommen, daß auf verschiedenen Disketten gleichnamige Dateien vorkommen. Die Frage, die sich dann stellt, ist, ob die Dateien verschieden oder identisch sind.

Um zwei Dateien auf Gleichheit zu prüfen, kann man sich eines kleinen Programmes bedienen. Wir stellen hier einen Algorithmus für Text-Dateien vor, der auf recht schnelle und elegante Art erlaubt, Differenzen zwischen zwei Dateien zu ermitteln.
Zunächst stellt sich die Frage, wie man Differenzen zwischen Dateien am besten darstellen kann. Dazu betrachten wir in Bild 1 die Dateien ALT und NEU.

Bild 1. Die Dateien OLD und NEW. Gleiche Zeilen sind verbunden.

Jede Zeile ist der Übersichtlichkeit wegen mit einer Zeilennummer versehen. In den ersten drei Zeilen stimmen beide Dateien überein. Die Zeile 4 der Datei ALT kommt in der Datei NEU in der Zeile 7 vor. Ebenfalls findet man den Inhalt der Zeilen 6 und 11 in der Datei NEU wieder. Es scheint sinnvoll, solche Übereinstimmungen bei den Differenzen zu berücksichtigen. Sie werden bei der Erklärung des Algorithmus eine wesentliche Rolle spielen.
Um Differenzen zwischen zwei Dateien feststellen zu können, wählen wir drei Grundoperationen, die in sinnvoller Weise die Unterschiede in den Dateien darstellen. Diese Grundoperationen sind:

n1,n2d (lösche von Zeile n1 bis Zeile n2 in Datei ALT)
nl,n2cm1,m2 (ersetze Zeile n1 bis n2 in ALT durch Zeile m1 bis m2 in NEU)
n1am1,m2 (hänge ab Zeile n1 in ALT die Zeilen m1 bis m2 aus NEU an).
In Bild 2 sind diese Grundoperationen anhand des Beispieles aus Bild 1 dargestellt.

3a4,6 > egal > wie > lang 5,5c8,8 < richtigen --- > falschen 7,10d < und < am < richtigen < Platz 12,14c11,12 < spart < viele < Erklärungen --- > stiftet > Verwirrung Bild 2. So werden Differenzen von „dfc" angezeigt 3a4,6 > egal > wie > lang 5,5c8,8 > falschen 7,10d 12,14c11,12 > stiftet > Verwirrung Bild 3. Eine modifizierte Ausgabe, die von einem Editor bearbeitet werden kann

Steht vor der Zeile ein „<", so bezieht sie sich auf die Datei ALT. Steht vor der Zeile ein „>", so bezieht sie sich auf die Datei NEU. Beim Ersetzungskommando sind die Zeilenblöcke durch „---" getrennt.

Der Algorithmus arbeitet zeilenorientiert; für das Programm ist die Datei also eine Folge von Zeilen. Zuerst werden die beiden Dateien solange verglichen, bis zwei Zeilen verschieden sind. Dies ist in unserem Beispiel bei Zeile 4 der Fall. Von dieser Zeile ausgehend werden die beiden Dateien solange durchsucht, bis zwei gleiche Zeilen festgestellt werden. Diesen Vorgang nennen wir eine Synchronisation. Je nach dem, an welcher Stelle die Synchronisation stattfindet, wird eine der drei Grundfunktionen angewendet. Im Beispiel synchronisieren die Zeile 4 in ALT und die Zeile 7 in NEU, es wird
3a4,6
egal
wie
lang,
ausgegeben (Bild 3) und der weitere Vergleich startet bei der Synchronisation der Zeilen 4 aus ALT und der Zeile 7 aus NEU.
Nun wird wieder zeilenweise verglichen, bis zwei verschiedene Zeilen vorkommen. Ausgehend von diesen verschiedenen Zeilen sucht der Algorithmus dann eine weitere Synchronisation und der eben beschriebene Vorgang wiederholt sich so lange, bis bei beiden Dateien ein EOF (End of File) erkannt wird. Ein Vorteil dieses Algorithmus liegt darin, daß sofort nach einer Synchronisation eine Ausgabe erfolgt. Dadurch wird besonders bei PCs ohne Festplatte oder RAM-Disk schnell ein Ergebnis erzielt.

Der Algorithmus wurde in der Sprache C programmiert. Damit konnte das Programm schnell unter verschiedenen Betriebssystemen getestet werden. Alle betriebssystemspezifischen Teile des Programmes (Bild 4) sind in der Header-Datei (Bild 5) enthalten.
Das Hauptprogramm „main" bearbeitet nur die Eingabeparameter der Kommandozeile und notiert sie in der Struktur „dp", mit der das eigentliche Programm „dodfc" (Bild 6) als Funktion aufgerufen wird.
Dieses Vorgehen hat den Vorteil, daß auch unter Betriebssystemen wie z.B. CP/M, wo nur ein Prozeß laufen kann, die Funktion „dodfc" in anderen Programmen aufgerufen werden kann, obwohl sie ein eigenständiges Programm repräsentiert. Sie kann sogar zu einer Bibliotheksfunktion gemacht werden. Das Programm erwartet zwei Namen der zu vergleichenden Dateien als Parameter. Wird das Programm falsch aufgerufen, wird die richtige Aufrufform dfc [-{l|s|mN}] Oldfile Newfile angezeigt. Hierbei erkennt man, daß es drei optionale Parameter gibt. Mit der Option „-l" werden die erkannten Unterschiede wie in Bild 2 angezeigt. Diese Option ist voreingestellt. Möchte man die Unterschiede lieber, wie in Bild 3 gezeigt, als Editor-Script haben, muß man die Option „-s" wählen. Mit der Option „-mN" wird der Grad der Synchronisation festgelegt. Der Algorithmus synchronisiert nur dann, wenn N aufeinanderfolgende Zeilen übereinstimmen. N darf eine natürliche Zahl <32767 sein. Voreinstellung ist 1. Die Wahl dieses Wertes hängt von der Anwendung des Programmes ab.
Um das Programm klein zu halten, wird jeglicher Speicherplatz dynamisch besorgt. Beim Programmlauf erhält das Programm den benötigten Speicherplatz für Datenstrukturen durch einen Funktionsaufruf. Als Beispiel sind hier die Funktionen „GetSet" und „GetLink" zu nennen. Sie benutzen die C-Bibliotheksfunktion „calloc", welche den dynamischen Speicherplatz vom Betriebssystem besorgt und mit Null vorbelegt. Ist nicht mehr genügend Speicherplatz vorhanden, bricht das Programm mit der Fehlermeldung „not enough memory" ab. Wird dynamisch besorgter Speicherplatz nicht mehr benötigt, geben die Funktionen „FreeSet" und „Release" diesen Platz wieder frei. Damit wird erreicht, daß das Programm nur soviel Speicherplatz belegt, wie die Differenzen der Dateien benötigen. Das hat zur Folge, daß auch sehr große Dateien untersucht werden können, solange sie nicht vollständig verschieden sind. Die Behandlung eines Fehlers geschieht mit den C-Funktionen „setjmp" und „longjmp". Die Funktion „setjmp" speichert eine Stelle des Programmes (Stack-Pointer, Programm-Zähler, usw.) in einer Variablen. Tritt nun irgendwo, also auch in einem Unterprogramm, eine Fehlerbehandlung auf, so kann direkt an die gespeicherte Stelle zurückgesprungen werden, ohne das Unterprogramm zu beenden. Diese Art, Fehlerfälle zu behandeln, ist elegant, aber für die Funktion des Algorithmus nicht zwingend.
Der Algorithmus besitzt zwei Typendefinitionen, FILESET und LIST. Für jede Datei wird mit „GetSet" eine Struktur vom Typ FILESET dynamisch besorgt. In ihr werden alle Kenndaten der Datei, die für den Vergleich relevant sind abgelegt und während des Vergleichs aktualisiert. Diese Strukturen werden bei Beendigung der Funktion „dodfc" mit „FreeSet" wieder freigegeben. Die Datenstruktur vom Typ LIST wird im Vergleichsalgorithmus benötigt.
Die Funktion „dodfc" ruft die eigentliche Vergleichs-Funktion „Compare" auf. Sie liest jeweils eine Zeile aus beiden Dateien mit „Readln" ein. Innerhalb einer While-Schleife wird nun in beiden Dateien so lange gelesen, bis zwei Zeilen verschieden sind. Sind die Dateien gleich, so wird „Compare" mit dem Status „Keine Unterschiede" verlassen und das Programm beendet. Anderenfalls wird von den als unterschiedlich erkannten Zeilen ausgehend für beide Dateien eine Kette von Elementen vom Typ LIST so lange aufgebaut, bis eine Synchronisation gefunden werden konnte. Dies geschieht schrittweise: Die Funktion „Addln" beschafft erst einmal Speicherplatz für ein Kettenelement vom Typ LIST und hängt es in die bestehende Kette ein. Dann liest sie eine Zeile aus der Datei und ermittelt einen Hash-Index [2]. Nun läuft der eigentliche Synchronisationsmechanismus in der Funktion „Sync" an. Zuerst wird die Funktion „Match" gerufen. Sie geht beide Ketten vom Anfang bis zum Ende durch und vergleicht die Hash-Indices zweier Kettenelemente. Hierbei zeigt sich der Vorteil dieser Methode. Sind nämlich zwei Schlüsssei verschieden, so sind es auch die dazugehörenden Zeilen. Sind die Schlüssel gleich, so muß die Gleichheit näher untersucht werden. Dies wird im Programm dann mit der Bibliotheksfunktion „strcmp" gemacht. Kann die Funktion „Match" in den Ketten gleiche Zeilen finden, so liefert sie als Status den Wert 1 der aufrufenden Funktion „Sync" zurück, im anderen Fall den Wert 0. Diese gibt im Fall einer Synchronisation sofort den gefundenen Unterschied mit der Funktion „Report" aus, sorgt mit „Release" dafür, daß die aufgebauten Ketten wieder freigegeben werden und besorgt mit „GetLink" Speicherplatz für die Anfangselemente neuer Kettenelemente. Schließlich wird der Lesezeiger in beiden Dateien richtig gestellt und der von „Match" gelieferte Status-Wert auch an „Compare" weitergeleitet. Konnte keine Synchronisation vorgenommen werden, wird jeweils eine neue Zeile in die entsprechende Kette eingehängt und ein neuer Synchronisationsversuch mit „Sync" gestartet. Konnte jedoch synchronisiert werden, wird die innere Schleife verlassen, zwei neue Zeilen aus den Dateien gelesen und in der äußeren While-Schleife solange weitergelesen, bis verschiedene Zeilen gefunden werden. Die äußere Schleife wird verlassen, wenn beide Dateien vollkommen durchsucht wurden.

Der hier vorgestellte Algorithmus ist natürlich nicht der einzige für derartige Problemstellungen. Es gibt in der Literatur [1] und [3] zwei wesentlich andere Techniken, Dateien zu vergleichen, auf die wir hier nicht weiter eingehen wollen. Der vorgestellte Algorithmus sollte auf jedem Computer mit einem C-Compiler übersetzbar und lauffähig sein. Leser, die mit einem CP/M-System arbeiten, sollten besonders auf die Groß- und Kleinschreibung achten. Eine wesentliche Voraussetzung an den C-Compiler stellen funktionstüchtige I/O-Funktionen wie z.B. „fseek" und „ftell" zum Positionieren des Lesezeigers in Dateien dar. Mit diesen Funktionen steht und fällt der Algorithmus.
Das Programm wurde zuerst unter MS-DOS mit dem Microsoft C-Compiler, Version 3.0 und unter CP/M68k mit dem mitgelieferten C-Compiler von Digital Research in der Version 1.2 und 1.3 entwickelt und erfolgreich getestet. Es läuft aber auch unter den Unix-Systemen ZEUS (Zilog Z8000), Microvax Ultrix BSD 4.2, Intel 80286 mit Xenix 3.5, Convergent Technologies Unix System V, um nur einige zu nennen.