Algoritmus Cocke-Younger-Kasami
Z Wikipedie, otevřené encyklopedie
Algoritmus CYK (Cocke-Younger-Kasami) je algoritmus, který určuje, zda slovo náleží do bezkontextového jazyka, a to v časové složitosti O(n3) vzhledem k délce slova. Bezkontextový jazyk musí být zapsán gramatikou v Chomského normální formě.
Algoritmus vypadá takto:
- Vytvoříme pole T[i,j,x], pro
, kde x jsou postupně všechny neterminály (nebo alternativně jejich čísla), a hodnoty všech jeho prvků nastavíme na 0 - Pro každý znak a na pozici i, a pro každé X takové, že v gramatice existuje pravidlo
, nastavíme v poli T[i,1,X]: = 1 - Pro každou délku podslova i od 2 do n:
- Pro každý začátek podslova j od 1 do n − i + 1:
- Pro každou délku první poloviny podslova k od 1 do i − 1:
- Jestliže v poli mají jedničkovou hodnotu T[j,k,X] i T[j + k,i − k,Y], a v gramatice existuje pravidlo
, nastavíme v poli T[j,i,Z]: = 1
- Jestliže v poli mají jedničkovou hodnotu T[j,k,X] i T[j + k,i − k,Y], a v gramatice existuje pravidlo
- Pro každou délku první poloviny podslova k od 1 do i − 1:
- Pro každý začátek podslova j od 1 do n − i + 1:
- Slovo náleží do jazyka, jestliže T[1,n,S] = 1, kde S je vstupní neterminál gramatiky.
