El análisis CKY (también llamado CYK, por Cocke-Younger-Kasami) es un algoritmo de análisis sintáctico para gramáticas libres de contexto que utiliza análisis ascendente y programación dinámica. Fue publicado por primera vez por Itiroo Sakai en 1961 y posteriormente redescubierto de forma independiente por John Cocke, Daniel Younger, Tadao Kasami y Jacob T. Schwartz, de quienes recibe su nombre. El algoritmo determina si una cadena dada puede ser generada por una gramática y, en caso afirmativo, puede construir todos los árboles de análisis posibles para esa cadena.
La versión estándar de CKY opera únicamente con gramáticas libres de contexto en forma normal de Chomsky (FNC), donde cada regla de producción es de la forma A → BC (dos no terminales) o A → a (un terminal). Cualquier gramática libre de contexto que no genere la cadena vacía puede transformarse algorítmicamente en una gramática FNC equivalente, por lo que esta restricción no limita la aplicabilidad del algoritmo en principio. Para gramáticas que generan la cadena vacía, se puede permitir explícitamente una regla S → ε, donde S es el símbolo inicial.
La importancia del análisis CKY radica en su complejidad temporal en el peor caso de O(n^3 · |G|), donde n es la longitud de la cadena de entrada y |G| es el tamaño de la gramática FNC. Esto lo convierte en uno de los algoritmos de análisis sintáctico más eficientes en términos de comportamiento asintótico en el peor caso, aunque otros algoritmos pueden tener mejores tiempos de ejecución promedio en escenarios prácticos.
Resumen del Algoritmo
El algoritmo funciona llenando una tabla tridimensional P[l, s, v], donde cada entrada es un valor booleano que indica si la subcadena de longitud l que comienza en la posición s puede ser generada desde el no terminal R_v. La tabla se llena en orden creciente de longitud de subcadena, comenzando con subcadenas de longitud 1.
Para cada símbolo terminal en la entrada, el algoritmo verifica todas las producciones unitarias de la forma R_v → a_s y marca las entradas correspondientes de la tabla como verdaderas. Para subcadenas más largas, considera cada partición posible de la subcadena en dos partes y verifica si existe una producción A → BC tal que B genera la primera parte y C genera la segunda parte. Si existe tal producción, la entrada para A se establece como verdadera.
Pseudocódigo
sea la entrada una cadena I que consiste en n caracteres: a1 ... an.
sea la gramática que contiene r símbolos no terminales R1 ... Rr, con símbolo inicial R1.
sea P[n,n,r] una matriz de booleanos. Inicializa todos los elementos de P a falso.
sea back[n,n,r] una matriz de listas de triples de apuntadores hacia atrás. Inicializa todos los elementos de back a la lista vacía.
para cada s = 1 a n
para cada producción unitaria Rv → as
establece P[1,s,v] = verdadero
para cada l = 2 a n -- Longitud del segmento
para cada s = 1 a n-l+1 -- Inicio del segmento
para cada p = 1 a l-1 -- Partición del segmento
para cada producción Ra → Rb Rc
si P[p,s,b] y P[l-p,s+p,c] entonces
establece P[l,s,a] = verdadero,
añade <p,b,c> a back[l,s,a]
si P[n,1,1] es verdadero entonces
I es miembro del lenguaje
devuelve back -- al rastrear los pasos a través de back, se pueden construir fácilmente todos los árboles de análisis posibles de la cadena.
si no
devuelve "no es miembro del lenguaje"
Ejemplo
Considere la siguiente gramática en FNC:
S → NP VP
VP → VP PP
VP → V NP
VP → eats
PP → P NP
NP → Det N
NP → she
V → eats
P → with
Det → the
N → fish
Para analizar la cadena "she eats the fish with the fish", el algoritmo primero marca todas las subcadenas de longitud 1. Por ejemplo, P[1,1,NP] se establece como verdadero porque NP → she, y P[1,2,VP] se establece como verdadero porque VP → eats. Luego procesa subcadenas de longitud 2, como "she eats", que se puede derivar como S → NP VP, por lo que P[2,1,S] se vuelve verdadero. El proceso continúa para subcadenas más largas, considerando todas las particiones. Al final, si P[n,1,S] es verdadero, la cadena se reconoce como parte del lenguaje, y los apuntadores hacia atrás permiten reconstruir el árbol de análisis.
Aplicaciones y Variantes
El análisis CKY se utiliza ampliamente en el procesamiento del lenguaje natural y la lingüística computacional, particularmente para el análisis con gramáticas libres de contexto probabilísticas. Se han desarrollado variantes del algoritmo para manejar gramáticas ponderadas y mejorar el rendimiento en el caso promedio. El enfoque de programación dinámica del algoritmo también lo conecta con otros métodos de análisis, como el analizador Earley, que maneja gramáticas libres de contexto arbitrarias sin conversión a FNC pero tiene una complejidad similar en el peor caso.
En los sistemas modernos de Artificial intelligence, el análisis CKY ha sido en gran medida superado por enfoques basados en Neural network, particularmente los modelos Transformer (architecture) utilizados en Large language models. Sin embargo, el algoritmo sigue siendo una técnica fundamental importante en la teoría de lenguajes formales y todavía se enseña en los planes de estudio de ciencias de la computación. Sus principios de programación dinámica y análisis ascendente también aparecen en otras áreas, como los modelos Sequence-to-Sequence (Seq2Seq) y la decodificación Beam Search.
La eficiencia y claridad del algoritmo lo han convertido en un ejemplo estándar en libros de texto sobre análisis sintáctico y Machine learning. Instituciones de investigación como MIT CSAIL y Stanford AI Lab han contribuido a su estudio y aplicación, y sigue siendo relevante en campos que requieren análisis exacto de datos estructurados, como la bioinformática y el diseño de compiladores.
Limitaciones
El análisis CKY requiere que la gramática esté en forma normal de Chomsky, lo que puede aumentar el número de reglas de producción y el tamaño de la gramática. La complejidad temporal en el peor caso de O(n^3) puede ser prohibitiva para cadenas de entrada muy largas, especialmente en aplicaciones en tiempo real. Además, la complejidad espacial del algoritmo es O(n^2 · r), que puede ser grande para gramáticas con muchos no terminales. A pesar de estas limitaciones, el análisis CKY sigue siendo un punto de referencia para algoritmos de análisis exactos y un concepto clave en el estudio de lenguajes libres de contexto.