next up previous contents index
Next: Satzzuordnung für lange Texte Up: Die maschinelle Generierung von Previous: Die Bestimmung korrespondierender Sätze

Ein Algorithmus zur maschinellen Satzzuordnung

Für die Entwicklung des nachfolgend beschriebenen Algorithmus wurde der von Brown et al. (1990) verwendete Ansatz aufgegriffen. Die Grundidee ist hierbei, daß die Satzlängen einander entsprechender Sätze in Ausgangstext und Übersetzung eine Abhängigkeit aufweisen. Lange Sätze im Ausgangstext korrespondieren in der Regel mit langen Sätzen in der Übersetzung und umgekehrt. Weiterhin wird die Reihenfolge einander entsprechender Sätze in Ausgangstext und Übersetzung normalerweise dieselbe sein. Sicherlich kann es jedoch vereinzelt vorkommen, daß Sätze ausgelassen werden, daß mehrere Sätze zu einem zusammengefaßt werden oder daß umgekehrt ein Satz in mehrere Sätze zerlegt wird. In einem noch allgemeineren Fall werden Satzgrenzen nicht eingehalten. Der Inhalt von m Sätzen des Ausgangstextes wird dann durch n Sätze der Übersetzung ausgedrückt.

Die Entwicklung eines Algorithmus, der alle diese Möglichkeiten berücksichtigt und dennoch effizient arbeitet, dürfte auf erhebliche Schwierigkeiten stoßen. Deshalb wurden für die vorliegende Studie einige Vereinfachungen vorgenommen. Berücksichtigt werden nur die folgenden häufig auftretenden Fälle der Satzzuordnung:

  1. Ein Satz des Ausgangstextes korrespondiert mit genau einem Satz in der Übersetzung
  2. Ein Satz des Ausgangstextes wurde nicht übersetzt, d. h. es existiert kein korrespondierender Satz in der Übersetzung
  3. Die Übersetzung eines Satzes des Ausgangstextes besteht aus zwei Sätzen
Die Übersetzung eines Satzes durch mehr als zwei Sätze, Vertauschungen in der Satzreihenfolge sowie die Verschiebung von Satzgrenzen werden also nicht erkannt. Auch der gegenüber Punkt 3 umgekehrte Fall, nämlich die Übersetzung von zwei Sätzen des Ausgangstextes durch einen Satz, wird nicht berücksichtigt, um in der folgenden Beschreibung eine größere Transparenz zu erzielen. Dadurch weist das Verfahren aber in Bezug auf Ausgangstext und Übersetzung eine Asymmetrie auf.

Die Arbeitsweise des Algorithmus soll an einem Beispiel erläutert werden. Der Ausgangstext bestehe aus den drei Sätzen tex2html_wrap_inline24748 , tex2html_wrap_inline24750 und tex2html_wrap_inline24752 , die Übersetzung aus den vier Sätzen tex2html_wrap_inline24754 , tex2html_wrap_inline24756 , tex2html_wrap_inline24758 und tex2html_wrap_inline24760 . Unter den genannten Einschränkungen sind die in Tabelle gif dargestellten Satzzuordnungen möglich.

 

tex2html_wrap24886 tex2html_wrap24888 tex2html_wrap24890

tex2html_wrap24892 tex2html_wrap24894 tex2html_wrap24896

 
Tabelle: Mögliche Satzzuordnungen für einen Ausgangstext im Umfang von drei und eine Übersetzung im Umfang von vier Sätzen

Diese Darstellung läßt sich etwas abstrakter durch ein Zahlentupel ausdrücken, das jedem Satz des Originaltupels die Anzahl der ihm zugeordneten Sätze der Übersetzung zuweist. Für den Fall der Zuordnung

tex2html_wrap24898

ergäbe sich das Tupel (0, 2, 2), da Satz tex2html_wrap_inline24748 mit keinem, die Sätze tex2html_wrap_inline24750 und tex2html_wrap_inline24752 aber mit jeweils zwei Sätzen der Übersetzung korrespondieren. Den in Tabelle gif dargestellten Zuordnungen entsprechen also folgende Tupel:

  1. (0, 2, 2)
  2. (1, 1, 2)
  3. (1, 2, 1)
  4. (2, 0, 2)
  5. (2, 1, 1)
  6. (2, 2, 0)

Diese Tupel lassen sich algorithmisch erzeugen, indem ein Zähler, dessen Stellenzahl der Anzahl der Sätze im Ausgangstext entspricht, im Dreiersystem bei Null beginnend schrittweise inkrementiert wird. Unter den so erzeugten Zahlentupeln werden diejenigen ausgewählt, deren Quersumme mit der Anzahl der Sätze in der Übersetzung übereinstimmt. Auf diese Weise werden sämtliche unter den genannten Einschränkungen möglichen Satzzuordnungen generiert.

Diese werden nacheinander einer Bewertung unterzogen. Die Zuordnung mit der besten Bewertung ist das vom System erzielte Ergebnis. Ausgangspunkt für die Festlegung der Bewertungsfunktion ist die Überlegung, daß sich einander zugeordnete Sätze in ihrer Länge möglichst wenig unterscheiden sollten. Es wird also eine Längendifferenz  D gemessen, die wie folgt berechnet wird:

  equation15424

Hierbei ist n die Anzahl der Sätze im Ausgangstext, tex2html_wrap_inline24814 ist die Länge des Satzes tex2html_wrap_inline24816 im Ausgangstext. tex2html_wrap_inline24818 ist die Länge des dem Satz tex2html_wrap_inline24816 zugeordneten Satzes in der Übersetzung. Wurden tex2html_wrap_inline24816 mehrere Sätze zugeordnet, so ergibt sich tex2html_wrap_inline24818 als Summe der Längen dieser Sätze. v ist ein Verhältnisfaktor, der berücksichtigen soll, daß unterschiedliche Sprachen für die Formulierung desselben Sachverhaltes oftmals eine deutlich unterschiedliche Textlänge benötigen. Dieses Verhältnis liegt nach Angaben aus Gale & Church (1991) beispielsweise für das Sprachpaar Deutsch/Englisch bei etwa 1,1 und für Französisch/Englisch bei 1,06.

Als Länge eines Satzes wird hier nicht wie bei Brown et al. (1991) die Anzahl der Wörter, sondern stattdessen die Anzahl der Zeichen in einem Satz verstanden. Gale & Church (1991) haben gezeigt, daß dadurch die statistische Unsicherheit etwas vermindert werden kann. Dies leuchtet unmittelbar ein, wenn man z. B. an die unterschiedliche Schreibweise zusammengesetzter Wörter im Englischen und Deutschen denkt. Ein weiterer Vorteil dieses Vorgehens ist, daß eine Festlegung, welche Zeichenketten als Wörter verstanden werden sollen, entbehrlich ist.

Wie mit Hilfe von Formel gif die längenoptimale Satzzuordnung gefunden wird, sei an einem einfachen Beispiel demonstriert. Der Ausgangstext bestehe aus zwei Sätzen der Längen tex2html_wrap_inline24828 und tex2html_wrap_inline24830 . Die Übersetzung bestehe aus drei Sätzen der Längen tex2html_wrap_inline24832 , tex2html_wrap_inline24834 und tex2html_wrap_inline24836 . Für dieses Beispiel existieren nur zwei mögliche Zuordnungen:

tex2html_wrap24900 tex2html_wrap24902 tex2html_wrap24904

   figure15437
Abbildung: Vergleich der beiden Zuordnungsmöglichkeiten für die Beispielsätze.

In graphischer Darstellung ergibt sich das in Abb. gif gezeigte Bild. Die Anwendung von Formel gif ergibt unter Annahme von v=1 für den in Abb. gif links dargestellten Fall

tex2html_wrap_inline24880

Für den in Abb. gif rechts dargestellten Fall ergibt sich hingegen

tex2html_wrap_inline24882

Auf Grund des kleineren Wertes für D ist also die rechte Zuordnung gegenüber der linken vorteilhafter, was mit der Anschauung übereinstimmt.


next up previous contents index
Next: Satzzuordnung für lange Texte Up: Die maschinelle Generierung von Previous: Die Bestimmung korrespondierender Sätze

Reinhard Rapp
Fri Jul 18 19:19:31 MET DST 1997