synopse.nw
Unterst"utzung beim Finden von Parallelstellen

Felix G"artner
Juli 1996

Table of Contents

Einleitung

Im Sommer 1996 hatte ich eine Seminararbeit zu schreiben, in der es um Peter Schneiders Erz"ahlung ``Lenz'' ging. Hauptinhalt sollte eine genaue Analyse eines der wesentlichen Stilmerkmale von Schneiders Text sein, n"amlich die absichtlich-offensichtliche Neuformulierung eines historisch-literarischen Stoffes, in diesem Falle B"uchners fragmentarische Erz"ahlung ``Lenz''. Dabei hat Peter Schneider nicht nur die Thematik und das Genre beibehalten, sondern hat auch in fast ungenierter Art und Weise sich B"uchners Stil und Duktus angen"ahert, so da"s 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"uberstellung sollte Hauptteil meiner Seminararbeit sein.

Da sowohl B"uchners als auch Schneiders Texte maschinenlesbar vorlagen, lag es nahe, die Suche nach Parallelstellen durch Computer unterst"utzen zu lassen. Im Rahmen dieses Vorhabens entstand dieses Programm. Es soll zwei Texte gegen"uberstellen und in ganz rudiment"arer Art und Weise Indikatoren auf Parallelstellen liefern, die dann noch vn Hand "uberpr"uft und verfeinert werden m"ussen.

Benutzung

Das Programm hei"st synopse und nimmt die Namen zweier ASCII-Dateien als Eingabe. Es liefert auf die Standardausgabe eine Flut von Mitteilungen und Meldungen "uber vermutete Parallelstellen.

Beschaffenheit der Eingabetexte

Die beiden Eingabetexte m"ussen lesbaren ASCII-Text enthalten. Umlaute sollten in der TeX-Codierung des german.sty-Dokumentstils codiert sein, d.h. ``"a'' f"ur ``"a'', ``"U'' f"ur ``"U'' und ``"s'' f"ur ``"s''. Die G"ansef"u"schen werden auch im TeX-Format erwartet, d.h. ````'' als "offnende und ``'''' als schlie"sende G"ansef"u"schen. 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 "uber Seitenzahlen enthalten. Die Seitenzahlen sollten am Ende der Seite als Zahlen uneinger"uckt in einer eigenen Zeile stehen. Verweise auf Worte dieser Seite werden dann immer mit dieser Seitenzahl get"atigt. Worte auf der ersten Seite werden im Zweifelsfalle als ``auf Seite 0 befindlich'' angezeigt.

Der Code

"Uberblick

Die Idee des Programmes ist einfach. Text A wird mit Text B verglichen, indem schrittweise aus Text A Wortsequenzen einer gegebenen L"ange l herausgeschnitten und anschlie"send in Text B gesucht werden. Zur Suche des Musters in Text B wird ein standardm"a"siges 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"ur Wort in eine Folge von Zahlen ``"ubersetzt''. Die Zahlen sind dann das Alphabet, "uber dem gesucht wird.

Ein kurzes Wort zur Komplexit"at des Verfahrens: Bei einer Musterl"ange von m W"ortern hat der Algorithmus von Boyer und Moore eine Komplexit"at, die in der Gr"o"senordnung O(|B|+m) liegt, wenn |B| die Anzahl der W"orter des zu durchsuchenden Textes B ist. Da wir den Algorithmus im Prinzip frac|A|m-mal starten, bekommen wir im Endeffekt eine Komplexit"at von O(|A||B|), wenn wir die L"ange des Musters vernachl"assigen. Somit verbietet sich dieses Verfahren auch nur f"ur Texte durchschnittlicher Gr"o"se, zumal der Aufwand der Nachbereitung, die der Mensch zu leisten hat, aufgrund der vielen gefundenen ``Blindg"anger'' nicht mehr vertretbar ist.

Parameter und Alphabet

Folgende Parameter bestimmen das Verfahren und k"onnen nach Bedarf ``getuned'' werden: 

<Defines>= (U->) [D->]
#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, context_before, max_word_length, max_word_number, pattern_length (links are to index).

Das Alphabet, in welches die W"orter "uberf"uhrt werden ist eine einfache Hash-Funktion auf Zeichenketten. Die ASCII-Werte der einzelnen Buchstaben werden modulo einer gro"sen Primzahl zusammenaddiert. Da Peter Schneiders Text ca 30.000 W"orter umfa"st, ist eine Primzahl "uber 32.000 sicherlich ausreichend. 

<Defines>+= (U->) [<-D]
#define hash_prime 32003        /* large prime for hashing */
Defines hash_prime (links are to index).

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

<Functions>= (U->) [D->]
int hash( char* word ) {
  int h = 1;
  while ( *word != '\0' ) {
    h = (h * (int) *word) % hash_prime;
    word++;
  }
  return(h);
}
Defines hash (links are to index).

Der Programmrahmen

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

<Defines>

<Includes>

<Globals>

<Functions>

int main(int argc, char* argv[]) {
  <Check command line>
  <Convert input files to word and number arrays>
  <Do the hard work and output results to stdout> 
  printf("finished\n");
  return(0);
}
Defines main (links are to index).

Nat"urlich werden wir in irgendeiner Form die standardsisierten Ein- und Ausgabe-Funktionen benutzen: 

<Includes>= (<-U) [D->]
#include<stdio.h>

Auf der Kommandozeile sind keine Optionen erlaubt. Ben"otigt 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"serdem wird der Programmname in einer weiteren globalen Variablen gespeichert. 

<Globals>= (<-U) [D->]
char* text_a_name = NULL;  /* names of input files */
char* text_b_name = NULL;
char* progname = NULL;     /* name od program */
Defines progname, text_a_name, text_b_name (links are to index).

Die Kommandozeile kann dann wie folgt bearbeitet werden: 

<Check command line>= (<-U)
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];

Datenstrukturen

Die globalen Datenstrukturen, auf denen gearbeitet wird, sind riesige Wort- und Zahlenfelder. Sie erlauben effizienten Zugriff auf einzelne Elemente, m"ussen jedoch von vornherein dimensioniert sein. Der Wert max_word_number gibt dieses Maximum an. Mit diesem Wert k"onnen die gro"sen Arbeitsfelder definiert werden. Die Felder plaintext_a und plaintext_b enthalten den lesbaren Text, text_a und text_b den "ubersetzten Text als Hash-Zahl. Au"serdem gibt es ein zum jeweiligen Text analoges Feld, welches den Indices eine Seitenzahl zuordnet. Dieses Feld gibt es f"ur 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"ater vorgestellten Algorithmus zu vereinfachen, werden auf Seite [->] noch pattern_length ``Stopper'' ans Ende der Felder angef"ugt, weshalb die Felder etwas gr"o"ser dimensioniert werden als auf den ersten Blick n"otig. Wenn man sicherstellt, da"s der Algorithmus nie auf derartige Elemente in den Seitenzahlen-Feldern zugreift, dann braucht man diese Felder nicht derart gro"s zu machen. 

<Globals>+= (<-U) [<-D->]
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, pages_b, plaintext_a, plaintext_b, text_a, text_b (links are to index).

Eine n"utzliche 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"s sicherstellen, da"s start einen sinnvollen Wert besitzt, d.h. nicht auf ein Element hinter dem letzten Wort des Feldes zeigt. Die Funktion print_words erkennt daf"ur, wenn sie "uber das Ende des Feldes hinausschie"st und bricht ihre Arbeit in diesem Falle (ohne Fehler) ab. 

<Functions>+= (<-U) [<-D->]
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 (links are to index).

Sonstige Vorarbeiten

Das Einlesen der Dateien und das herauslesen der einzelnen W"orter ist vielleicht die umst"andlichste Programmierarbeit in diesem ganzen Text. Da wir die Sache zweimal durchf"uhren m"ussen, w"are eine eigene Funktion daf"ur angebracht. So wird's auch gemacht. Die Routine wird gleichzeitig mit dem Herauslesen der W"orter Seitenzahlen im Text erkennen und das Seitenzahl-Feld des entsprechenden Textes f"ullen. 

<Functions>+= (<-U) [<-D->]
void read_file(char* filename, char* word_array[], int number_array[],
    int page_array[]) {
  <Locals of read_file>
  <Read file filename into the two arrays>
}
Defines read_file (links are to index).

<Locals of read_file>= (<-U) [D->]
FILE* input_file;
Defines input_file (links are to index).

Zuerst m"ussen die Dateien ge"offnet werden. 

<Read file filename into the two arrays>= (<-U) [D->]
input_file = fopen( filename, "r" );
if (input_file == NULL) {
  printf("%s: can't open %s", progname, filename);
  exit(1);
}

Anschlie"send kann mit dem wortweisen Lesen begonnen werden. Es werden zun"achst 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"ankt auch die maximale Wortl"ange.

[*] Die zuletzt gelesene Seitenzahl (d.h. die Seite, auf der sich die gerade gelesenen W"orter 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"ullen. 

<Locals of read_file>+= (<-U) [<-D]
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, c, current_page, line_count, word_buffer, word_count (links are to index).

Das Lesen ist eine simple getc-Schleife, in der neue Zeichen so lange ans Ende des Puffers angef"ugt werden, bis eines der genanntes whitespace-Zeichen erscheint. "Uber das gerade gelesene Zeichen wird eine Fallunterscheidung gemacht, damit man noch flexibel besondere Zeichen wir Satzzeichen oder G"ansef"u"schen aussortieren kann. Der Wert von buffer_ptr zeigt immer auf das n"achste freie Feld in word_buffer]. Die Variable word_count z"ahlt die gefundenen W"orter und beh"alt dabei den "Uberblick, an welcher Stelle in den gro"sen Wort- und Zahlenfeldern wir als n"achstes etwas einzutragen haben. 

<Read file filename into the two arrays>+= (<-U) [<-D->]
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>
    break;
  case ',' : case '.' : case ':' : case '\'' : case '`' :
  case ';' : case '?' : case '-' :
    /* ignore */
    break;
  default:
    <Append character c to the buffer>
  }
}

Das Anh"angen des Zeichens an den Wortpuffer ist einfach. Nur mu"s darauf geachtet werden, ob die maximale Wortl"ange schon erreicht ist oder nicht. 

<Append character c to the buffer>= (<-U)
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);
}

Eine Folge von Zeichen wurde nun gelesen und ein whitespace-Zeichen entdeckt! Was ist zu tun? Zuerst einmal k"onnte die gelesene Zeichenfolge auch leer sein. In diesem Falle ist nat"urlich 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"sen Felder eingereiht werden mu"s.

Allerdings k"onnte sich es bei dem Wort ja auch um eine Seitenzahl handeln! Dies wird rechtzeitig abgepr"uft und n"otigenfalls der Wert von current_page korrigiert. 

<Found new word: save it>= (<-U)
if (buffer_ptr != 0) {
  char* new_home;
  word_buffer[buffer_ptr] = '\0';
  if <Word is a page number> {
    current_page = <Value of page number>;
    /* 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;
}

Hier geben wir eine Heuristik an, wie Seitenzahlen erkannt werden k"onnen: Erstens m"ussen alle Zeichen Ziffern sein, zweitens mu"s der Wert von c noch einen Zeilenvorschub enthalten. 

<Word is a page number>= (<-U)
((c == '\n') && (atoi(word_buffer) != 0))


<Value of page number>= (<-U)
atoi(word_buffer)


<Includes>+= (<-U) [<-D]
#include <stdlib.h>

Au"serdem werden hier noch ans Ende der gro"sen 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"ugt, um dem nacher vorgestellten Algorithmus zu vereinfachen (vgl. hierzu den Algorithmus auf Seite [->]).

[*] 

<Read file filename into the two arrays>+= (<-U) [<-D->]
{
  int i;
  for (i=0; i<pattern_length+1; i++) {
    word_array[word_count + i] = NULL;
    number_array[word_count + i] = -1;
  }
}

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

<Read file filename into the two arrays>+= (<-U) [<-D]
printf("Read %d words from file %s\n", word_count, filename);
fclose(input_file);

Jetzt das Ganze f"ur beide Texte. 

<Convert input files to word and number arrays>= (<-U)
read_file(text_a_name, plaintext_a, text_a, pages_a);
read_file(text_b_name, plaintext_b, text_b, pages_b);

Vorbereitungen f"ur die Textsuche

In den folgenden Programmabschnitten geht die eigentliche Arbeit los. Zuerst wird der erste Eingabetext Schritt f"ur Schritt in Abschnitte der L"ange 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. 

<Globals>+= (<-U) [<-D]
int pattern_start = 0;     /* pointer to beginning of pattern */
Defines pattern_start (links are to index).

Hier beginnt also die gro"se 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. 

<Do the hard work and output results to stdout>= (<-U)
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>
  pattern_start++;
}

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

[*] 

<Search text_a[pattern_start .. pattern_start + pattern_length]  in text_b>= (<-U)
{ 
  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>
      i = i + pattern_length + 1;
      j = pattern_length;
    }
  }
}

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"ange des Musters zur"uck. 

<Functions>+= (<-U) [<-D]
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 (links are to index).

Sagen wir, wir haben eine "Ubereinstimmung der L"ange pattern_length gefunden. Dann k"onnen wir die Sache auf die Spitze treiben und solange weitersuchen, wie die "Ubereinstimmung anh"alt (und solange wir in beiden Feldern noch nicht das Ende erreicht haben). Ist diese Arbeit getan, wird das gesamte Ergebnis dieser "Ubereinstimmung in m"oglichst n"utzlicher Weise ausgegeben. 

<Mangle match found at index i in text_b>= (<-U)
{
  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>
}

Weil das nachtr"agliche Suchen doch manchmal erfolgreich ist, m"ussen wir den Wert von i nach der Ausgabe der "Ubereinstimmung behutsam anheben, so da"s nicht nochmals nach demselben Muster gesucht wird (jetzt nur um ein Zeichen versetzt). Dies wird ganz einfach gemacht, n"amlich indem wir den Wert von i um t-pattern_length erh"ohen, denn t-pattern_length war ja gerade der zus"atzliche Betrag, um den das gefundene Muster l"anger war als pattern_length. 

<Cheat i into thinking pattern_length was longer>= (<-U)
i = i + t - pattern_length;

Index der Verfeinerungen

Index der Bezeichner

References

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

[2] R.S. Boyer, J.S. Moore: [3] Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen. Mannheim, Wien, Z"urich: BI-Wissenschaftsverlag, 1990.

*