Кук-Јангер-Касами алгоритам

Кук-Јангер-Касами алгоритам (Cocke-Younger-Kasami, CYK) је алгоритам који служи за одређивање припадности неке речи w контекстно слободном језику A (тип 2 у класификацији Чомског), тј:

w\in A?

Овај алгоритам спада у методе синтаксичке анализе које омогућавају анализирање било које контекстно слободне граматике. У основи, овом методом се, почетно од стартног симбола граматике, анализирају сва могућа извођења, док се не утврди да ли реч припада језику или не. Уколико се утврди да припада језику, овај алгоритам омогућава и увид у начин на који је реч изведена. Стандардни алгоритам анализира КС граматике које су дате у нормалној форми Чомског. Ипак, како се свака контекстно слободна граматика може превести у овај облик, метода је применљива на све КСГ. Постоје и проширења алгоритма којима се могу анализирати граматике које нису у нормалној форми Чомског.

CYK алгоритам спада у ефикасније алгоритме синтаксичке анализе који имају широку применљивост. Сложеност алгоритма је полиномска и спада у класу O(n³)(због три угнежђене петље), где је n дужина анализиране ниске. Наравно, постоје и методе линеарне сложености, али су оне применљиве само на неке поткласе КСГ. Алгоритам припада парадигми динамичког програмирања.

Алгоритам

Имплементација динамичким програмирањем:


Улаз: карактери а₁.... а_n од којих се састоји задата ниска, симболи задате
граматике: r терминала и нетерминали R₁ ... R_r, где је R₁ почетни симбол
Излаз: одговор да ли ниска припада језику граматике
{ локалне варијабле: 
         i, j, k (бројачке променљиве)
         матрица логичких вредности P[n,n,r] (на почетку сваки елемент матрице има вредност 0)
         (током рада алгритма P[i,j,k] ће постати 1 ако подниска улазне ниске од позиције 
         i на дужини j може да се генерише из R_r) 
  for(i = 1; i<= n; i++)  (узећемо да је први елемент P[1,1,1], а не  P[0,0,0]) 
     за свако правило граматике R_j → a_i поставити P[i,1,j] = 1;
  for(i = 2; i<= n; i++)  (скенира се улазна ниска, а за свако a[i])      
    for(j = 1; j<= n-i+1; j++)  (прегледа се префикс ниске дужине ј) 
        for(k = 1; k<= i-1;k++) (извођење из правила граматике)
            за свако правило RA -> RB RC 
               if  ((P[j,k,B]==1) && (P[j+k,i-k,C]==1))  P[j,i,A] = 1; 
                 (тј. ако је правило RA -> RB RC такво да се из RB може генерисати 
                 подниска дужине k почев од позиције ј, и из RC се може генерисати 
                 подниска дужине i-k почев од позиције j+k, онда се из RA може
                 генерисати подниска дужине i почев од позиције ј, тј. P[j,i,A] = 1)

 if  (P[1,n,1]==1) print 'ниска је члан језика'
 else  print 'ниска није члан језика'
}

Модификације алгоритма и примене

Ради конструкције дрвета извођења,CYK алгоритам се може модификовати тако да елементи матрице P не буду логичке вредности него чворови дрвета извођења. Како граматика може бити вишезначна, неопходно је памтити у матрици заправо листу чворова, а резултат ће бити не само једно дрво, већ читав низ могућих стабала.

Теоретски значај CYK алгоритма лежи у могућности да се користи као конструктиван доказ да је проблем припадности КСЈ одлучив.

Ради синтаксичке анализе стохастичких КСГ(СКСГ), CYK алгоритам се може модификовати тако да елементи матрице P не буду логичке вредности, већ вероватноће. СКСГ су КСГ у којима се свака примена правила обавља уз неку вероватноћу; тачније, вероватноћа извођења је производ вероватноћа правила која се користе у тим извођењима. СКСГ се користе у области NLP (обрада природних језика) и проучавања RNK молекула у биоинформатици.

Види још

Ерлијев алгоритам

Литература

Скрипта за предмет „Информатика 3“, УНИ Карлсруе, Петер Сандерс
Витас, Душко М. (2006). Преводиоци и интерпретатори (Увод у теорију и методе компилације програмских језика). Београд: Математички факултет.

Спољашње везе

CYK алгоритам, простор Јелене Грмуше, МатФ