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
[rediger | rediger kilde]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
[rediger | rediger kilde]- CYK-parsing-demo i JavaScript (en)
- Interaktivt program fra Universitetet i Leipzig som demonstrerer CYK-algoritmen (de)