Cocke -Younger- Kasami -algoritmi , CYK- tai CKY - algoritmi , on algoritmi , jonka avulla voit määrittää, onko mahdollista näyttää tietty merkkijono tietyssä yhteydettömässä kielioppissa , ja jos on, antaa sen tulos. Toisin sanoen se on merkkijonon jäsennysalgoritmi . Algoritmi toteuttaa alhaalta ylös -jäsennyksen ja perustuu dynaamiseen ohjelmointimenetelmään . sen löytäjät: John Cock, Daniel Younger, Tadao Kasami ja Jacob T. Schwartz. He käyttivät alhaalta ylös -analyysiä ja dynaamista ohjelmointia.
CYK:n vakioversio toimii vain yhteydettömien kielioppien kanssa, jotka on annettu normaalimuodossa (CNF). Mikä tahansa yhteydetön kielioppi voidaan kuitenkin muuntaa (muuntamisen jälkeen) samaa kieltä ilmaisevaksi CNF-kieliopiksi ( Sipser 1997 ).
Se on yksi tehokkaimmista jäsennysalgoritmeista pahimman asymptoottisen monimutkaisuuden kannalta , vaikka monissa käytännön skenaarioissa on muitakin algoritmeja, joilla on parempi keskimääräinen suoritusaika [1] .
Algoritmi toimii seuraavasti: ensimmäisessä vaiheessa ensimmäiselle riville kirjoitetaan sana ja jokainen ei-päätemerkki lisätään riville, jonka alla päätemerkit näytetään. Sen jälkeen jokaiselle ruudukon solulle on siirryttävä pystysuoraan ylhäältä alas valittuun soluun ja toinen solu ylös vinosti. Jokaisessa tällaisessa vaiheessa solut yhdistetään ja tarkistetaan yhdistelmän löytämiseksi kielioppista. Jos se löytyy, vasen ei-pääte lisätään ruudukon soluun. Jos alkumerkki on kaikkien vaiheiden jälkeen viimeisellä rivillä, sana voidaan saada annetusta kielioppista [2] .
Dynaaminen ohjelmointialgoritmi vaatii yhteydettömän kieliopin muuntamisen Chomsky Normal Form (CNF) -muotoon, koska se tarkistaa, voidaanko nykyinen sekvenssi jakaa kahdeksi pienemmäksi sekvenssiksi. Mikä tahansa yhteydetön kielioppi, joka ei tuota tyhjää merkkijonoa, voidaan esittää CNF:ssä tuotantosääntöjen avulla [3] .
Pseudokoodissa algoritmi näyttää tältä :
CYK-algoritmi: annettu merkkijono S , jossa on n merkkiä: a 1 ... a n . annettu kielioppi, joka sisältää r ei-terminaalista symbolia R 1 ... R r .Sisältää alkumerkkien R -osajoukon . def array P [ n , n , r ] Boolen arvoista, jotka on alustettu arvoon False. kullekin i = 1 : n jokaiselle tuotannolle R j -> a i määrittää P [ 1 , i , j ] = Tosi jokaiselle i = 2 : n on kunkin j = 1 : n intervallin pituus : n - i +1 - - intervallin alku jokaiselle k = 1: lle: i -1 on intervallin osio kullekin tuotannolle R A -> R B R C , jos P [ k , j , B ] ja P [ i - k , j + k , C ] määritä sitten P [ i , j , A ] = Tosi , jos jollekin x :lle joukosta s P [n, 1 , x ] = Tosi, missä s ovat kaikki R :n indeksit , niin palautus S kuuluu kieleen muuten paluu S ei kuulu kieleen| Muodolliset kielet ja viralliset kieliopit | |
|---|---|
| Yleiset käsitteet | |
| Tyyppi 0 | |
| Tyyppi 1 |
|
| Tyyppi 2 | |
| Tyyppi 3 |
|
| jäsentäminen | |