Viele statistische Probleme können dadurch gelöst werden, daß man sie in Teilprobleme zerlegt und deren Lösungen in geeigneter Weise zusammenfügt. Die aus der Informatik bekannte dynamische Programmierung (siehe Sedgewick, 1992, S. 673) eignet sich zur Lösung solcher Probleme, bei denen es sehr viel weniger Teilprobleme als mögliche Zerlegungen gibt. (Beispielsweise gibt es Arten von Problemen, bei denen es in Bezug auf die Größe der betrachteten Datenmenge nur polynomiell viele Teilprobleme, aber exponentiell viele Zuordnungen gibt). In diesen Fällen ist es günstig, die gefundenen Teillösungen in einer Tabelle zu speichern und so sicherzustellen, daß jedes Teilproblem nur einmal gelöst wird.
Nach Sankoff & Kruskal (1983) ist die dynamische Programmierung
für Zuordnungsprobleme verschiedenster Art geeignet. Dazu
gehören etwa der Vergleich der genetischen Codes unterschiedlicher Arten
von Lebewesen oder die Zuordnung eines elektroakustischen Sprachsignales
zu einem geschriebenen Text (Dynamic Time Warping ). Nach Gale & Church (1993)
kann auch die hier betrachtete Satzzuordnung bei zweisprachigen
Texten mit Hilfe der dynamischen Programmierung erfolgreich angegangen
werden. Die folgenden Ausführungen zeigen, wie dies in der Praxis
umgesetzt werden kann.
In Abb. 
wird das Problem der Satzzuordnung dadurch
veranschaulicht, daß man die Zuordnungspositionen der Sätze eines
Ausgangstextes O und der Übersetzung T als Positionen in einem
zweidimensionalen Koordinatensystem auffaßt.
In diesem Koordinatensystem soll nun ein Weg von links unten nach
rechts oben gefunden werden, der zum einen gewissen Vorgaben
enspricht (hier: ein Satz des Ausgangstextes darf entweder 0,
1 oder 2 Sätzen der Übersetzung zugewiesen werden) und zum
zweiten eine Kostenfunktion minimiert. Als Kostenfunktion
für die Satzzuordnung eignet sich die Summe der Längenunterschiede
der einander zugeordneten Sätze, wobei eine vorherige Normalisierung
der Satzlängen vorausgesetzt wird.
Die Vorgehensweise besteht nun darin, daß für jeden Punkt im
Koordinatensystem die Kosten des optimalen Pfades vom Ursprung
bis zu diesem Punkt eingetragen werden.
Dabei sind für jeden
Punkt nur die Werte derjenigen anderen Punkte relevant, die
näher zum Ursprung liegen. Deshalb kann dieser Vorgang
systematisch vom Ursprung aus in fortschreitenden Diagonalen
vorgenommen werden. Gelangt man an den rechten
Abbildung: Satzzuordnung eines Ausgangstextes O und einer Übersetzung T
mittels dynamischer Programmierung.
oberen Punkt des Koordinatensystems, hat man die Kosten des optimalen Pfades, und kann den Pfad selbst von rechts oben nach links unten rekonstruieren. Schneller ist es, schon beim Vorwärts-Durchlauf geeignete Rückwärts-Pointer abzuspeichern, was aber zusätzlichen Speicherplatz benötigt.
In Abb. ist für einen Ausgangstext mit vier und eine
Übersetzung mit fünf Sätzen das Diagramm der Kostenfunktion
dargestellt. Die Kosten jedes Punktes ergeben sich durch Addition
der Kosten des Vorgängerpunktes mit den Kosten, die sich durch
die gerade betrachtete Zuordnung ergeben.
Da viele Punkte des Koordinatensystems von mehreren
Vorgängerpositionen erreicht werden können (gekennzeichnet durch
die Verbindungslinien), wurden für jeden möglichen Weg die Kosten
berechnet. Zur Berechnung der Kosten der nachfolgenden (weiter
rechts liegenden) Positionen wurde jeweils der niedrigste - durch
Fettdruck gekennzeichnete - Wert verwendet. Einige der Pfade im
rechten unteren Bereich der Abbildung erreichen den Endpunkt rechts oben nicht,
das heißt, daß nicht alle Sätze der Übersetzung Zuordnungspartner
finden. Solche Pfade sind unzulässig und brauchen nicht vollständig
berechnet zu werden.
Wie sich aus dem niedrigsten Wert des rechten oberen Punktes ablesen läßt, hat der optimale Pfad Kosten von 41. Der Weg zum Ursprung führt entlang der eingezeichneten Linien über den jeweils niedrigsten, also fett gedruckten Wert. Von rechts oben nach links unten ergeben sich also für die Kostenfunktion die Werte 41, 30, 12, 11 und 0. Dem entspricht die folgende Zuordnung der Sätze:
