El algoritmo Cocke-Younger-Kasami (CYK, o CKY) es un algoritmo de análisis sintáctico para gramáticas libres de contexto en ciencias de la computación. Fue publicado por primera vez por Itiroo Sakai en 1961 y posteriormente redescubierto por John Cocke, Daniel Younger, Tadao Kasami y Jacob T. Schwartz, de quienes recibe su nombre. El algoritmo emplea análisis ascendente y programación dinámica para determinar si una cadena dada puede ser generada por una gramática dada, y también puede construir árboles de análisis. Su tiempo de ejecución en el peor caso es O(n^3 · |G|), donde n es la longitud de la cadena de entrada y |G| es el tamaño de la gramática en forma normal de Chomsky, lo que lo convierte en uno de los algoritmos de análisis más eficientes en términos de complejidad asintótica en el peor caso, aunque otros algoritmos pueden tener un mejor rendimiento promedio en la práctica.
El algoritmo CYK se utiliza ampliamente en procesamiento del lenguaje natural y en el diseño de compiladores, donde el análisis sintáctico es un paso fundamental. Se valora especialmente por su simplicidad y su tiempo polinómico garantizado, incluso para gramáticas ambiguas. La dependencia del algoritmo en la programación dinámica le permite manejar todas las posibles interpretaciones de manera sistemática, lo que resulta útil en aplicaciones como el análisis sintáctico en lenguajes de programación y el análisis sintáctico en sistemas de inteligencia artificial.
Antecedentes históricos
El algoritmo fue descrito por primera vez por Itiroo Sakai en 1961, pero ganó prominencia a través de redescubrimientos independientes por John Cocke, Daniel Younger y Tadao Kasami a finales de la década de 1960. Jacob T. Schwartz también contribuyó a su desarrollo. El nombre del algoritmo refleja estos redescubrimientos, con el acrónimo CYK derivado de Cocke, Younger y Kasami. El algoritmo se convirtió en un tema estándar en la educación de ciencias de la computación, particularmente en cursos sobre lenguajes formales y teoría de autómatas. Su desarrollo precede a los enfoques modernos de aprendizaje automático y red neuronal para el análisis sintáctico, pero sigue siendo relevante como técnica fundamental.
Forma estándar: forma normal de Chomsky
La versión estándar del algoritmo CYK requiere que la gramática libre de contexto esté en forma normal de Chomsky (CNF). En CNF, todas las reglas de producción son de la forma A → BC (donde B y C son no terminales) o A → α (donde α es un símbolo terminal). Además, el símbolo inicial S puede tener una producción S → ε para permitir la cadena vacía. Cualquier gramática libre de contexto que no genere la cadena vacía puede transformarse en una gramática CNF equivalente, como lo demostró Sipser en 1997. Esta transformación es algorítmica y preserva el lenguaje generado por la gramática. El requisito de CNF simplifica el proceso de análisis porque limita las formas en que una subcadena puede dividirse en dos partes, lo que permite una programación dinámica eficiente.
Descripción del algoritmo
El algoritmo CYK opera llenando una tabla tridimensional P[l, s, v], donde l es la longitud de una subcadena, s es la posición inicial de esa subcadena y v es un no terminal. La entrada P[l, s, v] se establece como verdadera si la subcadena de longitud l que comienza en la posición s puede derivarse del no terminal R_v. El algoritmo procede en orden creciente de longitud de subcadena, comenzando con la longitud 1.
Para cada subcadena de longitud 1, el algoritmo verifica producciones unitarias de la forma R_v → a_s, donde a_s es el terminal en la posición s. Para subcadenas de longitud 2 o mayor, considera cada partición posible de la subcadena en dos partes, y para cada producción A → BC, verifica si la primera parte puede derivarse de B y la segunda parte de C. Si es así, marca la subcadena como derivable de A. El algoritmo también mantiene una tabla de punteros hacia atrás para permitir la reconstrucción de los árboles de análisis.
Al final, la cadena de entrada se reconoce como miembro del lenguaje si P[n, 1, 1] es verdadero, lo que significa que el símbolo inicial R_1 puede derivar toda la cadena. Los punteros hacia atrás pueden usarse entonces para construir todos los árboles de análisis posibles.
Ejemplo
Considere la siguiente gramática en CNF:
- S → NP VP
- VP → VP PP
- VP → V NP
- VP → eats
- PP → P NP
- NP → Det N
- NP → she
- V → eats
- P → with
- N → fish
- Det → the
Esta gramática puede analizar oraciones como "she eats the fish with the fork". El algoritmo CYK llenaría la tabla marcando primero las subcadenas de una sola palabra: "she" como NP, "eats" como VP o V, "the" como Det, "fish" como N, "with" como P y "fork" como N. Luego combina subcadenas: "the fish" como NP (Det N), "eats the fish" como VP (V NP), y así sucesivamente. Finalmente, determina que toda la oración puede derivarse de S, y los punteros hacia atrás revelan la estructura del árbol de análisis.
Aplicaciones e importancia
El algoritmo CYK es significativo en la teoría y práctica del análisis sintáctico. Se utiliza en procesamiento del lenguaje natural para el análisis sintáctico, en el diseño de compiladores para analizar lenguajes de programación y en bioinformática para la predicción de la estructura secundaria del ARN. Su complejidad temporal en el peor caso de O(n^3) es óptima para el análisis de gramáticas libres de contexto generales en el peor caso, aunque algoritmos especializados como el analizador Earley pueden ser más eficientes para ciertas gramáticas. El enfoque de programación dinámica del algoritmo también lo hace adecuado para gramáticas ambiguas, ya que puede enumerar todas las interpretaciones posibles. En la inteligencia artificial moderna, el algoritmo CYK se ha adaptado para su uso en gramáticas libres de contexto probabilísticas y análisis estadístico, donde calcula el árbol de análisis más probable dada una distribución de probabilidad sobre las producciones.
Limitaciones y extensiones
Una limitación del algoritmo CYK estándar es su requisito de CNF, que puede aumentar el tamaño de la gramática y afectar la eficiencia. Existen extensiones para gramáticas que no están en CNF, como el algoritmo Earley, que maneja gramáticas libres de contexto arbitrarias directamente. Además, el algoritmo CYK se ha extendido para manejar gramáticas ponderadas y probabilísticas, donde cada producción tiene un peso o probabilidad, y el objetivo es encontrar la interpretación con el peso o probabilidad máxima. Estas extensiones se utilizan en reconocimiento del habla y traducción automática. El algoritmo también forma la base para técnicas de análisis más avanzadas en modelos basados en aprendizaje profundo, aunque estos suelen utilizar enfoques de red neuronal en lugar de reglas gramaticales explícitas.