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 , und , die Übersetzung aus den vier Sätzen , , und . Unter den genannten Einschränkungen sind die in Tabelle  dargestellten Satzzuordnungen möglich.

 

 
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

ergäbe sich das Tupel (0, 2, 2), da Satz mit keinem, die Sätze und aber mit jeweils zwei Sätzen der Übersetzung korrespondieren. Den in Tabelle  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:

 

Hierbei ist n die Anzahl der Sätze im Ausgangstext, ist die Länge des Satzes im Ausgangstext. ist die Länge des dem Satz zugeordneten Satzes in der Übersetzung. Wurden mehrere Sätze zugeordnet, so ergibt sich 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  die längenoptimale Satzzuordnung gefunden wird, sei an einem einfachen Beispiel demonstriert. Der Ausgangstext bestehe aus zwei Sätzen der Längen und . Die Übersetzung bestehe aus drei Sätzen der Längen , und . Für dieses Beispiel existieren nur zwei mögliche Zuordnungen:

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

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

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

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