imported>StefanOllinger: Fixed Index

2025-06-20T16:21:39Z

Fixed Index

Neue Seite

Der '''Cocke-Younger-Kasami-Algorithmus''' ('''CYK-Algorithmus''') ist ein [[Algorithmus]] aus dem Gebiet der [[Theoretische Informatik|theoretischen Informatik]]. Mit ihm lässt sich feststellen, ob ein [[Wort (Theoretische Informatik)|Wort]] zu einer bestimmten [[Kontextfreie Sprache|kontextfreien Sprache]] gehört. In der Fachsprache bezeichnet man dies als Lösen des [[Wortproblem (Berechenbarkeitstheorie)|Wortproblems]] für kontextfreie Sprachen. Mit Hilfe von [[Backtracking]] kann der [[Syntaxbaum|Parse-Tree]] bzw. die Parse-Trees eines gegebenen Wortes der Sprache konstruiert werden. Um den Algorithmus anzuwenden, muss zu der vorgegebenen Sprache eine [[Formale Grammatik|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 [[Dynamische Programmierung|Prinzip der dynamischen Programmierung]].

== Beschreibung ==

Diese Beschreibung folgt Hopcroft/Ullman (1996).

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

Gemäß dem Prinzip der dynamischen Programmierung werden erst die <math>V_{i,j}</math> für die kleinsten Teilwörter von <math>w</math> 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 <math>w_{i,j}</math>, das mehr als nur ein Zeichen enthält, von <math>A</math> nur über eine Regel <math>(A \rightarrow BC) \in P</math> erzeugt werden. Da Nichtterminale nicht das [[Leeres Wort|leere Wort (ε)]] erzeugen können, muss <math>B</math> den linken und <math>C</math> den rechten Teil von <math>w_{i,j}</math> erzeugen. Daraus folgt:

:<math>A \in V_{i,j} \Leftrightarrow \exists k \in \N, 1 \le k \le j - 1: (A \rightarrow BC) \in P \land B \in V_{i,k} \land C \in V_{i + k, j - k}</math>

Mit anderen Worten: <math>A</math> kann <math>w_{i,j}</math> erzeugen, wenn es gemäß der Produktionsregeln auf <math>BC</math> abgeleitet werden kann und <math>B</math> und <math>C</math> wiederum auf <math>w_{i,k}</math> und <math>w_{i+k,j-k}</math> abgeleitet werden, also
:<math>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}</math>.

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

== Algorithmus ==

Aus der Beschreibung ergibt sich folgender Algorithmus:

'''Für''' i = 1 ... n
'''Für''' jede Produktion <math>(l \rightarrow r) \in P</math>
'''Falls''' r = <math>w_i</math>
Setze <math>V_{i,1}:=V_{i,1} \cup \{ l \}</math>
'''Für''' j = 2 ... n
'''Für''' i = 1 ... n - j + 1
'''Für''' k = 1 ... j - 1
Setze <math>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} \}</math>
'''Falls''' <math>S \in V_{1,n}</math>, stoppe und gib "w wird von G erzeugt" aus
Stoppe und gib "w wird nicht von G erzeugt" aus

== Beispiel ==

Die Fragestellung lautet, ob sich das [[Wort (theoretische Informatik)|Wort]] <math>w = ()[()]</math> durch die Grammatik <math>G = (\{ S, T, U, A, B, C, D \}, \{ (, ), [, ] \}, P, S)</math> erzeugen lässt. Die [[Produktionsregel]]n <math>P</math> der Grammatik seien:
:<math>S \rightarrow AB \mid CD \mid AT \mid CU \mid SS</math>
:<math>T \rightarrow SB</math>
:<math>U \rightarrow SD</math>
:<math>A \rightarrow (</math>
:<math>B \rightarrow )</math>
:<math>C \rightarrow [</math>
:<math>D \rightarrow ]</math>

Den Algorithmus kann man mittels einer Tabelle durchführen. Dabei ist in der <math>i</math>-ten Spalte und <math>j</math>-ten Zeile <math>V_{i,j}</math> gespeichert, also die Menge der [[Nichtterminalsymbol]]e, aus denen sich das Teilwort ableiten lässt, das beim Index <math>i</math> anfängt und die Länge <math>j</math> hat.

Es gilt <math>w_1 = ( </math>, <math>w_2 = ) </math>, <math>w_3 = [ </math>, <math>w_4 = ( </math>, <math>w_5 = ) </math>, <math>w_6 = ] </math>. Aus den [[Produktionsregel|Produktionsregeln]] <math>A \rightarrow (</math>, <math>B \rightarrow )</math>, <math>C \rightarrow [</math>, <math>D \rightarrow ]</math> folgt <math>V_{1,1} := \{A\}</math>, <math>V_{2,1} := \{B\}</math>, <math>V_{3,1} := \{C\}</math>, <math>V_{4,1} := \{A\}</math>, <math>V_{5,1} := \{B\}</math>, <math>V_{6,1} := \{D\}</math>. Das ergibt die erste Zeile der Tabelle:

{| class="wikitable"
! <math>V_{i,j}</math>
! 1
! 2
! 3
! 4
! 5
! 6
|-
! 1
| {A}
| {B}
| {C}
| {A}
| {B}
| {D}
|}
Nun wird für jedes <math>V_{i,j}</math> geprüft, ob es Produktionsregeln der Form <math>l \rightarrow YZ</math> gibt, für die das Nichtterminalsymbol <math>Y</math> in derselben Spalte der Tabelle oberhalb von <math>V_{i,j}</math> liegt, das Nichtterminalsymbol <math>Z</math> in derselben Diagonalen rechts oberhalb von <math>V_{i,j}</math> liegt und außerdem <math>Y \in V_{i,k}</math> und <math>Z \in V_{i,k}</math> gilt. Aus der Produktionsregel <math>S \rightarrow AB</math> und den Einträgen <math>A \in V_{1,1}</math>, <math>B \in V_{2,1}</math>, <math>A \in V_{4,1}</math>, <math>B \in V_{5,1}</math> der ersten Zeile folgt <math>V_{1,2} := \{S\}</math>, <math>V_{4,2} := \{S\}</math>. Das ergibt die zweite Zeile der Tabelle:
{| class="wikitable"
! <math>V_{i,j}</math>
! 1
! 2
! 3
! 4
! 5
! 6
|-
! 1
| {A}
| {B}
| {C}
| {A}
| {B}
| {D}
|-
! 2
| {S}
| {}
| {}
| {S}
| {}
|
|}
Aus den Produktionsregeln <math>U \rightarrow SD</math>, <math>S \rightarrow CU</math>, <math>S \rightarrow SS</math> und den schon jeweils oberhalb vorhandenen Nichtterminalsymbolen ergeben sich die weiteren Zeilen der Tabelle:
{| class="wikitable"
! <math>V_{i,j}</math>
! 1
! 2
! 3
! 4
! 5
! 6
|-
! 1
| {A}
| {B}
| {C}
| {A}
| {B}
| {D}
|-
! 2
| {S}
| {}
| {}
| {S}
| {}
|
|-
! 3
| {}
| {}
| {}
| {U}
|
|
|-
! 4
| {}
| {}
| {S}
|
|
|
|-
! 5
| {}
| {}
|
|
|
|
|-
! 6
| {S}
|
|
|
|
|
|}

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

Eine Linksableitung des Wortes <math>w</math> wäre demnach:
:<math> S \Rightarrow SS \Rightarrow ABS \Rightarrow (BS \Rightarrow ()S \Rightarrow ()CU \Rightarrow ()[U \Rightarrow ()[SD \Rightarrow ()[ABD \Rightarrow ()[(BD \Rightarrow ()[()D \Rightarrow ()[()] = w</math>

Also ist <math>w</math> ein Wort der Sprache <math>L(G)</math>.

== Komplexität ==

Der Cocke-Younger-Kasami-Algorithmus entscheidet in der Zeit <math>\mathcal{O}\left(n^3\right)</math>, ob ein Wort der Länge <math>n</math> in der Sprache <math>L(G)</math> liegt (vgl. [[Landau-Symbole]] zur Beschreibung der Notation). Dabei wird Speicherplatz in der Größenordnung <math>\mathcal{O}\left(n^2\right)</math> benötigt, denn jeder Eintrag <math>V_{i,j}</math> der Tabelle benötigt Speicherplatz der Größenordnung <math>\mathcal{O}\left(1\right)</math>. Die Effizienz hängt entscheidend vom [[Algorithmus]] für die [[Chomsky-Normalform]] ab, denn nur dann kann der CYK-Algorithmus verwendet werden.<ref>Laura Kallmeyer, Heinrich-Heine-Universität Düsseldorf: [https://user.phil-fak.uni-duesseldorf.de/~kallmeyer/Parsing/cyk.pdf Cocke Younger Kasami (CYK)]</ref><ref>Alexander Koller: [https://coli-saar.github.io/cl19/lectures/07-cky.pdf The CKY Parser]</ref>

Es gibt [[Asymptotische Laufzeit|asymptotisch]] schnellere Algorithmen. Graham, Harrison und Ruzzo geben eine Variante des [[Earley-Algorithmus]] an. Er hat eine [[Laufzeit (Informatik)|Laufzeit]] von <math>\mathcal{O}\left(gn^3 / \log(n)\right)</math>. Rytter modifiziert diesen Algorithmus weiter und verbessert die Abhängigkeit von der Wortlänge auf <math>\mathcal{O}\left(n^3 / \log(n)\right)</math>. 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 <math>n \times n</math>-Matrixen. Der schnellste derzeit bekannte Algorithmus für die [[Matrizenmultiplikation]] ist eine Variante des Coppersmith-Winograd-Algorithmus, der eine Laufzeit von etwa <math>\mathcal{O}\left(n^{2{,}376}\right)</math> hat.<ref>Lillian Lee, Department of Computer Science, Cornell University: [https://arxiv.org/pdf/cs/0112018.pdf Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication]</ref>

== Literatur ==
* {{Literatur
|Autor=Itiroo Sakai
|Titel=Syntax in universal translation
|Sammelwerk=1961 International Conference on Machine Translation of Languages and Applied Language Analysis
|Verlag=Her Majesty’s Stationery Office
|Ort=London
|Datum=1962
|Seiten=593–608
|Online=[http://www.mt-archive.info/NPL-1961-Sakai.pdf mt-archive.info]
|Format=PDF
|KBytes=}}
* {{Literatur
|Autor=Tadao Kasami
|Titel=An Efficient Recognition and Syntax-Analysis Algorithm for Context-Free Languages
|Verlag=Air Force Cambridge Research Lab
|Ort=Bedford
|Datum=1965-06-11
|Kommentar=''Scientific report AFCRL-65-758''}}
* {{Literatur
|Autor=Daniel H. Younger
|Titel=Recognition and parsing of context-free languages in time ''n³''
|Sammelwerk=Information and Control
|Band=10
|Nummer=2
|Datum=1967
|Seiten=189–208}}
* {{Literatur
|Autor=[[John Cocke]], [[Jacob T. Schwartz]]
|Titel=Programming languages and their compilers. Preliminary notes
|Verlag=Courant Institute of Mathematical Sciences of New York University
|Ort=New York
|Datum=1970}}
* {{Literatur
|Autor=[[John E. Hopcroft]], [[Jeffrey D. Ullman]]
|Titel=Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie
|Auflage=3.
|Verlag=Addison-Wesley
|Ort=Bonn
|Datum=1996
|Seiten=148–149
|Kommentar=1. Nachdruck}}
* {{Literatur
|Autor=Dick Grune, Ceriel J. H. Jacobs
|Titel=Parsing Techniques. A Practical Guide
|Auflage=1.
|Verlag=Ellis Horwood
|Ort=New York
|Datum=1990
|ISBN=0-13-651431-6
|Seiten=81–104
|Online=[ftp://ftp.cs.vu.nl/pub/dick/PTAPG_1st_Edition/BookBody.pdf]
|Format=PDF
|KBytes=1900}}

== Weblinks ==
* [https://raw.org/tool/cyk-algorithm/ Interaktives Applet zur Demonstration des CYK-Algorithmus]
* [https://github.com/RobMcH/CYK-Parser/ Freie Python-Implementierung des CYK-Algorithmus]
* David Rodriguez-Velazquez, University of California: [https://www.cs.ucdavis.edu/~rogaway/classes/120/winter12/CYK.pdf The CYK Algorithm]
* educative.io: [https://www.educative.io/answers/what-is-the-cyk-algorithm What is the CYK algorithm?]

== Einzelnachweise ==
<references />

[[Kategorie:Algorithmus]]
[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Dynamische Programmierung]]

Cocke-Younger-Kasami-Algorithmus - Versionsgeschichte

imported>StefanOllinger: Fixed Index