En ciencias de la computación , el algoritmo Cocke-Younger-Kasami (alternativamente llamado CYK o CKY ) es un algoritmo de análisis de gramáticas libres de contexto publicado por Itiroo Sakai en 1961. [1] El algoritmo lleva el nombre de algunos de sus redescubridores: John Cocke , Daniel Younger, Tadao Kasami y Jacob T. Schwartz . Emplea análisis de abajo hacia arriba y programación dinámica .
La versión estándar de CYK opera solo en gramáticas libres de contexto dadas en la forma normal de Chomsky (CNF). Sin embargo, cualquier gramática libre de contexto puede transformarse (después de la convención) en una gramática CNF que exprese el mismo idioma ( Sipser 1997 ).
La importancia del algoritmo CYK radica en su alta eficiencia en determinadas situaciones. Usando la notación Big O , el peor tiempo de ejecución de CYK es, dónde es la longitud de la cadena analizada y es el tamaño de la gramática CNF ( Hopcroft y Ullman 1979 , pág. 140). Esto lo convierte en uno de los algoritmos de análisis sintáctico más eficientes en términos de complejidad asintótica en el peor de los casos , aunque existen otros algoritmos con un mejor tiempo de ejecución promedio en muchos escenarios prácticos.
Forma estándar
El algoritmo de programación dinámica requiere que la gramática libre de contexto se traduzca en la forma normal de Chomsky (CNF), porque prueba las posibilidades de dividir la secuencia actual en dos secuencias más pequeñas. Cualquier gramática libre de contexto que no genere la cadena vacía se puede representar en CNF utilizando solo las reglas de producción de las formas. y .
Algoritmo
Como pseudocódigo
El algoritmo en pseudocódigo es el siguiente:
deje que la entrada sea una cadena I que consta de n caracteres: a 1 ... a n .deje que la gramática contenga r símbolos no terminales R 1 ... R r , con el símbolo inicial R 1 .sea P [ n , n , r ] una matriz de valores booleanos. Inicialice todos los elementos de P a falso.para cada s = 1 an para cada unidad de producción R v → a s conjunto P [ 1 , s , v ] = verdaderopara cada l = 2 an - Longitud del tramo para cada s = 1 an - l +1 - Inicio del tramo para cada p = 1 a l -1 - Partición del tramo para cada producción R a → R b R c si P [ p , s , b ] y P [ l - p , s + p , c ] entonces establezca P [ l , s , a ] = verdaderosi P [n, 1 , 1 ] es verdadero, entonces yo soy miembro de la lengua, de lo contrario, no soy miembro de la lengua
CYK probabilístico (para encontrar el análisis más probable)
Permite recuperar el parse más probable dadas las probabilidades de todas las producciones.
deje que la entrada sea una cadena I que consta de n caracteres: a 1 ... a n .deje que la gramática contenga r símbolos no terminales R 1 ... R r , con el símbolo inicial R 1 .sea P [ n , n , r ] una matriz de números reales. Inicialice todos los elementos de P a cero.dejemos atrás [ n , n , r ] ser una matriz de triples de backpointing.para cada s = 1 an para cada unidad de producción R v → a s conjunto P [ 1 , s , v ] = Pr ( R v → a s ) para cada l = 2 an - Longitud del tramo para cada s = 1 an - l +1 - Inicio del tramo para cada p = 1 a l -1 - Partición del tramo para cada producción R a → R b R c prob_splitting = Pr ( R a → R b R c ) * P [ p , s , b ] * P [ l - p , s + p , c ] si P [ p , s , b ]> 0 y P [ l - p , s + p , c ]> 0 y P [ l , s , un ]entonces conjunto P [ l , s , un ] = prob_splitting conjunto de vuelta [ l , s , un ] = ,>
Como prosa
En términos informales, este algoritmo considera todas las posibles subcadenas de la cadena de entrada y establece para ser cierto si la subcadena de longitud empezando desde se puede generar desde el no terminal . Una vez que ha considerado las subcadenas de longitud 1, pasa a las subcadenas de longitud 2, y así sucesivamente. Para las subcadenas de longitud 2 y superiores, considera todas las posibles particiones de la subcadena en dos partes y comprueba si hay algo de producción. tal que coincide con la primera parte y coincide con la segunda parte. Si es así, registracomo coincidir con toda la subcadena. Una vez que se completa este proceso, la gramática genera la cadena de entrada si la subcadena que contiene toda la cadena de entrada coincide con el símbolo de inicio.
Ejemplo
Esta es una gramática de ejemplo:
Ahora se analiza la frase en la que se come un pescado con un tenedor utilizando el algoritmo CYK. En la siguiente tabla, en, i es el número de la fila (comenzando en la parte inferior en 1), y j es el número de la columna (comenzando en la izquierda en 1).
S | ||||||
Vicepresidente | ||||||
S | ||||||
Vicepresidente | PÁGINAS | |||||
S | notario público | notario público | ||||
notario público | V, VP | Det. | norte | PAG | Det | norte |
ella | come | a | pescado | con | a | tenedor |
Para facilitar la lectura, la tabla CYK para P se representa aquí como una matriz bidimensional M que contiene un conjunto de símbolos no terminales, de modo que R k está en si y solo si, . En el ejemplo anterior, dado que un símbolo de inicio S está en, la oración puede ser generada por la gramática.
Extensiones
Generando un árbol de análisis
El algoritmo anterior es un reconocedor que solo determinará si una oración está en el idioma. Es simple extenderlo a un analizador que también construye un árbol de análisis , almacenando los nodos del árbol de análisis como elementos de la matriz, en lugar del booleano 1. El nodo está vinculado a los elementos de la matriz que se usaron para producirlo, por lo que para construir la estructura del árbol. Solo se necesita un nodo de este tipo en cada elemento de la matriz si solo se va a producir un árbol de análisis. Sin embargo, si se van a mantener todos los árboles de análisis sintáctico de una oración ambigua, es necesario almacenar en el elemento de la matriz una lista de todas las formas en que se puede obtener el nodo correspondiente en el proceso de análisis sintáctico. Esto a veces se hace con una segunda tabla B [n, n, r] de los llamados backpointers . El resultado final es entonces un bosque compartido de posibles árboles de análisis sintáctico, donde las partes de árboles comunes se factorizan entre los distintos análisis sintácticos. Este bosque compartido se puede leer convenientemente como una gramática ambigua que genera solo la oración analizada, pero con la misma ambigüedad que la gramática original, y los mismos árboles de análisis hasta un cambio de nombre muy simple de no terminales, como lo muestra Lang (1994). .
Analizar gramáticas libres de contexto que no son CNF
Como señalan Lange & Leiß (2009) , el inconveniente de todas las transformaciones conocidas en la forma normal de Chomsky es que pueden conducir a una hinchazón no deseada en el tamaño de la gramática. El tamaño de una gramática es la suma de los tamaños de sus reglas de producción, donde el tamaño de una regla es uno más la longitud de su lado derecho. Utilizando para denotar el tamaño de la gramática original, el tamaño de la ampliación en el peor de los casos puede oscilar entre a , dependiendo del algoritmo de transformación utilizado. Para el uso en la enseñanza, Lange y Leiß proponen una ligera generalización del algoritmo CYK, "sin comprometer la eficiencia del algoritmo, la claridad de su presentación o la simplicidad de las pruebas" ( Lange & Leiß 2009 ).
Analizar gramáticas libres de contexto ponderadas
También es posible extender el algoritmo CYK para analizar cadenas usando gramáticas libres de contexto ponderadas y estocásticas . Los pesos (probabilidades) se almacenan en la tabla P en lugar de valores booleanos, por lo que P [i, j, A] contendrá el peso mínimo (probabilidad máxima) de que la subcadena de i a j pueda derivarse de A. Otras extensiones de la El algoritmo permite que todos los análisis de una cadena se enumeren de menor a mayor peso (mayor a menor probabilidad).
Algoritmo de Valiant
El peor tiempo de ejecución de CYK es, donde n es la longitud de la cadena analizada y | G | es el tamaño de la CNF gramática G . Esto lo convierte en uno de los algoritmos más eficientes para reconocer lenguajes generales libres de contexto en la práctica. Valiant (1975) dio una extensión del algoritmo CYK. Su algoritmo calcula la misma tabla de análisis que el algoritmo CYK; sin embargo, demostró que se pueden utilizar algoritmos para la multiplicación eficiente de matrices con entradas 0-1 para realizar este cálculo.
Usando el algoritmo Coppersmith-Winograd para multiplicar estas matrices, esto da un tiempo de ejecución asintótico en el peor de los casos de. Sin embargo, el término constante oculto por la notación Big O es tan grande que el algoritmo Coppersmith-Winograd solo es útil para matrices que son demasiado grandes para manejarlas en las computadoras actuales ( Knuth 1997 ), y este enfoque requiere una resta, por lo que solo es adecuado para el reconocimiento. La dependencia de la multiplicación de matrices eficiente no se puede evitar por completo: Lee (2002) ha demostrado que cualquier analizador de gramáticas libres de contexto que trabaje en el tiempo se puede convertir efectivamente en un algoritmo que calcula el producto de -matrices con 0-1-entradas en el tiempo .
Ver también
- Analizador GLR
- Analizador Earley
- Analizador de Packrat
Referencias
- ^ Grune, Dick (2008). Técnicas de análisis: una guía práctica (2ª ed.). Nueva York: Springer. pag. 579. ISBN 978-0-387-20248-8.
Fuentes
- Sakai, Itiroo (1962). Sintaxis en traducción universal . 1961 Conferencia internacional sobre traducción automática de idiomas y análisis de lenguajes aplicados, Teddington, Inglaterra. II . Londres: Oficina de papelería de Su Majestad. págs. 593–608.
- Cocke, John ; Schwartz, Jacob T. (abril de 1970). Lenguajes de programación y sus compiladores: Notas preliminares (PDF) (Informe técnico) (2ª edición revisada). CIMS , NYU .
- Hopcroft, John E .; Ullman, Jeffrey D. (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Lectura / MA: Addison-Wesley. ISBN 0-201-02988-X.
- Kasami, T. (1965). Un algoritmo eficiente de reconocimiento y análisis de sintaxis para lenguajes libres de contexto (Informe técnico). AFCRL . 65-758.
- Knuth, Donald E. (14 de noviembre de 1997). El arte de la programación informática Volumen 2: Algoritmos seminuméricos (3ª ed.). Addison-Wesley Professional. pag. 501. ISBN 0-201-89684-2.
- Lang, Bernard (1994). "El reconocimiento puede ser más difícil que analizar". Computación. Intell. 10 (4): 486–494. CiteSeerX 10.1.1.50.6982 . doi : 10.1111 / j.1467-8640.1994.tb00011.x .
- Lange, Martin; Leiß, Hans (2009). "¿A CNF o no a CNF? Una versión eficiente pero presentable del algoritmo CYK" . Informatica Didactica . 8 .
- Lee, Lillian (2002). "El análisis rápido de gramática libre de contexto requiere una rápida multiplicación de matrices booleanas". J. ACM . 49 (1): 1-15. arXiv : cs / 0112018 . doi : 10.1145 / 505241.505242 .
- Sipser, Michael (1997). Introducción a la Teoría de la Computación (1ª ed.). IPS. pag. 99 . ISBN 0-534-94728-X.
- Valiente, Leslie G. (1975). "Reconocimiento general sin contexto en menos de un tiempo cúbico". J. Comput. Syst. Sci. 10 (2): 308–314. doi : 10.1016 / s0022-0000 (75) 80046-8 .
- Younger, Daniel H. (febrero de 1967). "Reconocimiento y análisis de lenguajes libres de contexto en el tiempo n 3 " . Informar. Control . 10 (2): 189-208. doi : 10.1016 / s0019-9958 (67) 80007-x .
enlaces externos
- Demostración de análisis de CYK en JavaScript
- Exorciser es una aplicación Java para generar ejercicios en el algoritmo CYK, así como en máquinas de estado finito, algoritmos de Markov, etc.