Kuk-Janger-Kasami algoritam

Kuk-Janger-Kasami algoritam (Cocke-Younger-Kasami, CYK) je algoritam koji služi za određivanje pripadnosti neke reči w kontekstno slobodnom jeziku A (tip 2 u klasifikaciji Čomskog), tj:

$w\in A?$

Ovaj algoritam spada u metode sintaksičke analize koje omogućavaju analiziranje bilo koje kontekstno slobodne gramatike. U osnovi, ovom metodom se, početno od startnog simbola gramatike, analiziraju sva moguća izvođenja, dok se ne utvrdi da li reč pripada jeziku ili ne. Ukoliko se utvrdi da pripada jeziku, ovaj algoritam omogućava i uvid u način na koji je reč izvedena. Standardni algoritam analizira KS gramatike koje su date u normalnoj formi Čomskog. Ipak, kako se svaka kontekstno slobodna gramatika može prevesti u ovaj oblik, metoda je primenljiva na sve KSG. Postoje i proširenja algoritma kojima se mogu analizirati gramatike koje nisu u normalnoj formi Čomskog.

CYK algoritam spada u efikasnije algoritme sintaksičke analize koji imaju široku primenljivost. Složenost algoritma je polinomska i spada u klasu O(n³)(zbog tri ugnežđene petlje), gde je n dužina analizirane niske. Naravno, postoje i metode linearne složenosti, ali su one primenljive samo na neke potklase KSG. Algoritam pripada paradigmi dinamičkog programiranja.

Algoritam

Implementacija dinamičkim programiranjem:

Ulaz: karakteri a1.... an od kojih se sastoji zadata niska, simboli zadate
gramatike: r terminala i neterminali R1 ... Rr, gde je R1 početni simbol
Izlaz: odgovor da li niska pripada jeziku gramatike
{ lokalne varijable: 
         i, j, k (brojačke promenljive)
         matrica logičkih vrednosti P[n,n,r] (na početku svaki element matrice ima vrednost 0)
         (tokom rada algritma P[i,j,k] će postati 1 ako podniska ulazne niske od pozicije 
         i na dužini j može da se generiše iz Rr) 
  for(i = 1; i<= n; i++)  (uzećemo da je prvi element P[1,1,1], a ne  P[0,0,0]) 
     za svako pravilo gramatike Rj → ai postaviti P[i,1,j] = 1;
  for(i = 2; i<= n; i++)  (skenira se ulazna niska, a za svako a[i])      
    for(j = 1; j<= n-i+1; j++)  (pregleda se prefiks niske dužine ј) 
        for(k = 1; k<= i-1;k++) (izvođenje iz pravila gramatike)
            za svako pravilo RA -> RB RC 
               if  ((P[j,k,B]==1) && (P[j+k,i-k,C]==1))  P[j,i,A] = 1; 
                 (tj. ako je pravilo RA -> RB RC takvo da se iz RB može generisati 
                 podniska dužine k počev od pozicije ј, i iz RC se može generisati 
                 podniska dužine i-k počev od pozicije j+k, onda se iz RA može
                 generisati podniska dužine i počev od pozicije ј, tj. P[j,i,A] = 1)

 if  (P[1,n,1]==1) print 'niska je član jezika'
 else  print 'niska nije član jezika'
}

Modifikacije algoritma i primene

• Radi konstrukcije drveta izvođenja,CYK algoritam se može modifikovati tako da elementi matrice P ne budu logičke vrednosti nego čvorovi drveta izvođenja. Kako gramatika može biti višeznačna, neophodno je pamtiti u matrici zapravo listu čvorova, a rezultat će biti ne samo jedno drvo, već čitav niz mogućih stabala.

• Teoretski značaj CYK algoritma leži u mogućnosti da se koristi kao konstruktivan dokaz da je problem pripadnosti KSJ odlučiv.

• Radi sintaksičke analize stohastičkih KSG(SKSG), CYK algoritam se može modifikovati tako da elementi matrice P ne budu logičke vrednosti, već verovatnoće. SKSG su KSG u kojima se svaka primena pravila obavlja uz neku verovatnoću; tačnije, verovatnoća izvođenja je proizvod verovatnoća pravila koja se koriste u tim izvođenjima. SKSG se koriste u oblasti NLP (obrada prirodnih jezika) i proučavanja RNK molekula u bioinformatici.

Vidi još

• Erlijev algoritam

Literatura

• Skripta za predmet „Informatika 3“, UNI Karlsrue, Peter Sanders
• Vitas, Duško M. (2006). Prevodioci i interpretatori (Uvod u teoriju i metode kompilacije programskih jezika). Beograd: Matematički fakultet. 

Spoljašnje veze

• CYK algoritam, prostor Jelene Grmuše, MatF