Alignment

Eine abstrakte Darstellung des Alignments wurde bereits in Abschnitt vorgenommen. Da die Betrachtung dort sehr allgemein ist, wurde die KoKS-Terminologie nicht übernommen. Da die Einheiten, die alignt werden, überwiegend Sätze sind, wird im folgenden vereinfachend von Sätzen gesprochen, obwohl auch Überschriften und Listenelemente Einheiten sein können. In KoKS heißen die Gruppen eines Alignment-Beads Segmente, wie bereits im Abschnitt erwähnt wurde. Leider wird die Segmentendemarkierung auch verwendet, um die Einheiten zu kennzeichnen, aus denen der Aligner die Gruppen bilden darf, sodass mit Segment auch eine einzelne Einheit gemeint sein kann.

Abbildung: aligntes Dokumentpaar

Der Unterschied zwischen Abbildung und zeigt, wie die Markierungen verändert werden, um das Alignment zu repräsentieren. (In dem abgebildeten Ausschnitt liegt ein $1:2$ Alignment-Bead vor.)

Der KoKS-Aligner ist auf Satzalignment spezialisiert. Gruppen können nur aus zusammenhängenden Einheiten gebildet werden, und die Zuordnungen dürfen sich nicht überkreuzen. Etwas ungewöhnlich für einen Satzaligner ist, dass der KoKS-Aligner zwar keine leeren Gruppen erlaubt, aber zugleich die Anzahl der Einheiten in einer Gruppe nicht nach oben beschränkt. Ein KoKS-Alignment ist also eine Abfolge von $n:m$ Zuordnungen mit $n,m>0$.

Die Beschreibung des Aligners ist im KoKS-Abschlussbericht bereits sehr ausführlich. Hier wird trotzdem auf die Funktionsweise eingegangen, da das Alignment der Schlüssel zur Identifikation der Übersetzung innerhalb eines Translation Memorys ist. Des Weiteren wird hier eine andere Sichtweise auf den KoKS-Aligner vorgestellt, mit der die konzeptionellen Defizite des KoKS-Aligners besser verstanden werden können und aus denen sich Verbesserungsmöglichkeiten ableiten lassen.^3.20

Abstandswerte und -matrix

Der KoKS-Aligner bestimmt nicht direkt die Abstände von Gruppen der beiden Sprachseiten Deutsch und Englisch. Es werden immer nur einzelne Sätze miteinander verglichen. Das hat den Vorteil, dass nicht so viele Kombinationen von zu vergleichenden Satzgruppen auftreten. Wenn das deutsche Eingabedokument $m$ Sätze und das englische $n$ Sätze umfasst, dann müssen maximal $mn$ Abstandswerte berechnet werden. Diese Werte können vorab bestimmt und in einer Matrix, die Abstandsmatrix, abgelegt werden, auf die der Alignment-Optimierer zurückgreift.^3.21

In die Berechnung der Abstandswerte fließen verschiedene, linguistisch motivierte Bewertungen ein. Es werden die POS-Tags und Lemmata genutzt, die vom IMS TreeTagger annotiert wurden, und auf ein umfangreiches, bilinguales Wörterbuch zurückgegriffen, das im KoKS-Projekt aus verschiendenen Quellen zusammengestellt wurde.

Zu Wörtern aus offenen Wortklassen werden die Entsprechungen zwischen den Sätzen gezählt, die mit Hilfe des KoKS-Wörterbuchs und den annotierten Grundformen gefunden werden können. Die übrigen Wörter aus offenen Wortklassen werden zu einer Zeichenkette je Sprachseite zusammengefügt und mit einem Abstandsmaß verglichen, das bereits auf kurze übereinstimmenden Zeichenfolgen anspricht und die Reihenfolge der Übereinstimmungen nachrangig behandelt. Schließlich werden die Wörter aus geschlossenen Wortklassen gezählt, um ihre Anzahl zu vergleichen. Weitere Informationen, z.B. der Anteil der einzelnen Wortarten, werden nicht ausgewertet.

Da die Abstandswertberechnung viel Zeit beansprucht, werden unter verschiedenen Bedingungen Werte durch den minimalen oder maximalen Abstandswert abgeschätzt. Betroffen sind hiervon beispielsweise Sätze aus Absätzen, die sich nicht entsprechen. (Siehe KoKS-Abschlussbericht für Details.) Das Laufzeitverhalten des KoKS-Aligners ist trotzdem mindestens quadratisch, da die volle Abstandsmatrix mit $mn$ Einträgen erzeugt werden muss und die Dokumentlängen $m$ und $n$ deutlich korrelieren.^3.22In der Praxis ist vor allem ein Problem, dass der Speicherbedarf der Abstandsmatrix quadratisch mit der Länge der Eingabedateien wächst.

Pfadrepräsentation eines Alignments

In einer Abstandsmatrix fallen in der Regel längere Diagonalfolgen von Matrixzellen mit niedrigen Abstandswerten auf. Sie deuten auf Sequenzen von $1:1$ zu alignenden Sätzen hin. Im KoKS-Projekt wurde daher entschieden, zum Bestimmen eines Alignments einen Pfad in der Abstandsmatrix zu suchen, der über Zellen führt, deren Abstandswerte in der Summe möglichst klein sind. Der Pfad soll die Zellen $(1,1)$ und $(m,n)$ verbinden, da angenommen wird, dass das erste Alignment-Bead mindestens die ersten Sätze der zu alignenden Dokumente und entsprechend das letzte Bead die letzten Sätze enthält.

Jeder Pfad setzt sich aus einer Abfolge von Zellen zusammen. Nachfolger einer Zelle $(i,j)$ können $(i+1,j)$, $(i,j+1)$ und $(i+1,j+1)$ sein, sofern sie innerhalb der Matrix liegen. Graphentheoretisch gesprochen handelt es sich um einen gerichteten Graphen mit $mn$ Knoten und $(m-1)(n-1)+n(m-1)+m(n-1) = 3mn-2(m+n)+1$ Kanten.

Abbildung: Anzahl der Pfade in der Abstandsmatrix

Die Zahl der möglichen Pfade von $(1,1)$ zu jeder einzelnen Zelle zeigt Abbildung für eine 9 x 16 Matrix. In der Darstellung liegt $(1,1)$ oben links. In dieser Matrix kann man die Anzahl der möglichen Alignmentpfade für verschieden große Abstandsmatrizen ablesen. Beispielsweise gibt es 41 Alignmentpfade in einer 5 x 3 Abstandsatrix. Eine einfache, nicht rekursive Formel für die Anzahl der Pfade liegt nicht nahe. Im KoKS-Abschlussbericht wird ein exponentielles Verhalten zur Größe der Matrix vermutet. Die Werte in der Nähe der in der Abbildung hervorgehobenen Diagonalen wachsen überexponentiell zu $i+j-2$.^3.23

Wie ein Pfad als Alignment interpretiert werden kann, ist nicht offensichtlich. Andere Zuordnungen als $1:1$ Zuordnungen treten immer dann auf, wenn der Pfad nicht diagonal verläuft. Eine rechte oder untere Nachbarzelle vergrößert das aktuelle Alignment-Bead um die Sätze, deren Abstand die Matrixzelle enthält.

Abbildung: Pfadrepräsentation von Alignments

Abbildung zeigt einige Pfade und die Art der Zuordnung. Die einzelnen Zeichenpositionen entsprechen Zellen einer Abstandsmatrix. Die Zellen, über die der jeweilige Pfad führt, sind mit X markiert. Oben links und unten rechts in jedem Teilbild ist der weitere Verlauf des Pfades angedeutet. Teilbilder b und c zeigen, dass es für $m:n$ Zuordnungen mit $\min(m,n) > 1$ immer zwei mögliche Pfadeverläufe gibt. In e/f wird deutlich, dass kleine Änderungen zu einem ganz anderen Alignment führen können.

Optimierung

Der KoKS-Aligner sucht einen Pfad in der Abstandsmatrix mit möglichst geringer Summe der Abstandswerte. Die Suche wird mit dem A-Stern-Algorithmus und einer Heuristik, die die minimale Abstandssumme zwischen zwei beliebigen Matrixzellen abschätzt, effizient durchgeführt. So konnte selbst eine 699 x 685 Matrix in wenigen Minuten verarbeitet werden, obwohl die Anzahl der möglichen Pfade bei $6,6 * 10^{528}$ liegt.

Teilpfade wie in b bis e (Abbildung ) können nur gewählt werden, wenn eine Abkürzung der Ecke wie in Teilbild f nicht zu einer geringeren Abstandswertsumme führt. Das ist nur möglich, wenn die Eckzelle den Abstandswert null hat, da negative Abstandswerte nicht erlaubt sind.^3.24Treten $k$ solche Eckzellen am Alignment-Pfad auf, dann gibt es $2^k$ optimale Pfade. Welchen der Alignmentoptimierer wählt, hängt von Details der Implementation ab. Da nicht positive Abstandswerte sehr ungewöhnlich sind, erzeugt der KoKS-Aligner also im Regelfall nur $n:1$ und $1:n$ Zuordnungen mit $n \ge 1$. ^3.25

Ausblick

Um die hier geschildertert Probleme des Aligners und andere zu lösen, die bereits im KoKS-Abschlussbericht beschrieben werden, wurde eine neue Pfadrepräsentation und Pfadbewertung entworfen und implementiert. Die Repräsentation erlaubt alle Zuordnungsarten, auch $n:0$. Beibehalten wurde, dass die Gruppen zusammenhängend sein müssen und nicht über kreuz alignt werden können. Die Beschränkung der Abstandswertberechnung auf Satzpaare wurde aufgegeben zugunsten einer Berechnung nach Bedarf für beliebige Gruppenpaare. Erste Experimente zeigten ein gutes Laufzeitverhalten. Jedoch war keine Zeit vorhanden für einen gründlichen Test des Aligners und die Feinabstimmung der Parameter.

Es ist unklar, ob sich der Aufwand für die Entwicklung eines neuen Aligners lohnt, da der KoKS-Aligner bereits eine (für die Anwendungen im KoKS-Projekt und in dieser Arbeit) zufrieden stellende Alignmentqualität erreicht. Das ist ein weiterer Grund, warum der Ansatz nicht weiter verfolgt wurde.

Fußnoten

... lassen.^3.20

In diesem Zusammenhang möchte der Autor auch Patrick Tschorn, der wesentlich Komponenten des KoKS-Aligner entwickelt hat, für die zahlreichen Gespräche über Alignment danken.

... zurückgreift.^3.21

Ausschlaggebend für diese Trennung war im KoKS-Projekt, dass so die Entwicklung des Aligners auf zwei Projektmitglieder verteilt werden konnte. Später (nach der Einführung der Umlautkorrektur) konnten gespeicherte Abstandsmatrizen tatsächlich wiederverwertet und so mehrere Tage Rechenzeit eingespart werden.

... korrelieren.^3.22

Im KoKS-Projekt wurden zwar einige Komponenten für eine kompaktere Repräsentation der Matrizen angepasst. Es gelang aber nicht mehr, ein reibungsfreies Zusammenspiel herzustellen, sodass auf eine Darstellung, die sämtliche Werte der Matrix auflistet, nicht ganz verzichtet werden konnte.

....^3.23

Bei einer Beschreibung der Pfadanzahl $v$ mittels $v=b(i,j)^{i+j-2}$ liegen die Basen $b(i,j) = \sqrt[i+j-2]{v}$ in einem Bereich der Matrix über zwei, der sich ca. $\pm{27}$ Grad um die Diagonale herum öffnet. Soweit die Folge $b(i,i)$ mit dem Python Modul ,,math`` berechnet werden kann und vorausgesetzt, es treten keine numerischen Probleme auf, wächst sie streng monoton mit abnehmender Zuwachsrate. Die größte quadratische Matrix, die berechnet werden konnte, reicht bis $i=405$. Die Basen wachsen über $2,4$ nur noch sehr langsam. Möglicherweise konvergiert die Folge, sodass die Pfadanzahl in O$(b^{i+j-2})$ mit $b>2,403$ liegt.

... sind.^3.24

Das KoKS-Abstandsmaß gibt leider doch negative Werte aus. In den vorhandenen Abstandsmatrizen wurden Werte zwischen $-10^{-8}$ und $-10^{-9}$ beobachtet. Vermutlich sind numerische Probleme die Ursache und die Werte müssten eigentlich null sein.

.... ^3.25

Es wurde nochmal der Quellcode des Aligners durchgesehen, ob nicht doch weitere Faktoren in die Pfadbewertung einfließen. Des Weiteren wurde mit einer manuell erstellten Matrix versucht, eine $3:3$ Zuordnung zu erzwingen. Ebenso wurden die Alignmentpfade zu 10 mit Zufallswerten gefüllten 51 x 52 Matrizen bestimmt. Auch hier trat kein Pfad auf, der über Eck führt.