Das maschinelle Übersetzungssystem CAT2

4.6 Unifikation

Im Verarbeitungsmodell von CAT2 wird der Begriff Unifikation weiter gefaßt. Mit Unifikation wird auch der Prozeß bezeichnet, der eine Baumstruktur mit den in den verschiedenen Regeln beschriebenen Baumstrukturen vergleicht, und dabei eine Unifikation der Merkmalsstrukturen der Baumstruktur mit den Merkmalsstrukturbeschreibungen der Grammatikregeln vornimmt.

Unifikation von Baumstrukturen

Die Unifikation von Baumstrukturen wird während des Parsens genutzt, um Wurzelknoten eines Objekts mit Tochterknoten von in Regeln beschriebenen Teilbäumen zu unifizieren. Sie wird bei der Transformation genutzt, um die Quellseite einer T-Regel mit Teilstrukturen des Quellobjekts zu unifizieren. Auch während der Anwendung von F-Regeln und TF-Regeln auf ein Objekt ist die Unifikation von Objektstrukturen und Regelstrukturen notwendig.

In allen Regeln existiert die Möglichkeit, für die verschiedenen beschriebenen Knoten Bedingungen und Konsequenzen mit Hilfe des Implikationsoperators '>>' zu formulieren. Nur bei F-Regeln und TF-Regeln wird diese Implikation auch verwirklicht. In allen anderen Fällen wird der Operator im Sinn einer konjunktiven Verknüpfung interpretiert und kann der Effizienzverbesserung dienen.

Zu einer Verbesserung kann es kommen, weil zuerst alle Bedingungsteile geprüft werden, dann erst alle zugehörigen Konsequenzen. Diese Vorgehensweise ermöglicht es, die entscheidenden und evtl. schnell unifizierbaren Merkmale eines Knotens in den Bedingungsteil zu schreiben. Nur wenn die Bedingungsteile aller Knoten des durch die Regel beschriebenen Objekts mit dem Objekt unifizierbar sind, müssen die zeitaufwendigen Unifikationen aller Konsequenzen erfolgen. Während des Parsens tritt jedoch keine Verbesserung ein, da hier nie ganze Objekte unifiziert werden, sondern immer nur einzelne Merkmalsstrukturen.

Die Unifikation der Bedingungen teilt sich in zwei Aufgaben. Die erste Aufgabe besteht darin die Wurzel der Regel und des Objekts mittels Merkmalsunifikation zu vergleichen. Dann werden die Konstituenten betrachtet. Diese können mit Quantoren versehen sein, es besteht die Möglichkeit der disjunktiven Verknüpfung. Die Tochterbäume der Regel müssen sowohl strukturell als auch hinsichtlich ihrer Merkmale mit den Tochterbäumen des Objekts unifizierbar sein. Für jeden Tochterbaum des Objekts wird der Algorithmus von links beginnend rekursiv aufgerufen. Dabei wird der zugehörige Tochterbaum, der in der Regel beschrieben wird, übergeben. Schlug die Unifikation eines Tochterbaumes fehl, wird via Backtracking nach einer anderen strukturellen Lösung gesucht, die durch Quantoren oder Disjunktionen in der Regel möglich ist. Können keine anderen Möglichkeiten gefunden werden, schlägt die gesamte Baumunifikation fehl. Bei jeder erfolgreichen Unifikation eines Tochterbaumes werden, falls welche existieren, die Konsequenzen und die zugehörigen Knoten vermerkt. Diese müssen dann nur noch nacheinander der Merkmalsunifikation unterzogen werden.

Merkmalsunifikation

Merkmalsunifikation findet immer zwischen der Merkmalsstrukturbeschreibung einer Grammatikregel und der Merkmalsstruktur eines linguistischen Objekts statt. Kann ein Constraint von der Merkmalsstruktur nicht entgültig bestätigt werden, d.h. die Merkmalsstruktur besitzt für das entsprechende Merkmal noch keinen Wert, der über die Erfüllung des Constraints eine Aussage treffen könnte, muß das Constraint auf geeignete Art und Weise gespeichert werden, um zu einem späteren Zeitpunkt erneut überprüft werden zu können. Ist statt des Wertes ein schon abgespeichertes Constraint vorhanden, müssen die beiden Constraints auf Verträglichkeit geprüft und gegebenenfalls zusammengefaßt werden.

Eine Merkmalsstrukturbeschreibung FBD soll mit einer Merkmalsstruktur FB unifiziert werden:

Unifikation von positivem Constraint {attr=A} und FB

Wenn FB kein Merkmal attr enthält, wird attr=X in die Merkmalsstruktur FB übernommen. A und die frei Variable X werden unifiziert.
Wenn FB das Merkmal attr mit dem Wert B enthält, wird A mit diesem unifiziert. Sind beide Werte nicht unifizierbar, schlägt die Unifikation fehl.

Unifikation von existentiellem Constraint {attr==A} und FB

Wenn FB kein Merkmal attr enthält, schlägt die Unifikation fehl.
Wenn FB das Merkmal attr mit dem Wert B enthält, wird dieser mit A unifiziert. Sind beide Werte nicht unifizierbar, schlägt die Unifikation fehl.

Unifikation von negativem Constraint {attr~=A} und FB

Es gibt drei prinzipielle Fälle, die bei der Unifikation mit einem negativen Constraint zu unterscheiden sind.

{attr=A} ist kompatibel mit FB. Die Unifikation schlägt fehl.
{attr=A} ist nicht unifizierbar mit FB. Die Unifikation von {attr~=A} und FB ist erfolgreich.
{attr=A} ist unifizierbar mit FB, aber nicht kompatibel. Die Unifikation von {attr~=A} mit FB ist nicht entscheidbar. Das Constraint muß abgespeichert und erneut überprüft werden, wenn eine Variable in FB mit Werten belegt wird.
Enthält FB kein Merkmal attr, wird attr=X in die Merkmalsstruktur FB übernommen und 3. tritt ein.

Kompatibilität zwischen A und B ist exakt definiert durch:

Wenn A ein disjunktives Constraint (A1;A2) ist, muß einer der beiden Werte A1 oder A2 mit B kompatibel sein.
Wenn A ein verkettendes Constraint (A1+A2) ist, muß sich die Zeichenkette B in A1 und A2 zerlegen lassen.
Wenn A ein atomarer Wert ist, muß B atomar und identisch sein, oder eine Variable ohne Constraints.
Wenn A eine Variable ist, muß auch B eine Variable sein.
Wenn A ein komplexer Wert ist, muß auch B ein komplexer Wert sein und für jedes Attribut-Werte-Paar in A existiert das Attribut in B und die Werte sind kompatibel.
Alle weiteren Fälle sind nicht entscheidbar.

Unifikation von atomarem Wert A und Wert B

Wenn B atomar ist und identisch mit A, ist die Unifikation erfolgreich.
Wenn B eine Variable ist, werden nach der Unifikation mit A alle über B gespeicherten Constraints überprüft. Dabei kann die Unifikation fehlschlagen. Außer den über B gespeicherten Constraints müssen auch alle Constraints überprüft werden, die evtl. durch den Wert von B aufgelöst werden können.

Unifikation von komplexem Wert A und Wert B

Bei einem komplexen Wert A handelt es sich wieder um eine Merkmalsstrukturbeschreibung.

Ist B atomar, schlägt die Unifikation fehl.
Ist B eine Merkmalsstruktur wird A mit dieser so unifiziert wie FBD mit FB.
Ist B eine Variable, wird diese mit A unifiziert, die Constraints, die über B abgespeichert sind, oder von dieser Variablen abhängig, sind müssen überprüft werden.

Unifikation von disjunktivem Wert (A1;A2) und B

Ist B ein atomarer Wert, muß er mit einem der beiden Werte A1 und A2 unifizierbar sein, sonst schlägt die gesamte Unifikation fehl.
Ist B eine Merkmalsstruktur kann man drei Fälle unterscheiden:

B kann mit keinem der Disjunkte unifiziert werden, die gesamte Unifikation schlägt fehl.
B kann genau mit einem der Disjunkte unifiziert werden, die Unifikation ist ergfolgreich.
B könnte mit mehreren der Disjunkte unifiziert werden. Die betreffenden Disjunkte werden in einer kleineren Disjunktion zusammengefaßt und das Constraint wird abgespeichert und erneut überprüft, wenn eine der Variablen in B mit einem Wert belegt wird.

Unifikation von implikativem Wert (A1>>A2) und Wert B

Die Merkmalsunifikation mit einem implikativen Constraint ist im Verarbeitungsmodell von CAT2 mit der Semantik einer Konjunktion belegt. Deshalb wird die Unifikation nacheinander mit beiden Teilen der Implikation durchgeführt. Wenn eine Unifikation fehlschlägt, schlägt die gesamte Unifikation fehl. Als Ergebnis dieser Analyse wird das Symbol '>>', wenn es in der Semantik einer Konjunktion verwendet wird, in einer späteren Version von CAT2 durch das Symbol '&' ersetzt.

Unifikation von verkettendem Wert (A1+A2) und Wert B

Wenn B eine Zeichenkette ist, die in die Zeichenketten A1 und A2 zerlegbar ist, ist die Unifikation erfolgreich.
Handelt es sich bei A1 bzw. A2 nicht um eine Zeichenkette, sondern um eine Disjunktion oder eine weitere Verkettung, muß diese aufgelöst werden.
Handelt es sich bei B um eine Variable, mußsen, nach dem Finden einer Lösung und der Unifikation der Variablen mit dieser, alle zur Variablen abgespeicherten Constraints überprüft werden und alle Constraints, die von dieser Variablen abhängen.