Der Cocke-Younger-Kasami-Algorithmus (CYK, oder CKY) ist ein Parsing-Algorithmus für kontextfreie Grammatiken in der Informatik. Er wurde erstmals 1961 von Itiroo Sakai veröffentlicht und später von John Cocke, Daniel Younger, Tadao Kasami und Jacob T. Schwartz wiederentdeckt, nach denen er benannt ist. Der Algorithmus verwendet Bottom-up-Parsing und dynamische Programmierung, um zu bestimmen, ob eine gegebene Zeichenkette von einer gegebenen Grammatik erzeugt werden kann, und er kann auch Parse-Bäume konstruieren. Seine Worst-Case-Laufzeit beträgt O(n^3 · |G|), wobei n die Länge der Eingabezeichenkette und |G| die Größe der Grammatik in Chomsky-Normalform ist, was ihn zu einem der effizientesten Parsing-Algorithmen hinsichtlich der asymptotischen Worst-Case-Komplexität macht, obwohl andere Algorithmen in der Praxis eine bessere durchschnittliche Leistung aufweisen können.
Der CYK-Algorithmus wird häufig in der Verarbeitung natürlicher Sprache und im Compiler-Design eingesetzt, wo Parsing ein grundlegender Schritt ist. Er wird besonders für seine Einfachheit und die garantierte polynomielle Laufzeit geschätzt, selbst für mehrdeutige Grammatiken. Die Abhängigkeit des Algorithmus von dynamischer Programmierung ermöglicht es ihm, alle möglichen Parses systematisch zu behandeln, was in Anwendungen wie der Syntaxanalyse in Programmiersprachen und dem syntaktischen Parsing in Systemen der künstlichen Intelligenz nützlich ist.
Historischer Hintergrund
Der Algorithmus wurde erstmals 1961 von Itiroo Sakai beschrieben, erlangte jedoch durch unabhängige Wiederentdeckungen von John Cocke, Daniel Younger und Tadao Kasami in den späten 1960er Jahren Bedeutung. Jacob T. Schwartz trug ebenfalls zu seiner Entwicklung bei. Der Name des Algorithmus spiegelt diese Wiederentdeckungen wider, wobei das Akronym CYK von Cocke, Younger und Kasami abgeleitet ist. Der Algorithmus wurde zu einem Standardthema in der Informatikausbildung, insbesondere in Kursen über formale Sprachen und Automatentheorie. Seine Entwicklung geht modernen maschinellen Lernansätzen und Ansätzen mit neuronalen Netzen zum Parsing voraus, bleibt aber als grundlegende Technik relevant.
Standardform: Chomsky-Normalform
Die Standardversion des CYK-Algorithmus erfordert, dass die kontextfreie Grammatik in Chomsky-Normalform (CNF) vorliegt. In CNF haben alle Produktionsregeln die Form A → BC (wobei B und C Nichtterminale sind) oder A → α (wobei α ein Terminalsymbol ist). Zusätzlich kann das Startsymbol S eine Produktion S → ε haben, um die leere Zeichenkette zu ermöglichen. Jede kontextfreie Grammatik, die nicht die leere Zeichenkette erzeugt, kann in eine äquivalente CNF-Grammatik transformiert werden, wie von Sipser 1997 gezeigt wurde. Diese Transformation ist algorithmisch und erhält die von der Grammatik erzeugte Sprache. Die CNF-Anforderung vereinfacht den Parsing-Prozess, da sie die Möglichkeiten begrenzt, wie eine Teilzeichenkette in zwei Teile aufgeteilt werden kann, was eine effiziente dynamische Programmierung ermöglicht.
Algorithmusbeschreibung
Der CYK-Algorithmus funktioniert, indem er eine dreidimensionale Tabelle P[l, s, v] füllt, wobei l die Länge einer Teilzeichenkette, s die Startposition dieser Teilzeichenkette und v ein Nichtterminal ist. Der Eintrag P[l, s, v] wird auf wahr gesetzt, wenn die Teilzeichenkette der Länge l, die an Position s beginnt, aus dem Nichtterminal R_v abgeleitet werden kann. Der Algorithmus geht in aufsteigender Reihenfolge der Teilzeichenkettenlänge vor, beginnend mit der Länge 1.
Für jede Teilzeichenkette der Länge 1 prüft der Algorithmus Einheitsproduktionen der Form R_v → a_s, wobei a_s das Terminal an Position s ist. Für Teilzeichenketten der Länge 2 oder größer betrachtet er jede mögliche Aufteilung der Teilzeichenkette in zwei Teile und prüft für jede Produktion A → BC, ob der erste Teil aus B und der zweite Teil aus C abgeleitet werden kann. Wenn dies der Fall ist, markiert er die Teilzeichenkette als aus A ableitbar. Der Algorithmus führt auch eine Backpointer-Tabelle, um die Rekonstruktion von Parse-Bäumen zu ermöglichen.
Am Ende wird die Eingabezeichenkette als Mitglied der Sprache erkannt, wenn P[n, 1, 1] wahr ist, was bedeutet, dass das Startsymbol R_1 die gesamte Zeichenkette ableiten kann. Die Backpointer können dann verwendet werden, um alle möglichen Parse-Bäume zu konstruieren.
Beispiel
Betrachten Sie die folgende Grammatik in CNF:
- S → NP VP
- VP → VP PP
- VP → V NP
- VP → eats
- PP → P NP
- NP → Det N
- NP → she
- V → eats
- P → with
- N → fish
- Det → the
Diese Grammatik kann Sätze wie "she eats the fish with the fork" parsen. Der CYK-Algorithmus würde die Tabelle füllen, indem er zuerst Ein-Wort-Teilzeichenketten markiert: "she" als NP, "eats" als VP oder V, "the" als Det, "fish" als N, "with" als P und "fork" als N. Dann kombiniert er Teilzeichenketten: "the fish" als NP (Det N), "eats the fish" als VP (V NP) und so weiter. Schließlich bestimmt er, dass der gesamte Satz aus S abgeleitet werden kann, und die Backpointer offenbaren die Parse-Baumstruktur.
Anwendungen und Bedeutung
Der CYK-Algorithmus ist in der Parsing-Theorie und -Praxis bedeutend. Er wird in der Verarbeitung natürlicher Sprache für die syntaktische Analyse, im Compiler-Design für das Parsing von Programmiersprachen und in der Bioinformatik für die Vorhersage der RNA-Sekundärstruktur verwendet. Seine Worst-Case-Zeitkomplexität von O(n^3) ist im schlimmsten Fall optimal für das allgemeine Parsing kontextfreier Grammatiken, obwohl spezialisierte Algorithmen wie der Earley-Parser für bestimmte Grammatiken effizienter sein können. Der dynamische Programmieransatz des Algorithmus macht ihn auch für mehrdeutige Grammatiken geeignet, da er alle möglichen Parses aufzählen kann. In der modernen künstlichen Intelligenz wurde der CYK-Algorithmus für die Verwendung in probabilistischen kontextfreien Grammatiken und statistischem Parsing angepasst, wo er den wahrscheinlichsten Parse-Baum angesichts einer Wahrscheinlichkeitsverteilung über Produktionen berechnet.
Einschränkungen und Erweiterungen
Eine Einschränkung des Standard-CYK-Algorithmus ist seine Anforderung an CNF, die die Größe der Grammatik erhöhen und die Effizienz beeinträchtigen kann. Es existieren Erweiterungen für Grammatiken, die nicht in CNF vorliegen, wie der Earley-Algorithmus, der beliebige kontextfreie Grammatiken direkt behandelt. Darüber hinaus wurde der CYK-Algorithmus erweitert, um gewichtete Grammatiken und probabilistische Grammatiken zu behandeln, bei denen jede Produktion ein Gewicht oder eine Wahrscheinlichkeit hat und das Ziel darin besteht, den Parse mit dem maximalen Gewicht oder der maximalen Wahrscheinlichkeit zu finden. Diese Erweiterungen werden in der Spracherkennung und der maschinellen Übersetzung verwendet. Der Algorithmus bildet auch die Grundlage für fortgeschrittenere Parsing-Techniken in Deep-Learning-basierten Modellen, obwohl diese oft Ansätze mit neuronalen Netzen anstelle expliziter Grammatikregeln verwenden.