CYK-algoritmen

Cocke-Younger-Kasami-algoritmen, vanligvis omtalt som CYK-algoritmen, er en algoritme som bestemmer hvorvidt en streng kan genereres av en gitt kontekstfri grammatikk og, i så fall, hvordan den kan genereres. Dette kalles å parse en streng. Algoritmen tar i bruk bottom–up-parsing og dynamisk programmering.

Standardversjonen av CYK-algoritmen opererer på kontekstfrie grammatikker gitt på Chomsky normalform (CNF), som en hvilken som helst konteksfri grammatikk kan omgjøres til.

CYK-algoritmen er viktig fordi den beviser at medlemskapsproblemet for kontekstfrie grammatikker er løsbart, og fordi den gjør det på en så effektiv måte. Uttrykt med stor O-notasjon er den lengste mulige kjøretida for CYK-algoritmen , hvor n er lengden av den parsa strengen og |G| størrelsen på CNF-grammatikken G.

Algoritmen ble oppdaga av de tre som den har fått navnet sitt etter, uavhengig av hverandre: Cocke og Schwartz i 1970, Younger i 1967 og Kasami i 1965.

Beskrivelse
Den opprinnelige CYK-algoritmen kan beskrives med følgende pseudokode:

 La innputt være en streng S bestående av n tegn: a1 ... an.
 La grammatikken inneholde r ikke-terminalsymboler R1 ... Rr.
 Denne grammatikken inneholder delmengden Rs, som er mengden startsymboler.
 La P[n,n,r] være en array av booleanske verdier. Sett alle elementenes P-verdi til false.
 For hver i = 1 til n
   For hver enhetsproduksjon Rj → ai, sett P[i,1,j] = true.
 For hver i = 2 til n -- Spanlengden
   For hver j = 1 til n-i+1 -- Spanstart
     For hver k = 1 til i-1 -- Spanoppdeling
       For hver produksjon RA → RB RC
         Hvis P[j,k,B] og P[j+k,i-k,C] så sett P[j,i,A] = true
 Hvis minst én av P[1,n,x] er true (x itereres over settet s, hvor s er alle indeksene for Rs)
   Så er S medlem av språket
 Ellers er S ikke medlem av språket

Eksterne lenker
 CYK-parsing-demo i JavaScript 
 Interaktivt program fra Universitetet i Leipzig som demonstrerer CYK-algoritmen 

Kategori:Algoritmer