Algoritmo CYK - CYK algorithm

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. El algoritmo lleva el nombre de algunos de sus redescubridores: John Cocke , Daniel Younger , Tadao Kasami y Jacob T. Schwartz . Emplea análisis de abajo hacia arriba y programación dinámica .

La versión estándar de CYK opera solo en gramáticas libres de contexto dadas en la forma normal de Chomsky (CNF). Sin embargo, cualquier gramática libre de contexto puede transformarse (después de la convención) en una gramática CNF que exprese el mismo idioma ( Sipser 1997 ).

La importancia del algoritmo CYK radica en su alta eficiencia en determinadas situaciones. Usando la notación Big O , 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 & Ullman 1979 , p. 140). Esto lo convierte en uno de los algoritmos de análisis sintáctico 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 traduzca 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 las reglas de producción de las formas y . ${\ Displaystyle A \ rightarrow \ alpha}$${\ displaystyle A \ rightarrow BC}$

Algoritmo

Como pseudocódigo

El algoritmo en pseudocódigo es el siguiente:

let the input be a string I consisting of n characters: a1 ... an.
let the grammar contain r nonterminal symbols R1 ... Rr, with start symbol R1.
let P[n,n,r] be an array of booleans. Initialize all elements of P to false.

for each s = 1 to n
    for each unit production Rv → as
        set P[1,s,v] = true

for each l = 2 to n -- Length of span
    for each s = 1 to n-l+1 -- Start of span
        for each p = 1 to l-1 -- Partition of span
            for each production Ra    → Rb Rc
                if P[p,s,b] and P[l-p,s+p,c] then set P[l,s,a] = true

if P[n,1,1] is true then
    I is member of language
else
    I is not member of language

let the input be a string I consisting of n characters: a1 ... an.
let the grammar contain r nonterminal symbols R1 ... Rr, with start symbol R1.
let P[n,n,r] be an array of real numbers. Initialize all elements of P to zero.
let back[n,n,r] be an array of backpointing triples.
for each s = 1 to n
  for each unit production Rv →as
    set P[1,s,v] = Pr(Rv →as)
for each l = 2 to n -- Length of span
  for each s = 1 to n-l+1 -- Start of span
    for each p = 1 to l-1 -- Partition of span       
      for each production Ra → Rb Rc
        prob_splitting = Pr(Ra →Rb Rc) * P[p,s,b] * P[l-p,s+p,c]
        if P[p,s,b] > 0 and P[l-p,s+p,c] > 0 and P[l,s,a] <  prob_splitting then 
          set P[l,s,a] = prob_splitting
          set back[l,s,a] = <p,b,c>

Como prosa

En términos informales, este algoritmo considera que todas las posibles subcadenas de la cadena de entrada y los conjuntos son verdaderas si la subcadena de longitud a partir de se puede generar a partir del no terminal . Una vez que ha considerado las subcadenas de longitud 1, pasa a las subcadenas de longitud 2, y así sucesivamente. Para las subcadenas de longitud 2 y mayores, considera todas las posibles particiones de la subcadena en dos partes y comprueba si hay alguna producción que coincida con la primera parte y coincida 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 toda la cadena de entrada coincide con el símbolo de inicio. ${\ Displaystyle P [l, s, v]}$${\ Displaystyle l}$${\ Displaystyle s}$${\ Displaystyle R_ {v}}$${\ Displaystyle A \ a B \; C}$${\ Displaystyle B}$${\ Displaystyle C}$${\ Displaystyle A}$

Ejemplo

Análisis de oraciones usando el algoritmo CYK

Esta es una gramática de ejemplo:

${\ Displaystyle {\ begin {alineado} {\ ce {S}} & \ {\ ce {-> NP \ VP}} \\ {\ ce {VP}} & \ {\ ce {-> VP \ PP} } \\ {\ ce {VP}} & \ {\ ce {-> V \ NP}} \\ {\ ce {VP}} & \ {\ ce {-> come}} \\ {\ ce {PP }} & \ {\ ce {-> P \ NP}} \\ {\ ce {NP}} & \ {\ ce {-> Det \ N}} \\ {\ ce {NP}} & \ {\ ce {-> ella}} \\ {\ ce {V}} & \ {\ ce {-> come}} \\ {\ ce {P}} & \ {\ ce {-> con}} \\ { \ ce {N}} & \ {\ ce {-> pez}} \\ {\ ce {N}} & \ {\ ce {-> tenedor}} \\ {\ ce {Det}} & \ {\ ce {-> a}} \ end {alineado}}}$

Ahora se analiza la frase en la que se come un pescado con un tenedor 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, ya que un símbolo inicial S está en la sentencia puede ser generado por la gramática. ${\ 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 simple extenderlo a un analizador que también construye 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, por lo que para construir la estructura del árbol. Solo se necesita uno de estos nodos en cada elemento de la matriz si solo se va a producir un árbol de análisis. Sin embargo, si se van a mantener todos los árboles de análisis sintáctico 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 sintáctico. 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 sintáctico, donde las partes de árboles comunes se factorizan entre los diversos análisis sintácticos. Este bosque compartido se puede leer convenientemente como una gramática ambigua que genera solo 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 no terminales, como lo muestra Lang (1994). .

Analizar gramáticas libres de contexto que no son CNF

Como señalan Lange & Leiß (2009) , el inconveniente de todas las transformaciones conocidas en la forma normal de Chomsky es que pueden conducir a una hinchazón no deseada en el 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, la ampliación del tamaño en el peor de los casos puede variar de a , dependiendo del algoritmo de transformación utilizado. Para el 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 & Leiß 2009 ). ${\ Displaystyle g}$${\ Displaystyle g ^ {2}}$${\ Displaystyle 2 ^ {2g}}$

Analizar gramáticas libres de contexto ponderadas

También es posible extender el algoritmo CYK para analizar cadenas usando gramáticas libres de contexto ponderadas y estocásticas . 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. Otras extensiones de la El algoritmo permite que todos los análisis de una cadena se enumeren de menor a mayor peso (mayor a menor probabilidad).

Algoritmo de Valiant

El peor tiempo de ejecución de CYK es , donde n es la longitud de la cadena analizada y | G | es el tamaño de la CNF gramática 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 |)}$

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 es útil para matrices que son demasiado grandes para manejarlas en las computadoras actuales ( Knuth 1997 ), y este enfoque requiere una resta, por lo que solo es adecuado para el reconocimiento. La dependencia de la multiplicación de matrices eficiente no puede evitarse por completo: Lee (2002) ha demostrado que cualquier analizador sintáctico para gramáticas libres de contexto que trabajen en el tiempo puede convertirse efectivamente en un algoritmo que calcule el producto de matrices con 0-1 entradas en el tiempo . ${\ 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 de Packrat
• Algoritmo interior-exterior

Referencias

Fuentes

• Sakai, Itiroo (1962). Sintaxis en traducción universal . 1961 Conferencia internacional sobre traducción automática de idiomas y análisis de lenguajes aplicados, Teddington, Inglaterra. II . Londres: Oficina de papelería de Su Majestad. 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, los lenguajes y la computación de los autómatas . Lectura / MA: Addison-Wesley. ISBN 0-201-02988-X.
• Kasami, T. (1965). Un algoritmo eficiente de reconocimiento y análisis de sintaxis 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. pag. 501. ISBN 0-201-89684-2.
• Lang, Bernard (1994). "El reconocimiento puede ser más difícil que analizar". Computación. Intell. 10 (4): 486–494. CiteSeerX  10.1.1.50.6982 . doi : 10.1111 / j.1467-8640.1994.tb00011.x .
• Lange, Martin; Leiß, Hans (2009). "¿A CNF o no a CNF? Una versión eficiente pero presentable del algoritmo CYK" . Informatica Didactica . 8 .
• Lee, Lillian (2002). "El análisis rápido de gramática libre de contexto requiere una rápida multiplicación de matrices booleanas". J. ACM . 49 (1): 1-15. arXiv : cs / 0112018 . doi : 10.1145 / 505241.505242 .
• 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 sin contexto en menos de un tiempo 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 libres de contexto en el tiempo n ³ " . 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 en máquinas de estado finito, algoritmos de Markov, etc.