              synopse.nw

Unterstützung beim Finden von Parallelstellen

Felix Gärtner

Juli 1996

Inhaltsverzeichnis

1 Einleitung 1

2 Benutzung 2

3 Beschaffenheit der Eingabetexte 2

4 Der Code 2 4.1 Überblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 4.2 Parameter und Alphabet . . . . . . . . . . . . . . . . . . . . . . . 3 4.3 Der Programmrahmen . . . . . . . . . . . . . . . . . . . . . . . . 4 4.4 Datenstrukturen . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 4.5 Sonstige Vorarbeiten . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.6 Vorbereitungen für die Textsuche . . . . . . . . . . . . . . . . . . 12

5 Index der Verfeinerungen 17

6 Index der Bezeichner 17

1 Einleitung

Im Sommer 1996 hatte ich eine Seminararbeit zu schreiben, in der es um Peter Schneiders Erzählung “Lenz” ging. Hauptinhalt sollte eine genaue Analyse eines der wesentlichen Stilmerkmale von Schneiders Text sein, nämlich die absichtlichoffensichtliche Neuformulierung eines historisch-literarischen Stoffes, in diesem Falle Büchners fragmentarische Erzählung “Lenz”. Dabei hat Peter Schneider nicht nur die Thematik und das Genre beibehalten, sondern hat auch in fast ungenierter Art und Weise sich Büchners Stil und Duktus angenähert, so daß Schneiders Werk an manchen Stellen einer Kopie des originales “Lenz” gleicht. Diese Tatsache ist bereits mehrfach untersucht worden, doch fehlt bisher eine genaue und systematische Bestandsaufnahme aller Parallelstellen in beiden Werken. Eine solche Gegenüberstellung sollte Hauptteil meiner Seminararbeit sein.

Da sowohl Büchners als auch Schneiders Texte maschinenlesbar vorlagen, lag es nahe, die Suche nach Parallelstellen durch Computer unterstützen zu lassen. Im Rahmen dieses Vorhabens entstand dieses Programm. Es soll zwei Texte gegenüberstellen und in ganz rudimentärer Art und Weise Indikatoren auf Parallelstellen liefern, die dann noch vn Hand überprüft und verfeinert werden müssen.

2 Benutzung

Das Programm heißt synopse und nimmt die Namen zweier ASCII-Dateien als Eingabe. Es liefert auf die Standardausgabe eine Flut von Mitteilungen und Meldungen über vermutete Parallelstellen.

3 Beschaffenheit der Eingabetexte

Die beiden Eingabetexte müssen lesbaren ASCII-Text enthalten. Umlaute sollten in der TEX-Codierung des german.sty-Dokumentstils codiert sein, d.h. “"a” für “ä”, “"U” für “Ü” und “"s” für “ß”. Die Gänsefüßchen werden auch im TEX-Format erwartet, d.h. “``” als öffnende und “''” als schließende Gänsefüßchen. Liegt der Text nicht in dieser Form vor, so sollte er mit einem Texteditor vorberarbeitet werden.

Der Eingabetext kann (und sollte) zum besseren Wiederfinden von Textstellen Informationen über Seitenzahlen enthalten. Die Seitenzahlen sollten am Ende der Seite als Zahlen uneingerückt in einer eigenen Zeile stehen. Verweise auf Worte dieser Seite werden dann immer mit dieser Seitenzahl getätigt. Worte auf der ersten Seite werden im Zweifelsfalle als “auf Seite 0 befindlich” angezeigt.

4 Der Code

4.1 Überblick

Die Idee des Programmes ist einfach. Text A wird mit Text B verglichen, indem schrittweise aus Text A Wortsequenzen einer gegebenen Länge l herausgeschnitten und anschließend in Text B gesucht werden. Zur Suche des Musters in Text B wird ein standardmäßiges Zeichenketten-Suchverfahren benutzt, in unserem Falle der Algorithmus von Boyer und Moore. Da statt Zeichenketten hier Wortketten gesucht werden, werden die Texte zuerst Wort für Wort in eine Folge von Zahlen “übersetzt”. Die Zahlen sind dann das Alphabet, über dem gesucht wird.

Ein kurzes Wort zur Komplexität des Verfahrens: Bei einer Musterlänge von m Wörtern hat der Algorithmus von Boyer und Moore eine Komplexität, die in der Größenordnung O(|B| + m) liegt, wenn |B| die Anzahl der Wörter des zu durchsuchenden Textes B ist. Da wir den Algorithmus im Prinzip \frac{|A|}{m}- mal starten, bekommen wir im Endeffekt eine Komplexität von O(|A| · |B|), wenn wir die Länge des Musters vernachlässigen. Somit verbietet sich dieses Verfahren auch nur für Texte durchschnittlicher Größe, zumal der Aufwand der Nachbereitung, die der Mensch zu leisten hat, aufgrund der vielen gefundenen “Blindgänger” nicht mehr vertretbar ist.

4.2 Parameter und Alphabet

Folgende Parameter bestimmen das Verfahren und können nach Bedarf “getuned” werden:

• pattern length: Länge des aus Text A herausgeschnittenen Musters.

• max word number: Maximale Anzahl von Worten in Text A oder B. Dient zur Dimensionierung

• max word length: Maximale Anzahl von Zeichen in einem Wort. Dient zur Dimensionierung des Eingabepuffers (siehe Seite 8).

• context before: Maximale Anzahl von Worten, die bei einem gefundenen Treffer als Kontext vor der Parallelstelle angezeigt werden.

• context after: Maximale Anzahl von Worten, die bei einem gefundenen Treffer als Kontext nach der Parallelstelle angezeigt werden. (Dient zur Indentifizierung der Qualität von Treffern.)

3a  ⟨Defines 3a⟩≡  (4b) 3b ▷

  #define pattern_length 2
  #define max_word_number 60000
  #define max_word_length 100     /* it's German */
  #define context_before 2
  #define context_after 5

Defines:

context after, used in chunk 15.

context before, used in chunk 15.

max word length, used in chunks 5b, 8b, and 9b.

max word number, used in chunks 5b, 6, and 10.

pattern length, used in chunks 5b, 6, 11–13, 15, and 16.

Das Alphabet, in welches die Wörter überführt werden ist eine einfache Hash-Funktion auf Zeichenketten. Die ASCII-Werte der einzelnen Buchstaben werden modulo einer großen Primzahl zusammenaddiert. Da Peter Schneiders Text ca 30.000 Wörter umfaßt, ist eine Primzahl über 32.000 sicherlich ausreichend.

3b  ⟨Defines 3a⟩+≡  (4b) ◁ 3a

  #define hash_prime 32003        /* large prime for hashing */

Defines:

hash prime, used in chunk 4a.

Die Hash-Funktion, die die Wörter auf Zahlen abbildet, benutzt diese Primzahl. Sie nimmt eine Zeichenkette als Eingabe und spuckt die zugehörige Hash-Zahl aus.

4a  ⟨Functions 4a⟩≡  (4b) 7a ▷

int hash( char* word ) {
  int h = 1;
  while ( *word != '\0' ) {
    h = (h * (int) *word) % hash_prime;
    word++;
  }
  return(h);
}

Defines:

hash, used in chunk 10.

Uses hash prime 3b.

4.3 Der Programmrahmen

4b ⟨* 4b⟩≡

/* synopse.nw   (c) by F.G. 1996 */

⟨Defines 3a⟩

⟨Includes 4c⟩

⟨Globals 5a⟩

⟨Functions 4a⟩

int main(int argc, char* argv[]) {

⟨Check command line 5b⟩

⟨Convert input files to word and number arrays 11f⟩ ⟨Do the hard work and output results to stdout 12b⟩

  printf("finished\n");
  return(0);
}

Defines:

main, never used. Uses c 8b.

Natürlich werden wir in irgendeiner Form die standardsisierten Ein- und Ausgabe-Funktionen benutzen:

4c  ⟨Includes 4c⟩≡  (4b) 11c ▷

#include<stdio.h>

Auf der Kommandozeile sind keine Optionen erlaubt. Benötigt werden allerdings zwei Dateinamen. Wir wollen Zeiger auf diese beiden Namen in den beiden globalen Variablen text a name und text b name speichern. Außerdem wird der Programmname in einer weiteren globalen Variablen gespeichert.

5a  ⟨Globals 5a⟩≡  (4b) 6 ▷

char* text_a_name = NULL;  /* names of input files */
char* text_b_name = NULL;
char* progname = NULL;     /* name od program */

Defines:

progname, used in chunks 5b and 8–10. text a name, used in chunks 5b, 11f, and 15. text b name, used in chunks 5b, 11f, and 15.

Die Kommandozeile kann dann wie folgt bearbeitet werden:

5b  ⟨Check command line 5b⟩≡  (4b)

progname = argv[0];
if (argc != 3) {
  printf("%s: help finding word sequence parallels in two texts\n",
    progname);
  printf("(pattern length %d, max. %d words per text, %d chars per word).\n",
    pattern_length, max_word_number, max_word_length);
  printf("usage: %s file1 file2\n", progname);
  exit(1);
}
text_a_name = argv[1];
text_b_name = argv[2];
Uses max word length 3a, max word number 3a, pattern length 3a, progname 5a,
text a name 5a, and text b name 5a.

4.4 Datenstrukturen

Die globalen Datenstrukturen, auf denen gearbeitet wird, sind riesige Wort- und Zahlenfelder. Sie erlauben effizienten Zugriff auf einzelne Elemente, müssen jedoch von vornherein dimensioniert sein. Der Wert max word number gibt dieses Maximum an. Mit diesem Wert können die großen Arbeitsfelder definiert werden. Die Felder plaintext a und plaintext b enthalten den lesbaren Text, text a und text b den übersetzten Text als Hash-Zahl. Außerdem gibt es ein zum jeweiligen Text analoges Feld, welches den Indices eine Seitenzahl zuordnet. Dieses Feld gibt es für beide Texte, d.h. pages a und pages b. Will man z.B. die Seitenzahl des Wortes an Position i aus dem Feld text a wissen, so findet man sie unter der Nummer pages a[i].

Um den später vorgestellten Algorithmus zu vereinfachen, werden auf Seite 11 noch pattern length “Stopper” ans Ende der Felder angefügt, weshalb die Felder etwas größer dimensioniert werden als auf den ersten Blick nötig. Wenn man sicherstellt, daß der Algorithmus nie auf derartige Elemente in den Seitenzahlen-Feldern zugreift, dann braucht man diese Felder nicht derart groß zu machen.

6  ⟨Globals 5a⟩+≡  (4b) ◁ 5a 12a ▷

  char* plaintext_a [max_word_number + pattern_length];
  char* plaintext_b [max_word_number + pattern_length];
  int text_a [max_word_number + pattern_length];
  int text_b [max_word_number + pattern_length];
  int pages_a[max_word_number];
  int pages_b[max_word_number];

Defines:

pages a, used in chunks 11f, 12b, and 15.

pages b, used in chunks 11f and 15.

plaintext a, used in chunks 11f, 12b, and 15.

plaintext b, used in chunks 11f and 15.

text a, used in chunks 11–13 and 15.

text b, used in chunks 11f, 13, and 15.

Uses max word number 3a and pattern length 3a.

Eine nützliche Routine zeigt n aufeinanderfolgende Worte aus einem beliebigen Feld ab Position start auf dem Bildschirm an. Die einzelnen Worte werden durch Leerzeichen getrennt. Der Rufer muß sicherstellen, daß start einen sinnvollen Wert besitzt, d.h. nicht auf ein Element hinter dem letzten Wort des Feldes zeigt. Die Funktion print words erkennt dafür, wenn sie über das Ende des Feldes hinausschießt und bricht ihre Arbeit in diesem Falle (ohne Fehler) ab.

7a  ⟨Functions 4a⟩+≡  (4b) ◁ 4a 7b ▷

  void print_words(char* word_array[], int start, int n) {
    int u;
    for (u=0; u < n-1; u++) {
      if (word_array[start+u] != NULL) {
        printf("%s ", word_array[start + u]);
      } else {
        return;
      }
    }
    if (word_array[start+u] != NULL) {
      printf("%s", word_array[start + u]);
    }
    return;
  }

Defines:

print words, used in chunks 12b and 15.

4.5 Sonstige Vorarbeiten

Das Einlesen der Dateien und das herauslesen der einzelnen Wörter ist vielleicht die umständlichste Programmierarbeit in diesem ganzen Text. Da wir die Sache zweimal durchführen müssen, wäre eine eigene Funktion dafür angebracht. So wird’s auch gemacht. Die Routine wird gleichzeitig mit dem Herauslesen der Wörter Seitenzahlen im Text erkennen und das Seitenzahl-Feld des entsprechenden Textes füllen.

7b  ⟨Functions 4a⟩+≡  (4b) ◁ 7a 14 ▷

  void read_file(char* filename, char* word_array[], int number_array[],
      int page_array[]) {

⟨Locals of read file 7c⟩

⟨Read file filename into the two arrays 8a⟩

  }

Defines:

read file, used in chunk 11f.

7c  ⟨Locals of read file 7c⟩≡  (7b) 8b ▷

  FILE* input_file;

Defines:

input file, used in chunks 8a, 9a, and 11e.

Zuerst müssen die Dateien geöffnet werden.

8a  ⟨Read file filename into the two arrays 8a⟩≡  (7b) 9a ▷

input_file = fopen( filename, "r" );
if (input_file == NULL) {
  printf("%s: can't open %s", progname, filename);
  exit(1);
}
Uses input file 7c and progname 5a.

Anschließend kann mit dem wortweisen Lesen begonnen werden. Es werden zunächst alle Zeichen eines Wortes in einen Puffer gelesen. Ein Wort ist beendet, wenn ein Leerzeichen, Tabulator oder ein Zeilenumbruch (sogenanntes whitespace) gelesen wurde. Der Puffer beschränkt auch die maximale Wortlänge.

Die zuletzt gelesene Seitenzahl (d.h. die Seite, auf der sich die gerade gelesenen Wörter befinden), steht in der Variablen current page geschrieben. Initialisiert wird sie mit dem Wert 0, was der “ersten Seite” entspricht. Sie wird verwendet, um die Seitenzahlen-Felder zu füllen.

8b  ⟨Locals of read file 7c⟩+≡  (7b) ◁ 7c

char word_buffer[max_word_length];  /* input buffer */
char c;                              /* mini input buffer */
int buffer_ptr = 0;
int word_count = 0;
int line_count = 1;
int current_page = 0;

Defines:

buffer ptr, used in chunks 9 and 10. c, used in chunks 4b, 9, and 11a. current page, used in chunk 10. line count, used in chunk 9. word buffer, used in chunks 9–11. word count, used in chunks 9–11.

Uses max word length 3a.

Das Lesen ist eine simple getc-Schleife, in der neue Zeichen so lange ans Ende des Puffers angefügt werden, bis eines der genanntes whitespace-Zeichen erscheint. Über das gerade gelesene Zeichen wird eine Fallunterscheidung gemacht, damit man noch flexibel besondere Zeichen wir Satzzeichen oder Gänsefüßchen aussortieren kann. Der Wert von buffer ptr zeigt immer auf das nächste freie Feld in word buffer]. Die Variable word count zählt die gefundenen Wörter und behält dabei den Überblick, an welcher Stelle in den großen Wort- und Zahlenfeldern wir als nächstes etwas einzutragen haben.

9a  ⟨Read file filename into the two arrays 8a⟩+≡  (7b) ◁ 8a 11d ▷

  word_count = 0;
  line_count = 0;
  buffer_ptr = 0;
  while ( (c = (char) getc(input_file)) != EOF ) {
    switch (c) {
    case ' ' : case '\t' : case '\n' :
      if (c == '\n') line_count++;

⟨Found new word: save it 10⟩

      break;
    case ',' : case '.' : case ':' : case '\'' : case '`' :
    case ';' : case '?' : case '-' :
      /* ignore */
      break;
    default:

⟨Append character c to the buffer 9b⟩

    }
  }
Uses buffer ptr 8b, c 8b, input file 7c, line count 8b, and word count 8b.

Das Anhängen des Zeichens an den Wortpuffer ist einfach. Nur muß darauf geachtet werden, ob die maximale Wortlänge schon erreicht ist oder nicht.

9b  ⟨Append character c to the buffer 9b⟩≡  (9a)

  word_buffer[buffer_ptr] = (char) c;
  buffer_ptr++;
  if (buffer_ptr == max_word_length) {
    printf("%s: word too long in line %d (max. %d chars)\n",
      progname, line_count, max_word_length);
    exit(1);
  }
Uses buffer ptr 8b, c 8b, line count 8b, max word length 3a, progname 5a,
  and word buffer 8b.

Eine Folge von Zeichen wurde nun gelesen und ein whitespace-Zeichen entdeckt! Was ist zu tun? Zuerst einmal könnte die gelesene Zeichenfolge auch leer sein. In diesem Falle ist natürlich nichts zu tun. Ansonsten liegt im word buffer zwischen Position 0 und buffer ptr−1 das Wort. Zuerst muss ein terminierendes Null-Byte an dessen Ende gesetzt werden, bevor es in einen frischen Bereich des Hauptspeichers kopiert werden kann, der dann nur noch in die großen Felder eingereiht werden muß.

Allerdings könnte sich es bei dem Wort ja auch um eine Seitenzahl handeln! Dies wird rechtzeitig abgeprüft und nötigenfalls der Wert von current page korrigiert.

10  ⟨Found new word: save it 10⟩≡  (9a)

if (buffer_ptr != 0) {
char* new_home;
word_buffer[buffer_ptr] = '\0';

if ⟨Word is a page number 11a⟩ { current_page = ⟨Value of page number 11b⟩;

/* printf("found new page number %d\n", current_page); */
} else {
new_home = (char*) malloc( buffer_ptr + 1 );
if (new_home == NULL) {
  printf("%s: low on memory\n", progname);
  exit(1);
}
strcpy(new_home, word_buffer);
word_array[word_count] = new_home;
number_array[word_count] = hash(new_home);
page_array[word_count] = current_page;
/* printf("%s:%s*%d on page %d\n", filename, new_home,
    hash(new_home), current_page); */
word_count++;
if (word_count == max_word_number) {
  printf("%s: too many words in %s (max. %d allowed)\n",
    progname, filename, max_word_number);
  exit(1);
}
}
buffer_ptr = 0;
}
Uses buffer ptr 8b, current page 8b, hash 4a, max word number 3a, progname 5a,
word buffer 8b, and word count 8b.

Hier geben wir eine Heuristik an, wie Seitenzahlen erkannt werden können: Erstens müssen alle Zeichen Ziffern sein, zweitens muß der Wert von c noch einen Zeilenvorschub enthalten.

11a  ⟨Word is a page number 11a⟩≡  (10)

((c == '\n') && (atoi(word_buffer) != 0))

Uses c 8b and word buffer 8b.

11b  ⟨Value of page number 11b⟩≡  (10)

atoi(word_buffer)
Uses word buffer 8b.

11c  ⟨Includes 4c⟩+≡  (4b) ◁ 4c

#include <stdlib.h>

Außerdem werden hier noch ans Ende der großen Felder (also an die Positionen word count) bestimmte Marken geschrieben, damit man beim linearen Durchsuchen der Datenstrukturen auch das Ende erkennt. Es werden genau pattern length+1 Stopper eingefügt, um dem nacher vorgestellten Algorithmus zu vereinfachen (vgl. hierzu den Algorithmus auf Seite 13).

11d  ⟨Read file filename into the two arrays 8a⟩+≡  (7b) ◁ 9a 11e ▷

{
  int i;
  for (i=0; i<pattern_length+1; i++) {
    word_array[word_count + i] = NULL;
    number_array[word_count + i] = -1;
  }
}
Uses pattern length 3a and word count 8b.

Bevor es noch vergessen wird, wird die Datei schnell noch geschlossen.

11e  ⟨Read file filename into the two arrays 8a⟩+≡  (7b) ◁ 11d

printf("Read %d words from file %s\n", word_count, filename);
fclose(input_file);
Uses input file 7c and word count 8b.

Jetzt das Ganze für beide Texte.

11f  ⟨Convert input files to word and number arrays 11f⟩≡  (4b)

read_file(text_a_name, plaintext_a, text_a, pages_a);
read_file(text_b_name, plaintext_b, text_b, pages_b);
Uses pages a 6, pages b 6, plaintext a 6, plaintext b 6, read file 7b, text a 6,
text a name 5a, text b 6, and text b name 5a.

4.6 Vorbereitungen für die Textsuche

In den folgenden Programmabschnitten geht die eigentliche Arbeit los. Zuerst wird der erste Eingabetext Schritt für Schritt in Abschnitte der Länge muster laenge zerschnitten. Diese herausgeschnittenen Muster werden dann an den zweiten Text angelegt und mit dem Boyer-Moore-Verfahren gesucht.

Der Beginn des herausgeschnittenen Musters im text a wird angezeigt durch den Wert der Variable pattern start. Ab dort stehen pattern length “Zeichen”, die im text b gesucht werden.

12a  ⟨Globals 5a⟩+≡  (4b) ◁ 6

  int pattern_start = 0;     /* pointer to beginning of pattern */

Defines:

pattern start, used in chunks 12b, 13, and 15.

Hier beginnt also die große erste Schleife, die jeweils immer ein neues Muster ausschneidet und die Textsuche damit beginnt. Beendet wird die Schleife, wenn das Muster das erste Stop-Zeichen am Ende des Feldes erreicht.

12b  ⟨Do the hard work and output results to stdout 12b⟩≡  (4b)

  while (text_a[pattern_start + pattern_length] >= 0) {
    /*
    printf("\nsearching for `");
    print_words(plaintext_a, pattern_start, pattern_length);
    printf("' (from page %d)\n", pages_a[pattern_start]);
    */
    ⟨Search text a[pattern start .. pattern start + pattern length] in text b 13⟩
    pattern_start++;
  }
Uses pages a 6, pattern length 3a, pattern start 12a, plaintext a 6, print words 7a,
  and text a 6.

Nun also zum bekannten Boyer-Moore-Algorithmus. Die von mir benutzte Quelle ist das Buch von Ottmann/Widmayer [3].

13  ⟨Search text a[pattern start .. pattern start + pattern length] in text b 13⟩≡  (12b)
{
int i, j;
i = pattern_length;           /* pointer into text_b */
j = pattern_length;           /* pointer into the pattern */
while (text_b[i-1] >= 0) {
while ((text_b[i-1] >= 0) && (j>=1)) {
if (text_b[i-1] == text_a[pattern_start + j-1]) {
  i--; j--;
} else { /* mismatch */
  int d = delta(text_a, pattern_start, pattern_length,
      text_b[i-1]);
  if (pattern_length - j + 1 > d) {
    i = i + pattern_length - j + 1;
  } else {
    i = i + d;
  }
  j = pattern_length;
}
}
/* text_b[i] < 0 or j<1 */
if (j<1) {

⟨Mangle match found at index i in text b 15⟩

i = i + pattern_length + 1;
j = pattern_length;
}
}
}
Uses delta 14, pattern length 3a, pattern start 12a, text a 6, and text b 6.

Die Funktion delta berechnet den Abstand des ersten Auftretens des Zeichens mismatch char vom rechten Rand des Musters. Das Muster wird als Zeiger auf den Start des Feldes und den Abstand offset angegeben. Tritt das Zeichen nicht im Muster auf, so liefert delta die Gesamtlänge des Musters zurück.

14  ⟨Functions 4a⟩+≡  (4b) ◁ 7b

  int delta(int pat_array[], int offset, int pat_length,
      int mismatch_char) {
    int i;
    for (i = pat_length - 1; i>=0; i--) {
      if (mismatch_char == pat_array[offset + i]) {
        return(pat_length -1 -i);
      }
    }
    return(pat_length);
  }

Defines:

delta, used in chunk 13.

Sagen wir, wir haben eine Übereinstimmung der Länge pattern length gefunden. Dann können wir die Sache auf die Spitze treiben und solange weitersuchen, wie die Übereinstimmung anhält (und solange wir in beiden Feldern noch nicht das Ende erreicht haben). Ist diese Arbeit getan, wird das gesamte Ergebnis dieser Übereinstimmung in möglichst nützlicher Weise ausgegeben.

15  ⟨Mangle match found at index i in text b 15⟩≡  (13)

{
int start_of_context;
int t = pattern_length;
while ((text_b[i + t] == text_a[pattern_start + t]) &&
    (text_a[pattern_start + t] >= 0) &&
    (text_b[i + t] >= 0)) {
  t++;
  printf("t=%d A[%d]=%d B[%d]=%d\n", t, pattern_start + t,
    text_a[pattern_start + t], i+t, text_b[i + t]);
}
printf("\n");
printf("match length %d, pattern from %s (A), target from %s (B):\n",
  t, text_a_name, text_b_name);
/* Location A */
printf("v location A: total %d, page %d, context ", pattern_start,
  pages_a[pattern_start]);
if (pattern_start - context_before < 0) {
  start_of_context = 0;
} else {
  start_of_context = pattern_start - context_before;
}
printf("(%d before, %d behind)\n", pattern_start - start_of_context,
  context_after);
print_words(plaintext_a, start_of_context, pattern_length + t +
    context_after);
printf("\n");
/* Location B */
if (i - context_before < 0) {
  start_of_context = 0;
} else {
  start_of_context = i - context_before;
}
print_words(plaintext_b, start_of_context, pattern_length + t +
    context_after);
printf("\n");
printf("^location B: total %d, page %d, context ", i, pages_b[i]);

    printf("(%d before, %d behind)\n", i - start_of_context,
      context_after);

⟨Cheat i into thinking pattern length was longer 16⟩

  }
Uses context after 3a, context before 3a, pages a 6, pages b 6, pattern length 3a,
  pattern start 12a, plaintext a 6, plaintext b 6, print words 7a, text a 6,
  text a name 5a, text b 6, and text b name 5a.

Weil das nachträgliche Suchen doch manchmal erfolgreich ist, müssen wir den Wert von i nach der Ausgabe der Übereinstimmung behutsam anheben, so daß nicht nochmals nach demselben Muster gesucht wird (jetzt nur um ein Zeichen versetzt). Dies wird ganz einfach gemacht, nämlich indem wir den Wert von i um t-pattern length erhöhen, denn t-pattern length war ja gerade der zusätzliche Betrag, um den das gefundene Muster länger war als pattern length.

16  ⟨Cheat i into thinking pattern length was longer 16⟩≡  (15)

  i = i + t - pattern_length;
Uses pattern length 3a.

5 Index der Verfeinerungen

⟨* 4b⟩ ⟨Append character c to the buffer 9b⟩ ⟨Cheat i into thinking pattern length was longer 16⟩ ⟨Check command line 5b⟩ ⟨Convert input files to word and number arrays 11f⟩ ⟨Defines 3a⟩ ⟨Do the hard work and output results to stdout 12b⟩ ⟨Found new word: save it 10⟩ ⟨Functions 4a⟩ ⟨Globals 5a⟩ ⟨Includes 4c⟩ ⟨Locals of read file 7c⟩ ⟨Mangle match found at index i in text b 15⟩ ⟨Read file filename into the two arrays 8a⟩

⟨Search text a[pattern start .. pattern start + pattern length] in
  text b 13⟩

⟨Value of page number 11b⟩ ⟨Word is a page number 11a⟩

6 Index der Bezeichner

buffer ptr: \underline{8b}, 9a, 9b, 10 c: 4b, \underline{8b}, 9a, 9b, 11a

context after: \underline{3a}, 15
context before: \underline{3a}, 15
current page: \underline{8b}, 10

delta: 13, \underline{14} hash: \underline{4a}, 10

hash prime: \underline{3b}, 4a

input file: \underline{7c}, 8a, 9a, 11e

line count: \underline{8b}, 9a, 9b
main: \underline{4b}
max word length: \underline{3a}, 5b, 8b, 9b
max word number: \underline{3a}, 5b, 6, 10

pages a: \underline{6}, 11f, 12b, 15 pages b: \underline{6}, 11f, 15 pattern length: \underline{3a}, 5b, 6, 11d, 12b, 13, 15, 16 pattern start: \underline{12a}, 12b, 13, 15 plaintext a: \underline{6}, 11f, 12b, 15

plaintext b: \underline{6}, 11f, 15
print words: \underline{7a}, 12b, 15

progname: \underline{5a}, 5b, 8a, 9b, 10

read file: \underline{7b}, 11f

text a: \underline{6}, 11f, 12b, 13, 15 text a name: \underline{5a}, 5b, 11f, 15 text b: \underline{6}, 11f, 13, 15 text b name: \underline{5a}, 5b, 11f, 15 word buffer: \underline{8b}, 9b, 10, 11a, 11b word count: \underline{8b}, 9a, 10, 11d, 11e

Literatur

[1] Peter Schneider: Lenz. Eine Erzählung. Berlin: Rotbuch Verlag, 1973 (= Rotbuch 104).

[2] R.S. Boyer, J.S. Moore:

[3] Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen. Mannheim, Wien, Zürich: BI-Wissenschaftsverlag, 1990.