Cocke -Younger- Kasami - algoritmen , CYK- eller CKY - algoritmen , er en algoritme , der giver dig mulighed for at bestemme, om det er muligt at vise en given streng i en given kontekstfri grammatik , og i givet fald give dens output. Med andre ord er det en strengparsingalgoritme . Algoritmen implementerer bottom-up-parsing og er baseret på den dynamiske programmeringsmetode . dets opdagere: John Cock, Daniel Younger, Tadao Kasami og Jacob T. Schwartz. De brugte bottom-up analyse og dynamisk programmering.
Standardversionen af CYK fungerer kun med kontekstfri grammatik givet i normal form (CNF). Enhver kontekstfri grammatik kan dog konverteres (efter konvertering) til en CNF-grammatik, der udtrykker det samme sprog ( Sipser 1997 ).
Det er en af de mest effektive parsing-algoritmer med hensyn til worst-case asymptotisk kompleksitet , selvom der er andre algoritmer med bedre gennemsnitlige udførelsestider i mange praktiske scenarier [1] .
Algoritmen fungerer som følger: ved første trin skrives et ord i den første linje, og hvert ikke-terminaltegn tilføjes til linjen, hvorunder terminaltegnene vises. Derefter er det for hver celle i gitteret nødvendigt at gå lodret fra top til bund til den markerede celle og den anden celle op diagonalt. For hvert sådant trin kombineres og kontrolleres cellerne for at finde kombinationen i grammatikken. Hvis den findes, føjes den venstre ikke-terminal til gittercellen. Hvis starttegnet efter alle trin er indeholdt i den sidste linje, kan ordet fås fra den givne grammatik [2] .
Den dynamiske programmeringsalgoritme kræver , at den kontekstfri grammatik konverteres til Chomsky Normal Form (CNF), fordi den kontrollerer, om den aktuelle sekvens kan opdeles i to mindre sekvenser. Enhver kontekstfri grammatik, der ikke producerer en tom streng, kan repræsenteres i CNF ved hjælp af produktionsregler [3] .
I pseudokode ser algoritmen sådan ud:
CYK-algoritme: givet en streng S på n tegn: a 1 ... a n . givet en grammatik indeholdende r ikke-terminale symboler R 1 ... R r . Indeholder et undersæt R s af begyndelsestegn. def array P [ n , n , r ] af booleske værdier initialiseret til False. for hver i = 1 : n for hver produktion R j -> a i tildele P [ 1 , i , j ] = Sand for hver i = 2 : n er intervallængden for hver j = 1 : n - i +1 - - begyndelsen af intervallet for hver k = 1 : i -1 er partitionen af intervallet for hver produktion RA -> R B R C hvis P [ k , j , B ] og P [ i - k , j + k , C ] så tildel P [ i , j , A ] = Sand , hvis for nogle x fra mængden s P [n, 1 , x ] = Sand, hvor s er alle indekser af R s , så returnerer S tilhører sproget ellers hører retur S ikke til sproget| Formelle sprog og formelle grammatikker | |
|---|---|
| Generelle begreber | |
| Type 0 | |
| Type 1 |
|
| Type 2 | |
| Type 3 |
|
| parsing | |