Algoritmo CYK

Algoritmo de análisis para gramáticas libres de contexto

En informática , el algoritmo Cocke–Younger–Kasami (también llamado CYK o CKY ) es un algoritmo de análisis sintáctico para gramáticas libres de contexto publicado por Itiroo Sakai en 1961. ^{[1] [2]} El algoritmo recibe su nombre de algunos de sus redescubridores: John Cocke , Daniel Younger, Tadao Kasami y Jacob T. Schwartz . Emplea análisis sintáctico ascendente y programación dinámica .

La versión estándar de CYK opera únicamente con gramáticas libres de contexto dadas en la forma normal de Chomsky (CNF). Sin embargo, cualquier gramática libre de contexto puede transformarse algorítmicamente en una gramática CNF que exprese el mismo lenguaje (Sipser 1997).

La importancia del algoritmo CYK se debe a su alta eficiencia en ciertas situaciones. Si se utiliza la notación O mayúscula , el tiempo de ejecución en el peor de los casos de CYK es , donde es la longitud de la cadena analizada y es el tamaño de la gramática CNF (Hopcroft y Ullman 1979, p. 140). Esto lo convierte en uno de los algoritmos de análisis sintáctico más eficientes ^{[ cita requerida ] 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. ${\displaystyle {\mathcal {O}}\left(n^{3}\cdot \left|G\right|\right)}$ ${\displaystyle n}$ ${\displaystyle \left|G\right|}$ ${\displaystyle G}$

Formulario estándar

El algoritmo de programación dinámica requiere que la gramática libre de contexto se exprese 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 reglas de producción de las formas y ; para permitir la cadena vacía, se puede permitir explícitamente , donde es el símbolo de inicio. ^[3] ${\displaystyle A\rightarrow \alpha }$ ${\displaystyle A\rightarrow BC}$ ${\displaystyle S\to \varepsilon }$ ${\displaystyle S}$

Algoritmo

Como pseudocódigo

El algoritmo en pseudocódigo es el siguiente:

sea ​​la entrada una cadena I que consta de n caracteres: a 1 ... a n . sea la gramática conteniendo r símbolos no terminales R 1 ... R r , con símbolo de inicio R 1 . sea  P [ n , n , r ] una matriz de booleanos. Inicialice todos los elementos de P a falso. sea  back [ n , n , r ] una matriz de listas de triples retroapuntadores. Inicialice todos los elementos de back a la lista vacía.para cada  s = 1 ton para  cada unidad de producción R v → a s  conjunto  P [ 1 , s , v ] = verdaderopara cada  l = 2 a n  -- Longitud del tramo  para cada  s = 1 a n - 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 ] = verdadero, añadir <p,b,c> al final [ l , s , a ]si  P [n, 1 , 1 ] es verdadero entonces  I es miembro del lenguaje volver  atrás - al volver sobre los pasos hasta atrás, uno puede construir fácilmente todos los árboles de análisis posibles de la cadena. de lo contrario,  devuelve "no es miembro del lenguaje"

CYK probabilístico (para encontrar el análisis más probable)

Permite recuperar el análisis más probable dadas las probabilidades de todas las producciones.

sea ​​la entrada una cadena I que consta de n caracteres: a 1 ... a n . sea la gramática r símbolos no terminales R 1 ... R r , con símbolo de inicio R 1 . sea  P [ n , n , r ] una matriz de números reales. Inicialice todos los elementos de P a cero. sea  back [ n , n , r ] una matriz de tripletas de punto inverso. para cada  s = 1 ton para  cada unidad de producción R v → a s  establecer  P [ 1 , s , v ] = Pr( R v → a s ) para cada  l = 2 ton --  Longitud del lapso  para cada  s = 1 to n - l +1 -- Inicio del lapso  para cada  p = 1 a l -1 -- Partición del lapso  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 prob_splitting > P [ l , s , a ] entonces establecer P [ l , s , a ] = prob_splitting restablecer [ l , s , a ] = <p,b,c>   si  P [n, 1 , 1 ] > 0 entonces encuentre el árbol de análisis retrocediendo hasta el árbol de análisis; de lo contrario,  devuelva "no es miembro del lenguaje"

Como prosa

En términos informales, este algoritmo considera cada subcadena posible de la cadena de entrada y establece que es verdadero si la subcadena de longitud que comienza desde se puede generar a partir del no terminal . Una vez que ha considerado subcadenas de longitud 1, continúa con subcadenas de longitud 2, y así sucesivamente. Para subcadenas de longitud 2 y mayores, considera cada partición posible de la subcadena en dos partes y verifica si hay alguna producción tal que coincida con la primera parte y coincida con la segunda parte. Si es así, registra como coincidente con toda la subcadena. Una vez que se completa este proceso, la gramática genera la cadena de entrada si la subcadena que contiene la cadena de entrada completa coincide con el símbolo de inicio. ${\displaystyle P[l,s,v]}$ ${\displaystyle l}$ ${\displaystyle s}$ ${\displaystyle R_{v}}$ ${\displaystyle A\to B\;C}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle A}$

Ejemplo

Análisis de oraciones utilizando el algoritmo CYK

Este es un ejemplo de gramática:

${\displaystyle {\begin{aligned}{\ce {S}}&\ {\ce {->NP\ VP}}\\{\ce {VP}}&\ {\ce {->VP\ PP}}\\{\ce {VP}}&\ {\ce {->V\ NP}}\\{\ce {VP}}&\ {\ce {->eats}}\\{\ce {PP}}&\ {\ce {->P\ NP}}\\{\ce {NP}}&\ {\ce {->Det\ N}}\\{\ce {NP}}&\ {\ce {->she}}\\{\ce {V}}&\ {\ce {->eats}}\\{\ce {P}}&\ {\ce {->with}}\\{\ce {N}}&\ {\ce {->fish}}\\{\ce {N}}&\ {\ce {->fork}}\\{\ce {Det}}&\ {\ce {->a}}\end{aligned}}}$

Ahora se analiza la oración " ella come un pescado con un tenedor" utilizando el algoritmo CYK. En la siguiente tabla, en , i es el número de la fila (comenzando desde abajo en 1), y j es el número de la columna (comenzando desde la izquierda en 1). ${\displaystyle P[i,j,k]}$

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 ⁠ ⁠ ${\displaystyle M[i,j]}$ si, y solo si, ⁠ ⁠ ${\displaystyle P[i,j,k]}$ . En el ejemplo anterior, dado que un símbolo de inicio S está en ⁠ ⁠ ${\displaystyle M[7,1]}$ , 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 lenguaje. Es simple extenderlo a un analizador que también construya 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, de modo de construir la estructura del árbol. Solo se necesita un nodo de este tipo en cada elemento de la matriz si solo se debe producir un árbol de análisis. Sin embargo, si se deben mantener todos los árboles de análisis 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. Esto a veces se hace con una segunda tabla B[n,n,r] de los llamados retropunteros . El resultado final es entonces un bosque compartido de posibles árboles de análisis, donde las partes comunes de los árboles se factorizan entre los diversos análisis. Este bosque compartido puede leerse convenientemente como una gramática ambigua que genera sólo 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 los no terminales, como lo muestra Lang (1994).

Análisis de gramáticas libres de contexto que no sean CNF

Como señalan Lange y Leiß (2009), el inconveniente de todas las transformaciones conocidas en la forma normal de Chomsky es que pueden dar lugar a un aumento indeseable del 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 aumento del tamaño en el peor de los casos puede variar entre y , dependiendo del algoritmo de transformación utilizado. Para su 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 y Leiß 2009). ${\displaystyle g}$ ${\displaystyle g^{2}}$ ${\displaystyle 2^{2g}}$

Análisis de gramáticas ponderadas e independientes del contexto

También es posible extender el algoritmo CYK para analizar cadenas utilizando gramáticas libres de contexto ponderadas y estocásticas . Los pesos (probabilidades) se almacenan entonces en la tabla P en lugar de los 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 del algoritmo permiten enumerar todos los análisis de una cadena desde el peso más bajo hasta el más alto (la probabilidad más alta a la más baja).

Estabilidad numérica

Cuando se aplica el algoritmo probabilístico CYK a una cadena larga, la probabilidad de división puede llegar a ser muy pequeña debido a la multiplicación de muchas probabilidades. Esto se puede solucionar sumando las probabilidades logarítmicas en lugar de multiplicarlas.

Algoritmo de Valiant

El tiempo de ejecución del peor caso de CYK es , donde n es la longitud de la cadena analizada y | G | es el tamaño de la gramática CNF 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) proporcionó 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. ${\displaystyle \Theta (n^{3}\cdot |G|)}$

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 vale la pena para matrices que son demasiado grandes para manejar en las computadoras actuales (Knuth 1997), y este enfoque requiere resta y, por lo tanto, solo es adecuado para el reconocimiento. La dependencia de la multiplicación eficiente de matrices no se puede evitar por completo: Lee (2002) ha demostrado que cualquier analizador sintáctico para gramáticas libres de contexto que funcionen en el tiempo se puede convertir efectivamente en un algoritmo que calcule el producto de -matrices con 0-1-entradas en el tiempo , y esto fue extendido por Abboud et al. ^[4] para aplicarlo a una gramática de tamaño constante. ${\displaystyle O(n^{2.38}\cdot |G|)}$ ${\displaystyle O(n^{3-\varepsilon }\cdot |G|)}$ ${\displaystyle (n\times n)}$ ${\displaystyle O(n^{3-\varepsilon /3})}$

Véase también

• Analizador GLR
• Analizador sintáctico Earley
• Analizador de Packrat
• Algoritmo de dentro a fuera

Referencias

1. Grune, Dick (2008). Técnicas de análisis sintáctico: una guía práctica (2.ª ed.). Nueva York: Springer. p. 579. ISBN 978-0-387-20248-8.
2. Itiroo Sakai, “Sintaxis en la traducción universal”. En Actas de la Conferencia internacional de 1961 sobre traducción automática de idiomas y análisis lingüístico aplicado, Her Majesty's Stationery Office, Londres, págs. 593-608, 1962.
3. Sipser, Michael (2006). Introducción a la teoría de la computación (2.ª ed.). Boston: Thomson Course Technology. Definición 2.8. ISBN 0-534-95097-3.OCLC 58544333  .
4. Abboud, Amir; Backurs, Arturs; Williams, Virginia Vassilevska (5 de noviembre de 2015). "Si los algoritmos actuales de Clique son óptimos, también lo es el analizador de Valiant". arXiv : 1504.01431 [cs.CC].

Fuentes

• Sakai, Itiroo (1962). Sintaxis en la traducción universal . Conferencia internacional de 1961 sobre traducción automática de idiomas y análisis aplicado del lenguaje, Teddington, Inglaterra. Vol. II. Londres: Her Majesty's Stationery Office. 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 de autómatas, lenguajes y computación. Lectura/MA: Addison-Wesley. ISBN 0-201-02988-X.
• Kasami, T. (1965). Un algoritmo eficiente de reconocimiento y análisis sintáctico 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. pág. 501. ISBN 0-201-89684-2.
• Lang, Bernard (1994). "El reconocimiento puede ser más difícil que el análisis". Comput. Intell. 10 (4): 486–494. CiteSeerX  10.1.1.50.6982 . doi :10.1111/j.1467-8640.1994.tb00011.x. S2CID  5873640.
• Lange, Martin; Leiß, Hans (2009). "¿CNF o no CNF? Una versión eficiente y presentable del algoritmo CYK". Informatica Didactica . 8 .
• Lee, Lillian (2002). "El análisis gramatical rápido e independiente del contexto requiere una multiplicación rápida de matrices booleanas". J. ACM . 49 (1): 1–15. arXiv : cs/0112018 . doi :10.1145/505241.505242. S2CID  1243491.
• Sipser, Michael (1997). Introducción a la teoría de la computación (1.ª ed.). IPS. pág. 99. ISBN 0-534-94728-X.
• Valiant, Leslie G. (1975). "Reconocimiento general sin contexto en un tiempo menor que el 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 independientes del contexto en tiempo n3". Inform. Control . 10 (2): 189–208. doi : 10.1016/s0019-9958(67)80007-x .

Enlaces externos

• Visualización interactiva del algoritmo CYK
• Demostración de análisis de CYK en JavaScript
• Exorciser es una aplicación Java para generar ejercicios en el algoritmo CYK así como Máquinas de Estados Finitos, algoritmos de Markov, etc.