En informàtica, l'algorisme de Cocke-Younger-Kasami (també anomenat CYK o CKY) és un algorisme d'anàlisi sintàctica per a gramàtiques lliures de context publicat per Itiroo Sakai el 1961.Itiroo Sakai, "Syntax in universal translation". In Proceedings 1961 International Conference on Machine Translation of Languages and Applied Language Analysis, Her Majesty's Stationery Office, London, p. 593-608, 1962. L'algorisme rep el nom d'alguns dels seus redescobridors: John Cocke, Daniel Younger, Tadao Kasami i Jacob T. Schwartz. Empra l'anàlisi sintàctica ascendent i la programació dinàmica.
La versió estàndard de CYK només funciona amb gramàtiques lliures de context donades en forma normal de Chomsky (CNF). Tanmateix, qualsevol gramàtica independent de context es pot transformar algorítmicament en una gramàtica CNF que expressi el mateix llenguatge .
La importància de l'algorisme CYK prové de la seva alta eficiència en determinades situacions. Usant la notació O majúscula, el pitjor dels casos de temps d'execució de CYK és , on és la longitud de la cadena analitzada i és la mida de la gramàtica CNF . Això el converteix en un dels més eficients anàlisi d'algorismes en termes de complexitat asimptòtica en el pitjor dels casos, tot i que existeixen altres algorismes amb un millor temps d'execució mitjà en molts escenaris pràctics.
Formulari estàndard L'algorisme de programació dinàmica requereix que la gramàtica lliure de context es representi en forma normal de Chomsky (CNF), ja que comprova les possibilitats de dividir la seqüència actual en dues seqüències més petites. Qualsevol gramàtica lliure de context que no generi la cadena buida es pot representar en CNF utilitzant només regles de producció de les formes i ; per permetre la cadena buida, es pot permetre explícitament , on és el símbol d'inici.
Algorisme Com a pseudocodi Sigui l'entrada una cadena I que consti de n caràcters: a 1... una n.
Sigui que la gramàtica contingui r símbols no terminals R 1... R r, amb símbol d'inici R 1.
Sigui P [ n, n, r ] una matriu de booleans. Inicialitza tots els elements de P a fals.
Sigui back [ n, n, r ] una matriu de llistes de triplets que puntegen cap enrere. Inicialitza tots els elements de torna a la llista buida.
per a cada s = 1 a n
per a cada unitat de producció R v → a s establiu P [ 1, s, v ] = cert
per a cada l = 2 a n -- Longitud del tram
per a cada s = 1 a n - l +1 -- Inici de l'interval
per a cada p = 1 a l -1 -- Partició de l'expansió per a cada producció R a → R b R c si P [ p, s, b ] i P [ l - p, s + p, c ]
aleshores establiu P [ l, s, a ] = cert, afegeix <p,b,c> al darrere de [ l, s, a ]
si P [n, 1, 1 ] és certa,
aleshores Sóc membre de la llengua
tornar enrere -- tornant enrere pels passos fins a tornar enrere, es poden construir fàcilment tots els arbres d'anàlisi sintàctica possibles de la cadena.
altra cosa retorna "no és membre de l'idioma"
Com a prosa En termes informals, aquest algorisme considera totes les subcadenes possibles de la cadena d'entrada i estableix per ser cert si la subcadena de longitud començant des de es pot generar des del no terminal . Un cop ha considerat subcadenes de longitud 1, passa a subcadenes de longitud 2, i així successivament. Per a subcadenes de longitud 2 o superior, considera totes les particions possibles de la subcadena en dues parts i comprova si hi ha alguna producció. de tal manera que coincideix amb la primera part i coincideix amb la segona part. Si és així, registra com si coincidís amb tota la subcadena. Un cop finalitzat aquest procés, la gramàtica genera la cadena d'entrada si la subcadena que conté tota la cadena d'entrada coincideix amb el símbol d'inici.
Exemple miniatura|Anàlisi sintàctica de frases mitjançant l'algorisme CYK Aquest és un exemple de gramàtica:
Ara l'oració " ella menja un peix amb una forquilla" s'analitza mitjançant l'algorisme CYK. A la taula següent, en , és el número de la fila (començant a la part inferior amb 1) i és el número de la columna (començant a l'esquerra amb 1). SvicepresidentSvicepresidentPPSNPNPNPV, VPDet.NP.Det.Nellamenjaunpeixambunforquilla
Referències
Categoria:Algorismes Categoria:Informàtica