Cocke-Younger-Kasami-Algorithmus

Der Cocke-Younger-Kasami-Algorithmus (CYK-Algorithmus) ist ein Algorithmus aus dem Gebiet der theoretischen Informatik. Mit ihm lässt sich feststellen, ob ein Wort zu einer bestimmten kontextfreien Sprache gehört. In der Fachsprache bezeichnet man dies als Lösen des Wortproblems für kontextfreie Sprachen. Mit Hilfe von Backtracking kann der Parse-Tree bzw. die Parse-Trees eines gegebenen Wortes der Sprache konstruiert werden. Um den Algorithmus anzuwenden, muss zu der vorgegebenen Sprache eine Grammatik in Chomsky-Normalform vorliegen. Der in den 1960er Jahren von Itiroo Sakai, John Cocke, Tadao Kasami, Jacob Schwartz und Daniel Younger unabhängig voneinander entwickelte Algorithmus nutzt das Prinzip der dynamischen Programmierung.

Diese Beschreibung folgt Hopcroft/Ullman (1996).

Als Eingabe erhält der Algorithmus eine kontextfreie Grammatik ${\displaystyle G=(N,T,P,S)}$ in Chomsky-Normalform und das zu prüfende Wort ${\displaystyle w=w_{1}w_{2}\ldots w_{n}\in T^{*}}$. Nun wird für jedes Teilwort ${\displaystyle w_{i,j}:=w_{i}\ldots w_{i+j-1}}$ (d. h.: ${\displaystyle w_{i,j}}$ fängt beim Index ${\displaystyle i}$ an und hat die Länge ${\displaystyle j}$) die Menge der Nichtterminale berechnet, die ${\displaystyle w_{i,j}}$ erzeugen, bezeichnet durch ${\displaystyle V_{i,j}}$.

Gemäß dem Prinzip der dynamischen Programmierung werden erst die ${\displaystyle V_{i,j}}$ für die kleinsten Teilwörter von ${\displaystyle w}$ berechnet, abgespeichert und dann zur somit effizienten Berechnung der nächstgrößeren Teilwörter weiterverwendet. Die kleinsten Teilwörter sind einzelne Buchstaben. Da die kontextfreie Grammatik in Chomsky-Normalform gegeben ist, kann jeder Buchstabe nur in genau einem Schritt von einem Nichtterminal abgeleitet werden.

Ein Nichtterminal einer Grammatik in Chomsky-Normalform kann in einem Schritt nicht auf mehrere Terminale abgeleitet werden. Daher kann ein Teilwort ${\displaystyle w_{i,j}}$, das mehr als nur ein Zeichen enthält, von ${\displaystyle A}$ nur über eine Regel ${\displaystyle (A\rightarrow BC)\in P}$ erzeugt werden. Da Nichtterminale nicht das leere Wort (ε) erzeugen können, muss ${\displaystyle B}$ den linken und ${\displaystyle C}$ den rechten Teil von ${\displaystyle w_{i,j}}$ erzeugen. Daraus folgt:

${\displaystyle A\in V_{i,j}\Leftrightarrow \exists k\in \mathbb {N} ,1\leq k\leq j-1:(A\rightarrow BC)\in P\land B\in V_{i,k}\land C\in V_{i+k,j-k}}$

Mit anderen Worten: ${\displaystyle A}$ kann ${\displaystyle w_{i,j}}$ erzeugen, wenn es gemäß der Produktionsregeln auf ${\displaystyle BC}$ abgeleitet werden kann und ${\displaystyle B}$ und ${\displaystyle C}$ wiederum auf ${\displaystyle w_{i,k}}$ und ${\displaystyle w_{i+k,j-k}}$ abgeleitet werden, also

${\displaystyle A\Rightarrow BC\Rightarrow ^{*}w_{i}\ldots w_{i+k-1}C\Rightarrow ^{*}w_{i}\ldots w_{i+k-1}w_{i+k}\ldots w_{i+j-1}=w_{i,j}}$.

Das Wortproblem kann nun einfach entschieden werden: ${\displaystyle w}$ kann genau dann von der Grammatik erzeugt werden, wenn ${\displaystyle S\in V_{1,n}}$ gilt. In ${\displaystyle V_{1,n}}$ liegen alle Variablen, die das Teilwort erzeugen können, das beim ersten Buchstaben anfängt und die Länge ${\displaystyle n}$ hat, also das ganze Wort.

Aus der Beschreibung ergibt sich folgender Algorithmus:

Für i = 1 ... n
  Für jede Produktion ${\displaystyle (l\rightarrow r)\in P}$
    Falls r = ${\displaystyle w_{i}}$
      Setze ${\displaystyle V_{i,1}:=V_{i,1}\cup \{l\}}$
Für j = 2 ... n
  Für i = 1 ... n - j + 1
    Für k = 1 ... j - 1
      Setze ${\displaystyle V_{i,j}:=V_{i,j}\cup \{l\in N\mid \exists Y,Z\in N:(l\rightarrow YZ)\in P\land Y\in V_{i,k}\land Z\in V_{i+k,j-k}\}}$
Falls ${\displaystyle S\in V_{1,n}}$, stoppe und gib "w wird von G erzeugt" aus
Stoppe und gib "w wird nicht von G erzeugt" aus

Die Fragestellung lautet, ob sich das Wort ${\displaystyle w=()[()]}$ durch die Grammatik ${\displaystyle G=(\{S,T,U,A,B,C,D\},\{(,),[,]\},P,S)}$ erzeugen lässt. Die Produktionsregeln ${\displaystyle P}$ der Grammatik seien:

${\displaystyle S\rightarrow AB\mid CD\mid AT\mid CU\mid SS}$

${\displaystyle T\rightarrow SB}$

${\displaystyle U\rightarrow SD}$

${\displaystyle A\rightarrow (}$

${\displaystyle B\rightarrow )}$

${\displaystyle C\rightarrow [}$

${\displaystyle D\rightarrow ]}$

Den Algorithmus kann man mittels einer Tabelle durchführen. Dabei ist in der ${\displaystyle i}$-ten Spalte und ${\displaystyle j}$-ten Zeile ${\displaystyle V_{i,j}}$ gespeichert, also die Menge der Nichtterminalsymbole, aus denen sich das Teilwort ableiten lässt, das beim Index ${\displaystyle i}$ anfängt und die Länge ${\displaystyle j}$ hat.

Es gilt ${\displaystyle w_{1}=(}$, ${\displaystyle w_{2}=)}$, ${\displaystyle w_{3}=[}$, ${\displaystyle w_{4}=(}$, ${\displaystyle w_{5}=)}$, ${\displaystyle w_{6}=]}$. Aus den Produktionsregeln ${\displaystyle A\rightarrow (}$, ${\displaystyle B\rightarrow )}$, ${\displaystyle C\rightarrow [}$, ${\displaystyle D\rightarrow ]}$ folgt ${\displaystyle V_{1,1}:=\{A\}}$, ${\displaystyle V_{2,1}:=\{B\}}$, ${\displaystyle V_{3,1}:=\{C\}}$, ${\displaystyle V_{4,1}:=\{A\}}$, ${\displaystyle V_{5,1}:=\{B\}}$, ${\displaystyle V_{6,1}:=\{D\}}$. Das ergibt die erste Zeile der Tabelle:

${\displaystyle V_{i,j}}$	1	2	3	4	5	6
1	{A}	{B}	{C}	{A}	{B}	{D}

Nun wird für jedes ${\displaystyle V_{i,j}}$ geprüft, ob es Produktionsregeln der Form ${\displaystyle l\rightarrow YZ}$ gibt, für die das Nichtterminalsymbol ${\displaystyle Y}$ in derselben Spalte der Tabelle oberhalb von ${\displaystyle V_{i,j}}$ liegt, das Nichtterminalsymbol ${\displaystyle Z}$ in derselben Diagonalen rechts oberhalb von ${\displaystyle V_{i,j}}$ liegt und außerdem ${\displaystyle Y\in V_{i,k}}$ und ${\displaystyle Z\in V_{i,k}}$ gilt. Aus der Produktionsregel ${\displaystyle S\rightarrow AB}$ und den Einträgen ${\displaystyle A\in V_{1,1}}$, ${\displaystyle B\in V_{2,1}}$, ${\displaystyle A\in V_{4,1}}$, ${\displaystyle B\in V_{5,1}}$ der ersten Zeile folgt ${\displaystyle V_{1,2}:=\{S\}}$, ${\displaystyle V_{1,4}:=\{S\}}$. Das ergibt die zweite Zeile der Tabelle:

${\displaystyle V_{i,j}}$	1	2	3	4	5	6
1	{A}	{B}	{C}	{A}	{B}	{D}
2	{S}	{}	{}	{S}	{}

Aus den Produktionsregeln ${\displaystyle U\rightarrow SD}$, ${\displaystyle S\rightarrow CU}$, ${\displaystyle S\rightarrow SS}$ und den schon jeweils oberhalb vorhandenen Nichtterminalsymbolen ergeben sich die weiteren Zeilen der Tabelle:

${\displaystyle V_{i,j}}$	1	2	3	4	5	6
1	{A}	{B}	{C}	{A}	{B}	{D}
2	{S}	{}	{}	{S}	{}
3	{}	{}	{}	{U}
4	{}	{}	{S}
5	{}	{}
6	{S}

Da ${\displaystyle S\in V_{1,6}}$, lässt sich das gegebene Wort ${\displaystyle w=()[()]}$ unter der Grammatik ${\displaystyle G}$ aus ${\displaystyle S}$ ableiten.

Eine Linksableitung des Wortes ${\displaystyle w}$ wäre demnach:

${\displaystyle S\Rightarrow SS\Rightarrow ABS\Rightarrow (BS\Rightarrow ()S\Rightarrow ()CU\Rightarrow ()[U\Rightarrow ()[SD\Rightarrow ()[ABD\Rightarrow ()[(BD\Rightarrow ()[()D\Rightarrow ()[()]=w}$

Also ist ${\displaystyle w}$ ein Wort der Sprache ${\displaystyle L(G)}$.

Der Cocke-Younger-Kasami-Algorithmus entscheidet in der Zeit ${\displaystyle {\mathcal {O}}\left(n^{3}\right)}$, ob ein Wort der Länge ${\displaystyle n}$ in der Sprache ${\displaystyle L(G)}$ liegt (vgl. Landau-Symbole zur Beschreibung der Notation). Dabei wird Speicherplatz in der Größenordnung ${\displaystyle {\mathcal {O}}\left(n^{2}\right)}$ benötigt, denn jeder Eintrag ${\displaystyle V_{i,j}}$ der Tabelle benötigt Speicherplatz der Größenordnung ${\displaystyle {\mathcal {O}}\left(1\right)}$. Die Effizienz hängt entscheidend vom Algorithmus für die Chomsky-Normalform ab, denn nur dann kann der CYK-Algorithmus verwendet werden.^[1][2]

Es gibt asymptotisch schnellere Algorithmen. Graham, Harrison und Ruzzo geben eine Variante des Earley-Algorithmus an. Er hat eine Laufzeit von ${\displaystyle {\mathcal {O}}\left(gn^{3}/\log(n)\right)}$. Rytter modifiziert diesen Algorithmus weiter und verbessert die Abhängigkeit von der Wortlänge auf ${\displaystyle {\mathcal {O}}\left(n^{3}/\log(n)\right)}$. Aber Valiants Parsing-Methode, die die Berechnungen des Cocke-Younger-Kasami-Algorithmus neu organisiert, ist die asymptotisch schnellste bekannte. Die Worst-Case-Laufzeit für eine kontextfreie Grammatik in Chomsky-Normalform ist proportional zur Laufzeit für die Multiplikation von zwei booleschen ${\displaystyle n\times n}$-Matrixen. Der schnellste derzeit bekannte Algorithmus für die Matrizenmultiplikation ist eine Variante des Coppersmith-Winograd-Algorithmus, der eine Laufzeit von etwa ${\displaystyle {\mathcal {O}}\left(n^{2{,}376}\right)}$ hat.^[3]

• Itiroo Sakai: Syntax in universal translation. In: 1961 International Conference on Machine Translation of Languages and Applied Language Analysis. Her Majesty’s Stationery Office, London 1962, S. 593–608 (mt-archive.info [PDF]). 
• Tadao Kasami: An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages. Air Force Cambridge Research Lab, Bedford 11. Juni 1965 (Scientific report AFCRL-65-758). 
• Daniel H. Younger: Recognition and parsing of context-free languages in time n³. In: Information and Control. Band 10, Nr. 2, 1967, S. 189–208. 
• John Cocke, Jacob T. Schwartz: Programming languages and their compilers. Preliminary notes. Courant Institute of Mathematical Sciences of New York University, New York 1970. 
• John E. Hopcroft, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 3. Auflage. Addison-Wesley, Bonn 1996, S. 148–149 (1. Nachdruck). 
• Dick Grune, Ceriel J. H. Jacobs: Parsing Techniques. A Practical Guide. 1. Auflage. Ellis Horwood, New York 1990, ISBN 0-13-651431-6, S. 81–104 ([1] [PDF; 1,9 MB]). 

• Interaktives Applet zur Demonstration des CYK-Algorithmus
• Freie Python-Implementierung des CYK-Algorithmus
• David Rodriguez-Velazquez, University of California: The CYK Algorithm
• educative.io: What is the CYK algorithm?

1. ↑ Laura Kallmeyer, Heinrich-Heine-Universität Düsseldorf: Cocke Younger Kasami (CYK)
2. ↑ Alexander Koller: The CKY Parser
3. ↑ Lillian Lee, Department of Computer Science, Cornell University: Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication