algoritmo CYK

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

En informática , 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] [2]} El algoritmo lleva el nombre de algunos de sus redescubridores : John Cocke , Daniel Younger, Tadao Kasami y Jacob T. Schwartz . Emplea análisis ascendente y programación dinámica .

La versión estándar de CYK opera sólo 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 radica en su alta eficiencia en determinadas situaciones. Usando la notación O grande , el peor tiempo de ejecución 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 ^{[ cita necesaria ]} 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. ${\displaystyle {\mathcal {O}}\left(n^{3}\cdot \left|G\right|\right)}$ ${\displaystyle n}$ ${\displaystyle \left|G\right|}$ ${\displaystyle G}$

Forma estándar

El algoritmo de programación dinámica requiere que la gramática libre de contexto se represente 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 usando solo reglas de producción de las formas , y donde está 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 .Deje que la gramática contenga r símbolos no terminales R 1 ... R r , con símbolo inicial R 1 .sea  ​​P [ n , n , r ] una matriz de valores booleanos. Inicialice todos los elementos de P a falso.dejemos  que [ n , n , r ] sea una serie de listas de triples backpointing. Inicialice todos los elementos de regreso a la lista vacía.para cada  s = 1 an  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 fondo [ l , s , a ]si  P [n, 1 , 1 ] es verdadero, entonces I  es miembro del retorno del lenguaje ; al volver sobre los pasos hacia atrás, se pueden construir fácilmente todos los árboles de análisis posibles de la cadena. de lo contrario devolverá "no es miembro del idioma" 

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 .Deje que la gramática contenga r símbolos no terminales R 1 ... R r , con 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  que [ n , n , r ] sea una matriz de triples que apuntan hacia atrás.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 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 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  establezca  P [ l , s , a ] = prob_splitting retroceda [ l , s , a ] = <p,b,c>si  P [n, 1 , 1 ] > 0 entonces encuentre el árbol de análisis volviendo sobre atrás ,  devuelva el árbol de análisis; de lo contrario,  devuelva "no es miembro del lenguaje"

como prosa

En términos informales, este algoritmo considera todas las subcadenas posibles de la cadena de entrada y establece que es verdadero si la subcadena de longitud que comienza en puede generarse desde el no terminal . Una vez que ha considerado subcadenas de longitud 1, pasa a 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 que coincida con la primera parte y con la segunda parte. Si es así, registra que coincide 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 la frase ella se come un pescado con un tenedor se analiza 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). ${\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 si, y solo si ,. En el ejemplo anterior, dado que hay un símbolo inicial S , la gramática puede generar la oración. ${\displaystyle M[i,j]}$ ${\displaystyle P[i,j,k]}$ ${\displaystyle M[7,1]}$

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 sencillo 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 que para construir la estructura del árbol. Sólo se necesita uno de estos nodos en cada elemento de la matriz si sólo se va a producir un árbol de análisis. Sin embargo, si se van a conservar 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 backpointers . El resultado final es entonces un bosque compartido de posibles árboles de análisis, donde las partes de árboles comunes se factorizan entre los distintos 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 son CNF

Como señalaron Lange y Leiß (2009), el inconveniente de todas las transformaciones conocidas a la forma normal de Chomsky es que pueden provocar 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 tamaño ampliado en el peor de los casos puede variar de a , 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 libres de contexto

También es posible ampliar el algoritmo CYK para analizar cadenas utilizando gramáticas ponderadas y estocásticas libres de contexto . Luego, 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. Extensiones adicionales de la tabla P El algoritmo permite enumerar todos los análisis de una cadena de menor a mayor peso (de mayor a menor probabilidad).

Estabilidad numérica

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

algoritmo de valiente

El peor tiempo de ejecución de CYK es , donde n es la longitud de la cadena analizada y | GRAMO | 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) 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. ${\displaystyle \Theta (n^{3}\cdot |G|)}$

Al utilizar el algoritmo Coppersmith-Winograd para multiplicar estas matrices, se obtiene 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 O grande es tan grande que el algoritmo Coppersmith-Winograd sólo vale la pena para matrices que son demasiado grandes para manejarlas en las computadoras actuales (Knuth 1997), y este enfoque requiere resta y, por lo tanto, solo es adecuado para el reconocimiento. La dependencia de una 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 funcione en el tiempo puede convertirse efectivamente en un algoritmo que calcule el producto de matrices con 0-1 entradas en el tiempo . y esto fue ampliado por Abboud et al. ^[4] para aplicar 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})}$

Ver también

• analizador GLR
• Analizador Earley
• analizador packrat
• Algoritmo interior-exterior

Referencias

1. 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.
2. Itiroo Sakai, "Sintaxis en traducción universal". En Actas de la Conferencia Internacional de 1961 sobre Traducción Automática de Idiomas y Análisis Aplicado del Lenguaje, Her Majesty's Papelería Office, Londres, p. 593-608, 1962.
3. Sipser, Michael (2006). Introducción a la teoría de la computación (2ª ed.). Boston: Tecnología del curso Thomson. 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 de camarilla actuales son óptimos, también lo es el analizador de Valiant". arXiv : 1504.01431 [cs.CC].

Fuentes

• Sakai, Itiroo (1962). Sintaxis en traducción universal . 1961 Conferencia internacional sobre traducción automática de idiomas y análisis lingüístico aplicado, Teddington, Inglaterra. vol. II. Londres: Oficina de papelería de Su Majestad. págs. 593–608.
• Cocke, Juan ; Schwartz, Jacob T. (abril de 1970). Lenguajes de programación y sus compiladores: notas preliminares (PDF) (Informe técnico) (2ª edición revisada). CIMS , Universidad de Nueva York .
• Hopcroft, John E .; Ullman, Jeffrey D. (1979). Introducción a la teoría, los lenguajes y la computación de autómatas. Lectura/MA: Addison-Wesley. ISBN 0-201-02988-X.
• Kasami, T. (1965). Un algoritmo eficaz de reconocimiento y análisis de sintaxis para lenguajes libres de contexto (informe técnico). AFCR . 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.). Profesional de Addison-Wesley. pag. 501.ISBN _ 0-201-89684-2.
• Lang, Bernard (1994). "El reconocimiento puede ser más difícil que el análisis". Computadora. Intel. 10 (4): 486–494. CiteSeerX  10.1.1.50.6982 . doi :10.1111/j.1467-8640.1994.tb00011.x. S2CID  5873640.
• Lange, Martín; Leiß, Hans (2009). "¿A CNF o no a CNF? Una versión eficiente pero presentable del algoritmo CYK". Informática Didáctica . 8 .
• Lee, Lilian (2002). "El análisis gramatical rápido y libre de 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. pag. 99.ISBN _ 0-534-94728-X.
• Valiente, Leslie G. (1975). "Reconocimiento general libre de contexto en menos de tiempo cúbico". J. Computación. Sistema. Ciencia. 10 (2): 308–314. doi : 10.1016/s0022-0000(75)80046-8 .
• Más joven, Daniel H. (febrero de 1967). "Reconocimiento y análisis de lenguajes libres de contexto en el tiempo n3". 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 Máquinas de Estados Finitos, algoritmos de Markov, etc.