CYK Algorithmus

In der Informatik ist der Cocke-Younger-Kasami (CYK) Algorithmus (hat wechselweise CKY genannt), ein Syntaxanalyse-Algorithmus für Grammatiken ohne Zusammenhänge. Es verwendet von unten nach oben Syntaxanalyse und dynamische Programmierung.

Die Standardversion von CYK funktioniert nur auf im Chomsky Normalen Form (CNF) gegebenen Grammatiken ohne Zusammenhänge. Jedoch kann jede Grammatik ohne Zusammenhänge in eine CNF Grammatik umgestaltet werden, die dieselbe Sprache ausdrückt.

Die Wichtigkeit vom CYK Algorithmus stammt von seiner hohen Leistungsfähigkeit in bestimmten Situationen. Mit Landauer-Symbolen ist die Grenzfall-Laufzeit von CYK, wo n die Länge der grammatisch analysierten Schnur ist und G die Größe der CNF Grammatik G ist. Das macht es einen der effizientesten Syntaxanalyse-Algorithmen in Bezug auf den Grenzfall asymptotische Kompliziertheit, obwohl andere Algorithmen mit der besseren durchschnittlichen Laufzeit in vielen praktischen Drehbüchern bestehen.

Standardform

Der Algorithmus verlangt, dass die Grammatik ohne Zusammenhänge in den Chomsky Normale Form (CNF) gemacht wird, weil es für Möglichkeiten prüft, die aktuelle Folge entzwei zu spalten. Jede Grammatik ohne Zusammenhänge, die die leere Schnur nicht erzeugt, kann in CNF das Verwenden nur von Regeln der Formen vertreten werden und.

Algorithmus

Als Pseudocode

Der Algorithmus im Pseudocode ist wie folgt:

lassen Sie den Eingang eine Schnur S sein, aus n Charakteren bestehend:a... a.

lassen Sie die Grammatik r Nichtendsymbole R. enthalten.. R.

Diese Grammatik enthält die Teilmenge R, der der Satz von Anfang-Symbolen ist.

lassen Sie P [n, n, r] eine Reihe von booleans sein. Initialisieren Sie alle Elemente von P zum falschen.

für jeden ich = 1 zu n

für jede Einzelfertigung R-> ein

Satz P [ich, 1, j] = wahrer

für jeden ich = 2 zu n - Länge der Spanne

für jeden j = 1 zu n-i+1 - Anfang der Spanne

für jeden k = 1 zu i-1 - Teilung der Spanne

für jede Produktion R-> R R

wenn P [j, k, B] und P [j+k, i-k, C] dann P [j, ich,] = wahrer setzen

wenn einige von P [1, n, x] wahr ist (x, wird über den Satz s wiederholt, wo s alle Indizes für R sind) dann

S ist Mitglied der Sprache

sonst

S ist nicht Mitglied der Sprache

Als Prosa

In informellen Begriffen denkt dieser Algorithmus jede mögliche Subfolge der Folge von Wörtern und geht unter, um wahr zu sein, wenn die Subfolge von Wörtern, die von der Länge anfangen, davon erzeugt werden kann. Sobald es Subfolgen der Länge 1 gedacht hat, geht es zu Subfolgen der Länge 2, und so weiter weiter. Für Subfolgen der Länge 2 und größer denkt es, dass jede mögliche Teilung der Subfolge in zwei Teile und Kontrollen sieht, ob es etwas solche Produktion gibt, der den ersten Teil vergleicht und den zweiten Teil vergleicht. Wenn so, es registriert als das Zusammenbringen der ganzen Subfolge. Sobald dieser Prozess vollendet wird, wird der Satz durch die Grammatik anerkannt, wenn die Subfolge, die den kompletten Satz enthält, durch das Anfang-Symbol verglichen wird.

Beispiel

Das ist eine Beispiel-Grammatik:

:

S &\\to& NP \; \; VP \\

VP &\\to& VP \; \; SEITEN \\

VP &\\to& V \; \; NP \\

VP &\\to& isst \\

SEITEN &\\to& P \; \; NP \\

NP &\\to& Det \; \; N \\

NP &\\to& sie \\

V&\\to& isst \\

P &\\to& mit \\

N &\\to& angeln \\

N &\\to& Gabel \\

Det &\\to& ein

\end {Reihe} </Mathematik>

Jetzt wird der Satz sie isst einen Fisch mit einer Gabel, mit dem CYK Algorithmus analysiert. Im folgenden Tisch, darin, ist die Zahl der Säule (am verlassenen an 1 anfangend), und ist die Zahl der Reihe (am Boden an 1 anfangend).

Seitdem ist wahr, der Beispiel-Satz kann durch die Grammatik erzeugt werden.

Erweiterungen

Das Erzeugen eines Syntaxanalyse-Baums

Es ist einfach sich auszustrecken der obengenannte Algorithmus dazu bestimmen nicht nur, ob ein Satz auf einer Sprache ist, aber auch einen Syntaxanalyse-Baum, durch die Speicherung von Syntaxanalyse-Baumknoten als Elemente der Reihe statt booleans zu bauen. Da die Grammatiken, die anerkennen werden, zweideutig sein können, ist es notwendig, eine Liste von Knoten zu versorgen (wenn man nur einen möglichen Syntaxanalyse-Baum nicht aufpicken möchte); das Endergebnis ist dann ein Wald von möglichen Syntaxanalyse-Bäumen.

Eine alternative Formulierung verwendet eine zweite Tabelle B [n, n, r] von so genanntem backpointers.

Die Syntaxanalyse non-CNF Grammatiken ohne Zusammenhänge

Wie hingewiesen, durch der Nachteil aller bekannten Transformationen in Chomsky ist normale Form, dass sie zu einem unerwünschten bloat in der Grammatik-Größe führen können. Die Größe einer Grammatik ist die Summe der Größen seiner Produktionsregeln, wo die Größe einer Regel ein plus die Länge seiner Rechte ist. Mit, um die Größe der ursprünglichen Grammatik anzuzeigen, kann sich die Größe-Explosion im Grenzfall von dazu erstrecken, je nachdem der Transformationsalgorithmus verwendet hat. Für den Gebrauch im Unterrichten schlagen Lange und Leiß eine geringe Generalisation des CYK Algorithmus, "vor, ohne Leistungsfähigkeit des Algorithmus, Klarheit seiner Präsentation oder Einfachheit von Beweisen in Verlegenheit zu bringen".

Die Syntaxanalyse hat Grammatiken ohne Zusammenhänge beschwert

Es ist auch möglich, den CYK Algorithmus zu erweitern, um Schnuren mit beschwerten und stochastischen Grammatiken ohne Zusammenhänge grammatisch zu analysieren. Gewichte (Wahrscheinlichkeiten) werden dann in der Tabelle P statt booleans versorgt, so P [werde ich, j,] das minimale Gewicht enthalten (maximale Wahrscheinlichkeit), dass die Teilkette von mir bis j aus A abgeleitet werden kann. Weitere Erweiterungen des Algorithmus erlauben allen Syntaxanalysen einer Schnur, vom niedrigsten bis höchstes Gewicht (im höchsten Maße zur niedrigsten Wahrscheinlichkeit) aufgezählt zu werden.

Der Algorithmus von Valiant

Die Grenzfall-Laufzeit von CYK ist, wo n die Länge der grammatisch analysierten Schnur ist und G die Größe der CNF Grammatik G ist. Das macht es einen der effizientesten Algorithmen, um allgemeine Sprachen ohne Zusammenhänge in der Praxis anzuerkennen. hat eine Erweiterung des CYK Algorithmus gegeben. Sein Algorithmus schätzt denselben Syntaxanalyse-Tisch

als der CYK Algorithmus; noch hat er gezeigt, dass Algorithmen für die effiziente Multiplikation von matrices mit 0 1 Einträge verwertet werden können, um diese Berechnung durchzuführen.

Mit dem Algorithmus des Kupferschmieds-Winograd, um diese matrices zu multiplizieren, gibt das eine asymptotische Grenzfall-Laufzeit dessen. Jedoch ist der unveränderliche durch die Große O Notation verborgene Begriff so groß, dass der Algorithmus des Kupferschmieds-Winograd nur für matrices lohnend ist, die zu groß sind, um auf heutigen Computern zu behandeln. Die Abhängigkeit von der effizienten Matrixmultiplikation kann zusammen nicht vermieden werden: Hat bewiesen, dass jeder parser für Grammatiken ohne Zusammenhänge, die rechtzeitig arbeiten, in einen Algorithmus effektiv umgewandelt werden kann, das Produkt von-matrices mit 0 1 Einträge rechtzeitig schätzend.

Siehe auch

  • GLR parser
  • Earley parser
  • Packrat parser
  • John Cocke und Jacob T. Schwartz (1970). Programmiersprachen und ihre Bearbeiter: Einleitende Zeichen. Technischer Bericht, Courant Institut für Mathematische Wissenschaften, New Yorker Universität.
  • T. Kasami (1965). Ein effizienter Algorithmus der Anerkennung und Syntax-Analyse für Sprachen ohne Zusammenhänge. Wissenschaftlicher Bericht AFCRL-65-758, Luftwaffe Forschungslaboratorium von Cambridge, Bedford, Massachusetts
  • Daniel H. Younger (1967). Anerkennung und Syntaxanalyse von Sprachen ohne Zusammenhänge rechtzeitig n. Information und Kontrolle 10 (2): 189-208.

Links


Greibach normale Form / Ulysses (Roman)
Impressum & Datenschutz