Algoritmus Cocke-Younger-Kasami

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Algoritmus CYK (Cocke-Younger-Kasami) je algoritmus, který určuje, zda slovo náleží do bezkontextového jazyka, a to v časové složitosti 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 , pro , kde jsou postupně všechny neterminály (nebo alternativně jejich čísla), a hodnoty všech jeho prvků nastavíme na 0
Pro každý znak na pozici , a pro každé takové, že v gramatice existuje pravidlo , nastavíme v poli
Pro každou délku podslova od 2 do :
Pro každý začátek podslova od 1 do :
Pro každou délku první poloviny podslova od 1 do :
Jestliže v poli mají jedničkovou hodnotu i , a v gramatice existuje pravidlo , nastavíme v poli
Slovo náleží do jazyka, jestliže , kde je vstupní neterminál gramatiky.

Jiné algoritmy jsou Earlyho parser a packrat parser.

Související články[editovat | editovat zdroj]