El algoritmo de CYK (Cocke-Younger-Kasami) es un algoritmo que parsea una cadena a partir de una gramática libre de contexto en su forma normal de Chomsky.
Este algoritmo se basa en construir una tabla que, primero, asigna los símbolos no-terminales a las palabras y después determina los símbolos que corresponden a los nodos del árbol a partir de observar los símbolos que ha guardado. El resultado es una tabla que nos permitirá recuperar el árbol sintáctico de la oración.
import pandas as pd
def CYKParse(sentence, R):
"""
Algoritmo de CYK para parseo sintáctico.
Arguments
---------
sentence : list
Lista de tokens de la oración a parsear.
R : dict
Reglas de la gramática
Returns
-------
T : array
Tabla para recuperar el árbol sintáctico de la oración.
"""
#Longitud de la cadena
n = len(sentence)
#Generar tabla vacía
T = [[[] for j in range(n)] for i in range(n)]
#Recorre la cadena
for j in range(0, n):
#Revisa todas las reglas X \to r
for X, r in R.items():
#Revisa los elementos que puede generar la regla
for Y in r:
#Si es terminal
if len(Y) == 1 and Y[0] == sentence[j]:
#Agrega las X que generan w_j
T[j][j].append(X)
#Para i de j, j-1, j-2,...,0
for i in range(j, -1, -1):
#En cada i revisa los elementos que le siguen
#a la derecha hasta el final j+1
for k in range(i, j):
#Revisa las reglas
for X, r in R.items():
#Revisa lo que generan
for Y in r:
#Si no es terminal (Y=2)
#Si Y_0 en T[i.k] y Y_1 in T[k,j]
if len(Y) == 2 and Y[0] in T[i][k] and Y[1] in T[k+1][j]:
#print(pd.DataFrame(data=T, index=sentence, columns=sentence), '\n--------------')
T[i][j].append(X)
return T
La gramática debe constar de reglas en la forma normal de Chosmsky. En este caso, estructuramos la gramática como un diccionario donde las llaves son los símbolos no terminales y los valores son las reglas de reescritura posible a partir de esta gramática.
#Reglas de la gramática
CFG = {'O': [['FN', 'FV']],
'FN': [['DET', 'NC'], ['DET','FADJ']],
'FADJ': [['NC', 'ADJ']],
'FV': [['V', 'FN']],
'DET': [['la'],['el'],['un']],
'NC': [['libro'],['niño'],['niña']],
'ADJ': [['pesado'],['grande'],['pequeño'],['pequeña']],
'V': [['tiene'],['compró']]}
La gramática que hemos definido es de la forma:
\begin{align} O &\to FN \cdot FV \\ FN &\to DET \cdot NC | DET \cdot FADJ \\ FADJ &\to NC \cdot ADJ \\ FV &\to V \cdot FN \\ DET &\to la | el | un \\ NC &\to libro | niño | niña \\ ADJ &\to pesado | grande | pequeño | pequeña \\ V & \to tiene | compró \end{align}Podemos aplicarlo a una cadena específica y obtener la tabla. A partir de esta tabla podemos reconstruir el árbol que parsea la oración.
#Oración a probar
oracion = "la niña pequeña compró un libro grande".split()
#Árbol sintáctico
Tree = CYKParse(oracion, CFG)
print(pd.DataFrame(data=Tree, index=oracion, columns=oracion))
la niña pequeña compró un libro grande la [DET] [FN] [FN] [] [] [O] [O] niña [] [NC] [FADJ] [] [] [] [] pequeña [] [] [ADJ] [] [] [] [] compró [] [] [] [V] [] [FV] [FV] un [] [] [] [] [DET] [FN] [FN] libro [] [] [] [] [] [NC] [FADJ] grande [] [] [] [] [] [] [ADJ]