Cocke-Younger-Kasami-Algorithmus

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 proporitional 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 ( [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