Algoritmo Cocke-Younger-Kasami (CYK)

La gramática denota las reglas sintácticas para la conversación en lenguaje natural. Pero en la teoría del lenguaje formal, la gramática se define como un conjunto de reglas que pueden generar strings. El conjunto de todas las strings que se pueden generar a partir de una gramática se denomina lenguaje de la gramática.

Gramática Libre de Contexto:
Nos dan una Gramática Libre de Contexto G = (V, X, R, S) y una string w, donde:

V es un conjunto finito de variables o símbolos no terminales,
X es un conjunto finito de símbolos terminales,
R es un conjunto finito de reglas,
S es el símbolo de inicio, un elemento distinto de V , y
Se supone que V y X son conjuntos disjuntos.

El problema de pertenencia se define como: la gramática G genera una lengua L(G). ¿Es la string dada un miembro de L(G)?

Forma normal de Chomsky:
una gramática libre de contexto G está en forma normal de Chomsky (CNF) si cada regla si cada regla de G tiene la forma:

A –> BC , [con como máximo dos símbolos no terminales en el RHS]
A –> a , o [un símbolo de terminal en el RHS]
S –> string nula , [string nula]

Algoritmo de Cocke-Younger-Kasami
Se utiliza para resolver el problema de membresía utilizando un enfoque de programación dinámica . El algoritmo se basa en el principio de que la solución al problema [i, j] puede construirse a partir de la solución del subproblema [i, k] y la solución del subproblema [ k, j]. El algoritmo requiere que la Gramática G esté en la Forma Normal de Chomsky (CNF). Tenga en cuenta que cualquier gramática libre de contexto se puede convertir sistemáticamente a CNF . Esta restricción se emplea para que cada problema solo se pueda dividir en dos subproblemas y no más, para limitar la complejidad del tiempo.

¿Cómo funciona el algoritmo CYK?

Para una string de longitud N , construya una tabla T de tamaño N x N. Cada celda de la tabla T[i, j] es el conjunto de todos los constituyentes que pueden producir la substring que se extiende desde la posición i a la j. El proceso implica llenar la tabla con las soluciones a los subproblemas encontrados en el proceso de análisis de abajo hacia arriba. Por lo tanto, las celdas se llenarán de izquierda a derecha y de abajo hacia arriba.

	1	2	3	4	5
1	[1, 1]	[1, 2]	[1, 3]	[1, 4]	[15]
2		[2, 2]	[2, 3]	[2, 4]	[2, 5]
3			[3, 3]	[3, 4]	[3, 5]
4				[4, 4]	[4, 5]
5					[5, 5]

En T[i, j], el número de fila i indica el índice inicial y el número de columna j indica el índice final.

$A \in T[i, j] \text{ if and only if } B \in T[i, k], C \in T[k, j] \text{ and } A \rightarrow BC \text{ is a rule of G}$

El algoritmo considera todas las subsecuencias posibles de letras y agrega K a T[i, j] si la secuencia de letras que comienza de i a j se puede generar a partir de la K no terminal . Para subsecuencias de longitud 2 y mayores, considera todas las posibles particiones de la subsecuencia en dos partes y comprueba si existe una regla de la forma A ? BC en la gramática donde B y C pueden generar las dos partes respectivamente, basándose en entradas ya existentes en T . La gramática puede producir la oración solo si la string completa coincide con el símbolo de inicio, es decir, si S es un miembro deT[1, n].

Considere una gramática de muestra en la forma normal de Chomsky:

NP   -->  Det | Nom
Nom  -->  AP | Nom
AP  -->  Adv | A
Det  -->  a | an
Adv  -->  very | extremely
AP   -->  heavy | orange | tall
A   -->  heavy | orange | tall | muscular
Nom -->  book | orange | man

Ahora considere la frase, » un libro naranja muy pesado «:

a(1) very(2) heavy (3) orange(4) book(5)

Comencemos llenando la tabla de izquierda a derecha y de abajo hacia arriba, de acuerdo con las reglas descritas anteriormente:

	1 un	2 muy	3 pesado	4 naranja	5 libro
1 un	det	–	–	notario público	notario público
2 muy		Avanzado	punto de acceso	nombre	nombre
3 pesado			A, PA	nombre	nombre
4 naranja				nominal, A, AP	nombre
5 libro					nombre

La tabla se llena de la siguiente manera:

T[1, 1] = {Det} as Det –> a es una de las reglas de la gramática.
T[2, 2] = {Adv} as Adv –> very es una de las reglas de la gramática.
T[1, 2] = {} ya que no se observa ninguna regla de coincidencia.
T[3, 3] = {A, AP} ya que A –> muy y AP –> muy son reglas de la gramática.
T[2, 3] = {AP} como AP –> Adv (T[2, 2]) A (T[3, 3]) es una regla de la gramática.
T[1, 3] = {} ya que no se observa ninguna regla de coincidencia.
T[4, 4] = {Nom, A, AP} como Nom –> naranja y A –> naranja y AP –> naranja son reglas de la gramática.
T[3, 4] = {Nom} as Nom –> AP (T[3, 3]) Nom (T[3, 4]) es una regla de la gramática.
T[2, 4] = {Nom} as Nom –> AP (T[2, 3]) Nom (T[4, 4]) es una regla de la gramática.
T[1, 4] = {NP} como NP –> Det (T[1, 1]) Nom (T[2, 4]) es una regla de la gramática.
T[5, 5] = {Nom} como Nom –> libro es una regla de la gramática.
T[4, 5] = {Nom} as Nom –> AP (T[4, 4]) Nom (T[5, 5]) es una regla de la gramática.
T[3, 5] = {Nom} as Nom –> AP (T[3, 3]) Nom (T[4, 5]) es una regla de la gramática.
T[2, 5] = {Nom} as Nom –> AP (T[2, 3]) Nom (T[4, 5]) es una regla de la gramática.
T[1, 5] = {NP} como NP –> Det (T[1, 1]) Nom (T[2, 5]) es una regla de la gramática.

Vemos que T[1][5] tiene NP , el símbolo de inicio, lo que significa que esta frase es miembro del lenguaje de la gramática G .

El árbol de análisis de esta frase se vería así:

Veamos otra frase de ejemplo, “ un hombre muy alto y extremadamente musculoso”:

a(1) very(2) tall(3) extremely(4) muscular(5) man(6)

Ahora usaremos el algoritmo CYK para encontrar si esta string es miembro de la gramática G:

	1 un	2 muy	3 de altura	4 extremadamente	5 musculosos	6 hombre
1 un	det	–	–	–	–	notario público
2 muy		Avanzado	punto de acceso	–	–	nombre
3 de altura			AP, A	–	–	nombre
4 extremadamente				Avanzado	punto de acceso	nombre
5 musculosos					A	–
6 hombre						nombre

Vemos que T[1][6] tiene NP , el símbolo de inicio, lo que significa que esta frase es miembro del lenguaje de la gramática G.

A continuación se muestra la implementación del algoritmo anterior:

C++

// C++ implementation for the
// CYK Algorithm
 
#include<bits/stdc++.h>
using namespace std;
 
// Non-terminals symbols
vector<string> terminals,non_terminals;
 
// Rules of the grammar
unordered_map<string,vector<vector<string>>> R;
 
// function to perform the CYK Algorithm
void cykParse(vector<string> w)
{
  int n = (int)w.size();
 
  // Initialize the table
  map<int,map<int,set<string>>> T;
   
  // Filling in the table
  for(int j=0;j<n;j++)
  {
 
    // Iterate over the rules
    for(auto x:R)
    {
      string lhs = x.first;
      vector<vector<string>> rule = x.second;
       
      for(auto rhs:rule)
      {
 
        // If a terminal is found
        if(rhs.size() == 1 && rhs[0] == w[j])
          T[j][j].insert(lhs);
      }
 
    }
    for(int i=j;i>=0;i--)
    {
 
      // Iterate over the range from i to j
      for(int k = i;k<=j;k++)
      {
 
        // Iterate over the rules
        for(auto x:R)
        {
          string lhs = x.first;
          vector<vector<string>> rule = x.second;
 
          for(auto rhs:rule)
          {
          // If a terminal is found
            if(rhs.size()==2 && T[i][k].find(rhs[0])!=T[i][k].end() && T[k+1][j].find(rhs[1])!=T[k+1][j].end())
              T[i][j].insert(lhs);
          }
 
        }
      }
    }
  }
 
  // If word can be formed by rules
  // of given grammar
  if(T[0][n-1].size()!=0)
    cout << "True\n";
  else
    cout << "False\n";
}
 
// Driver Code
int main()
{
  // terminal symbols
  terminals = {"book", "orange", "man",
             "tall", "heavy",
             "very", "muscular"};
   
  // non terminal symbols
  non_terminals = {"NP", "Nom", "Det", "AP",
                  "Adv", "A"};
   
  // Rules
  R["NP"]={{"Det", "Nom"}};
  R["Nom"]= {{"AP", "Nom"}, {"book"},
             {"orange"}, {"man"}};
  R["AP"] = {{"Adv", "A"}, {"heavy"},
            {"orange"}, {"tall"}};
  R["Det"] = {{"a"}};
  R["Adv"] = {{"very"}, {"extremely"}};
  R["A"] = {{"heavy"}, {"orange"}, {"tall"},
           {"muscular"}};
   
  // Given String
  vector<string> w = {"a", "very", "heavy", "orange", "book"};
 
  // Function Call
  cykParse(w);
 
  return 0;
}

Python3

# Python implementation for the
# CYK Algorithm
 
# Non-terminal symbols
non_terminals = ["NP", "Nom", "Det", "AP",
                  "Adv", "A"]
terminals = ["book", "orange", "man",
             "tall", "heavy",
             "very", "muscular"]
 
# Rules of the grammar
R = {
     "NP": [["Det", "Nom"]],
     "Nom": [["AP", "Nom"], ["book"],
             ["orange"], ["man"]],
     "AP": [["Adv", "A"], ["heavy"],
            ["orange"], ["tall"]],
     "Det": [["a"]],
     "Adv": [["very"], ["extremely"]],
     "A": [["heavy"], ["orange"], ["tall"],
           ["muscular"]]
    }
 
# Function to perform the CYK Algorithm
def cykParse(w):
    n = len(w)
     
    # Initialize the table
    T = [[set([]) for j in range(n)] for i in range(n)]
 
    # Filling in the table
    for j in range(0, n):
 
        # Iterate over the rules
        for lhs, rule in R.items():
            for rhs in rule:
                 
                # If a terminal is found
                if len(rhs) == 1 and \
                rhs[0] == w[j]:
                    T[j][j].add(lhs)
 
        for i in range(j, -1, -1):  
              
            # Iterate over the range i to j + 1  
            for k in range(i, j + 1):    
 
                # Iterate over the rules
                for lhs, rule in R.items():
                    for rhs in rule:
                         
                        # If a terminal is found
                        if len(rhs) == 2 and \
                        rhs[0] in T[i][k] and \
                        rhs[1] in T[k + 1][j]:
                            T[i][j].add(lhs)
 
    # If word can be formed by rules
    # of given grammar
    if len(T[0][n-1]) != 0:
        print("True")
    else:
        print("False")
     
# Driver Code
 
# Given string
w = "a very heavy orange book".split()
 
# Function Call
cykParse(w)

C#

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
    // terminal and Non-terminals symbols
    // static List<string> terminals = new List<string>();
    // static List<string> non_terminals = new List<string>();
 
    // Rules of the grammar
    static Dictionary<string,List<List<string>>> R = new Dictionary<string,List<List<string>>>();
 
    // function to perform the CYK Algorithm
    static void cykParse(List<string> w)
    {
        int n = w.Count;
 
        // Initialize the table
        SortedDictionary<int, SortedDictionary<int, SortedSet<string>>> T = new SortedDictionary<int, SortedDictionary<int, SortedSet<string>>>();
 
        // Filling in the table
        for (int j = 0 ; j < n ; j++)
        {
 
            // Iterate over the rules
            foreach (KeyValuePair<string,List<List<string>>> x in R)
            {
                string lhs = x.Key;
                List<List<string>> rule = x.Value;
                 
                foreach (List<string> rhs in rule)
                {
 
                    // If a terminal is found
                    if(rhs.Count == 1 && rhs[0] == w[j]){
                        if(!T.ContainsKey(j)){
                            T.Add(j, new SortedDictionary<int, SortedSet<string>>());
                        }
                        if(!T[j].ContainsKey(j)){
                            T[j].Add(j, new SortedSet<string>());
                        }
                        T[j][j].Add(lhs);
                    }
                }
 
            }
            for(int i = j ; i >= 0 ; i--)
            {
 
                // Iterate over the range from i to j
                for(int k = i ; k <= j ; k++)
                {
 
                    // Iterate over the rules
                    foreach (KeyValuePair<string,List<List<string>>> x in R)
                    {
                        string lhs = x.Key;
                        List<List<string>> rule = x.Value;
 
                        foreach (List<string> rhs in rule)
                        {
                        // If a terminal is found
                            if(rhs.Count == 2 &&
                                T.ContainsKey(i) &&
                                T[i].ContainsKey(k) &&
                                T[i][k].Contains(rhs[0]) &&
                                T.ContainsKey(k + 1) &&
                                T[k + 1].ContainsKey(j) &&
                                T[k + 1][j].Contains(rhs[1]))
                            {
                                if(!T.ContainsKey(i)){
                                    T.Add(i, new SortedDictionary<int, SortedSet<string>>());
                                }
                                if(!T[i].ContainsKey(j)){
                                    T[i].Add(j, new SortedSet<string>());
                                }
                                T[i][j].Add(lhs);
                            }
                        }
 
                    }
                }
            }
        }
 
        // If word can be formed by rules
        // of given grammar
        if(T.ContainsKey(0) && T[0].ContainsKey(n - 1) && T[0][n - 1].Count != 0){
            Console.Write("True\n");
        }else{
            Console.Write("False\n");
        }
    }
 
     
    // Driver code
    public static void Main(string[] args){
 
        // terminal symbols
        // terminals = new List<string>{
        //     "book",
        //     "orange", "man",
        //    "tall", "heavy",
        //    "very", "muscular"
        // };
 
        // non terminal symbols
        // non_terminals = new List<string>{
        //     "NP", "Nom", "Det",
        //     "AP", "Adv", "A"
        // };
 
        // Rules
        R.Add("NP", new List<List<string>>{
            new List<string>{"Det", "Nom"}
        });
 
        R["Nom"]= new List<List<string>>{
            new List<string>{"AP", "Nom"},
            new List<string>{"book"},
            new List<string>{"orange"},
            new List<string>{"man"}
        };
 
        R["AP"] = new List<List<string>>{
            new List<string>{"Adv", "A"},
            new List<string>{"heavy"},
            new List<string>{"orange"},
            new List<string>{"tall"}
        };
 
        R["Det"] = new List<List<string>>{
            new List<string>{"a"}
        };
 
        R["Adv"] = new List<List<string>>{
            new List<string>{"very"},
            new List<string>{"extremely"}
        };
 
        R["A"] = new List<List<string>>{
            new List<string>{"heavy"},
            new List<string>{"orange"},
            new List<string>{"tall"},
            new List<string>{"muscular"}
        };
 
        // Given String
        List<string> w = new List<string>{"a", "very", "heavy", "orange", "book"};
 
        // Function Call
        cykParse(w);
         
    }
}
 
// This code is contributed by subhamgoyal2014.

Producción:

True

Complejidad de Tiempo: O(N ³ )
Espacio Auxiliar: O(N ² )

Publicación traducida automáticamente

Artículo escrito por monisha_jegadeesan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

C++

Python3

C#

Deja una respuesta Cancelar la respuesta