| Der letzte Beitrag |
| CookieMonsta |
CYK Algorithmus
Wer kennt sich mit dem CYK Algorithmus aus?
Der Algorithmus stellt für ein bestimmtes Wort und all die Enthaltenen Teilwörter mögliche Ableitungen aus einer Grammatik in Chomsky Normalform dar und damit, ob dieses Wort ableitbar ist von der Startvariable aus.
Die Grobe Erklärung findet man aber auch auf Wiki. Mein Problem ist jetzt, nachzuvollziehen, wie genau die Ableitungen (nicht zwingend vom Startsymbol) sich aus vorherigen berechnet.
Mein Ansatz:
In der Tabelle (siehe Wiki) findet man zunächst die Variablen linker Seite in der Grammatik, die einen einzelnen Buchstaben ableiten (immer möglich nach Chomsky Normalform) und trägt sie dort ein. Dann arbeitet man sich immer weiter, also anschliessend Teilwörter mit 2 Buchstaben.
Man geht dies wohl für alle !Teilstücke dieses !Teilwortes durch. D.h. man sucht ein k, das sich irgendwo in dem Teilwort befindet (bsp: aabaa ; k = 2 also aa und baa) und setzt die Variablen aus denen es abgeleitet ist, aus allen vorherigen Ableitungen der kürzeren Wörter zusammen.
Sprich:
Teilwort aab
Ableitungsmöglichkeiten gefunden durch eine gewisse Kombination aus a und ab sowie aa und b. (k = 1 und k = 2)
Jetzt kommt der Punkt den ich einfach nicht kapieren will. Wie genau werden die Regeln zusammengeschmissen?
also die aus aa mit b und diese mit a mit ab.
Da steig ich nicht ganz durch.
Meine Erklärung ist vielleicht etwas schlecht, liegt aber daran, dass ich es selbst noch nicht ganz verstanden hab. Wie ich schon sagte, der Wiki Eintrag unterstützt meine Erklärung vielleicht.
http://de.wikipedia.org/wiki/Cocke-Young...ami-Algorithmus
mfg |
|
|
