CKY-Parsing (auch CYK genannt, für Cocke-Younger-Kasami) ist ein Parsing-Algorithmus für kontextfreie Grammatiken, der Bottom-up-Parsing und dynamische Programmierung verwendet. Er wurde erstmals 1961 von Itiroo Sakai veröffentlicht und später unabhängig von John Cocke, Daniel Younger, Tadao Kasami und Jacob T. Schwartz wiederentdeckt, nach denen er benannt ist. Der Algorithmus bestimmt, ob eine gegebene Zeichenkette von einer Grammatik erzeugt werden kann, und kann, falls dies der Fall ist, alle möglichen Parse-Bäume für diese Zeichenkette konstruieren.
Die Standardversion von CKY arbeitet nur mit kontextfreien Grammatiken in Chomsky-Normalform (CNF), bei der jede Produktionsregel entweder die Form A → BC (zwei Nichtterminale) oder A → a (ein Terminal) hat. Jede kontextfreie Grammatik, die nicht die leere Zeichenkette erzeugt, kann algorithmisch in eine äquivalente CNF-Grammatik transformiert werden, sodass diese Einschränkung die Anwendbarkeit des Algorithmus prinzipiell nicht begrenzt. Für Grammatiken, die die leere Zeichenkette erzeugen, kann man explizit eine Regel S → ε zulassen, wobei S das Startsymbol ist.
Die Bedeutung des CKY-Parsings ergibt sich aus seiner Worst-Case-Zeitkomplexität von O(n^3 · |G|), wobei n die Länge der Eingabezeichenkette und |G| die Größe der CNF-Grammatik ist. Dies macht ihn zu einem der effizientesten Parsing-Algorithmen in Bezug auf das asymptotische Worst-Case-Verhalten, obwohl andere Algorithmen in praktischen Szenarien bessere durchschnittliche Laufzeiten aufweisen können.
Algorithmus-Überblick
Der Algorithmus funktioniert, indem er eine dreidimensionale Tabelle P[l, s, v] füllt, wobei jeder Eintrag ein boolescher Wert ist, der angibt, ob die Teilzeichenkette der Länge l, die an Position s beginnt, aus dem Nichtterminal R_v erzeugt werden kann. Die Tabelle wird in aufsteigender Reihenfolge der Teilzeichenkettenlänge gefüllt, beginnend mit Teilzeichenketten der Länge 1.
Für jedes Terminalsymbol in der Eingabe überprüft der Algorithmus alle Einheitsproduktionen der Form R_v → a_s und markiert die entsprechenden Tabelleneinträge als wahr. Für längere Teilzeichenketten betrachtet er jede mögliche Partition der Teilzeichenkette in zwei Teile und prüft, ob es eine Produktion A → BC gibt, sodass B den ersten Teil und C den zweiten Teil erzeugt. Wenn eine solche Produktion existiert, wird der Eintrag für A auf wahr gesetzt.
Pseudocode
sei die Eingabe eine Zeichenkette I, die aus n Zeichen besteht: a1 ... an.
sei die Grammatik mit r Nichtterminalen R1 ... Rr, mit Startsymbol R1.
sei P[n,n,r] ein Array von Booleans. Initialisiere alle Elemente von P auf false.
sei back[n,n,r] ein Array von Listen von Backpointer-Tripeln. Initialisiere alle Elemente von back auf die leere Liste.
für jedes s = 1 bis n
für jede Einheitsproduktion Rv → as
setze P[1,s,v] = true
für jedes l = 2 bis n -- Länge der Spanne
für jedes s = 1 bis n-l+1 -- Beginn der Spanne
für jedes p = 1 bis l-1 -- Partition der Spanne
für jede Produktion Ra → Rb Rc
wenn P[p,s,b] und P[l-p,s+p,c] dann
setze P[l,s,a] = true,
füge <p,b,c> an back[l,s,a] an
wenn P[n,1,1] wahr ist dann
I ist Mitglied der Sprache
gib back zurück -- durch Nachverfolgen der Schritte durch back kann man leicht alle möglichen Parse-Bäume der Zeichenkette konstruieren.
sonst
gib "kein Mitglied der Sprache" zurück
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
Det → the
N → fish
Um die Zeichenkette "she eats the fish with the fish" zu parsen, markiert der Algorithmus zunächst alle Teilzeichenketten der Länge 1. Zum Beispiel wird P[1,1,NP] auf true gesetzt, weil NP → she, und P[1,2,VP] wird auf true gesetzt, weil VP → eats. Dann verarbeitet er Teilzeichenketten der Länge 2, wie "she eats", die als S → NP VP abgeleitet werden kann, sodass P[2,1,S] wahr wird. Der Prozess wird für längere Teilzeichenketten fortgesetzt, wobei alle Partitionen berücksichtigt werden. Am Ende, wenn P[n,1,S] wahr ist, wird die Zeichenkette als Teil der Sprache erkannt, und die Backpointer ermöglichen die Rekonstruktion des Parse-Baums.
Anwendungen und Varianten
CKY-Parsing wird häufig in der Verarbeitung natürlicher Sprache und der Computerlinguistik verwendet, insbesondere für das Parsing mit probabilistischen kontextfreien Grammatiken. Varianten des Algorithmus wurden entwickelt, um gewichtete Grammatiken zu verarbeiten und die Durchschnittsleistung zu verbessern. Der dynamische Programmierungsansatz des Algorithmus verbindet ihn auch mit anderen Parsing-Methoden, wie dem Earley-Parser, der beliebige kontextfreie Grammatiken ohne CNF-Konvertierung verarbeitet, aber eine ähnliche Worst-Case-Komplexität aufweist.
In modernen Systemen der künstlichen Intelligenz wurde das CKY-Parsing weitgehend durch neuronale Netze basierte Ansätze ersetzt, insbesondere durch Transformer-Modelle, die in großen Sprachmodellen verwendet werden. Der Algorithmus bleibt jedoch eine wichtige grundlegende Technik in der Theorie der formalen Sprachen und wird weiterhin in Informatik-Lehrplänen gelehrt. Seine Prinzipien der dynamischen Programmierung und der Bottom-up-Analyse erscheinen auch in anderen Bereichen, wie Sequenz-zu-Sequenz-Modellen und Beam-Search-Dekodierung.
Die Effizienz und Klarheit des Algorithmus haben ihn zu einem Standardbeispiel in Lehrbüchern über Parsing und maschinelles Lernen gemacht. Forschungseinrichtungen wie MIT CSAIL und Stanford AI Lab haben zu seiner Erforschung und Anwendung beigetragen, und er bleibt in Bereichen relevant, die exaktes Parsing strukturierter Daten erfordern, wie Bioinformatik und Compiler-Design.
Einschränkungen
CKY-Parsing erfordert, dass die Grammatik in Chomsky-Normalform vorliegt, was die Anzahl der Produktionsregeln und die Größe der Grammatik erhöhen kann. Die Worst-Case-Zeitkomplexität von O(n^3) kann für sehr lange Eingabezeichenketten prohibitiv sein, insbesondere in Echtzeitanwendungen. Darüber hinaus ist die Raumkomplexität des Algorithmus O(n^2 · r), was für Grammatiken mit vielen Nichtterminalen groß sein kann. Trotz dieser Einschränkungen bleibt CKY-Parsing ein Maßstab für exakte Parsing-Algorithmen und ein Schlüsselkonzept in der Untersuchung kontextfreier Sprachen.