Algoritmus Cocke -Younger- Kasami , CYK nebo CKY algoritmus , je algoritmus , který vám umožňuje určit, zda je možné zobrazit daný řetězec v dané bezkontextové gramatice , a pokud ano, poskytnout jeho výstup. Jinými slovy, je to algoritmus analýzy řetězce . Algoritmus implementuje analýzu zdola nahoru a je založen na metodě dynamického programování . její objevitelé: John Cock, Daniel Younger, Tadao Kasami a Jacob T. Schwartz. Používali analýzu zdola nahoru a dynamické programování.
Standardní verze CYK pracuje pouze s bezkontextovými gramatikami uvedenými v normální formě (CNF). Jakákoli bezkontextová gramatika však může být převedena (po konverzi) na gramatiku CNF vyjadřující stejný jazyk ( Sipser 1997 ).
Je to jeden z nejúčinnějších algoritmů analýzy z hlediska asymptotické složitosti nejhoršího případu , i když v mnoha praktických scénářích existují i jiné algoritmy s lepšími průměrnými dobami provádění [1] .
Algoritmus funguje následovně: v prvním kroku se na první řádek napíše slovo a každý nekoncový znak se přidá na řádek, pod kterým se zobrazí koncové znaky. Poté je nutné pro každou buňku v mřížce přejít svisle shora dolů ke zaškrtnuté buňce a druhou buňku diagonálně nahoru. Pro každý takový krok se buňky spojí a zkontrolují, aby se našla kombinace v gramatice. Pokud je nalezen, přidá se do buňky mřížky levý neterminál. Pokud je po všech krocích počáteční znak obsažen na posledním řádku, lze slovo získat z dané gramatiky [2] .
Algoritmus dynamického programování vyžaduje, aby byla bezkontextová gramatika převedena na Chomsky Normal Form (CNF), protože kontroluje, zda lze aktuální sekvenci rozdělit na dvě menší sekvence. Jakákoli bezkontextová gramatika, která nevytváří prázdný řetězec, může být reprezentována v CNF pomocí produkčních pravidel [3] .
V pseudokódu vypadá algoritmus takto:
Algoritmus CYK: je dán řetězec S o n znacích: a 1 ... a n . je dána gramatika obsahující r neterminálních symbolů R 1 ... R r . Obsahuje podmnožinu R počátečních znaků . def pole P [ n , n , r ] booleovských hodnot inicializované na False. pro každé i = 1 : n pro každou produkci R j -> a i přiřadit P [ 1 , i , j ] = Pravda pro každé i = 2 : n je délka intervalu pro každé j = 1 : n - i +1 - - začátek intervalu pro každé k = 1 : i -1 je rozdělení intervalu pro každou produkci R A -> R B R C pokud P [ k , j , B ] a P [ i - k , j + k , C ] pak přiřaďte P [ i , j , A ] = True pokud pro nějaké x z množiny s P [n, 1 , x ] = True, kde s jsou všechny indexy R s pak vraťte S patří do jazyka jinak return S do jazyka nepatří| Formální jazyky a formální gramatiky | |
|---|---|
| Obecné pojmy | |
| Typ 0 | |
| Typ 1 |
|
| Typ 2 | |
| Typ 3 | |
| rozebrat | |