CYK algoritmus

Algoritmus CYK (Cocke-Younger-Kasami) je algoritmus, který určuje, zda slovo náleží do bezkontextového jazyka, a to v časové složitosti ${\displaystyle O(n^{3})}$ 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 ${\displaystyle T[i,j,x]}$, pro ${\displaystyle 1\leq i\leq j\leq n}$, kde ${\displaystyle 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 ${\displaystyle a}$ na pozici ${\displaystyle i}$, a pro každé ${\displaystyle X}$ takové, že v gramatice existuje pravidlo ${\displaystyle X\rightarrow a}$, nastavíme v poli ${\displaystyle T[i,1,X]:=1}$

Pro každou délku podslova ${\displaystyle i}$ od 2 do ${\displaystyle n}$:

Pro každý začátek podslova ${\displaystyle j}$ od 1 do ${\displaystyle n-i+1}$:

Pro každou délku první poloviny podslova ${\displaystyle k}$ od 1 do ${\displaystyle i-1}$:

Jestliže v poli mají jedničkovou hodnotu ${\displaystyle T[j,k,X]}$ i ${\displaystyle T[j+k,i-k,Y]}$, a v gramatice existuje pravidlo ${\displaystyle Z\rightarrow XY}$, nastavíme v poli ${\displaystyle T[j,i,Z]:=1}$

Slovo náleží do jazyka, jestliže ${\displaystyle T[1,n,S]=1}$, kde ${\displaystyle S}$ je vstupní neterminál gramatiky.

Jiné algoritmy jsou Earlyho parser a packrat parser.

• Dynamické programování

Zdroj