CYK-algoritmen

Fra Wikipedia, den frie encyklopedi
Gå til: navigasjon, søk

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 medlemsskapsproblemet 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 \Theta(n^3 \cdot |G|), 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 Rjai, 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 RARB RC
        Hvis P[j,k,B] og P[j+k,i-k,C]  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)
   er S medlem av språket
Ellers er S ikke medlem av språket

Eksterne lenker[rediger | rediger kilde]