Algoritmo CYK

O algoritmo Cocke-Younger-Kasami (CYK) determina se uma cadeia de caracteres pode ser gerada por uma determinada gramática livre de contexto e, se ela puder, como ela pode ser gerada. Esse processo é conhecido como a análise sintática da cadeia, no caso, ascendente.

A versão padrão do algoritmo opera em gramáticas livres de contexto expressas através da Forma Normal de Chomsky (CNF). No pior caso, o algoritmo possui complexidade $\Theta (n^{3}\cdot |G|)$, em que $n$ é o comprimento da cadeia de caracteres e $|G|$ o tamanho da gramática CNF $G$. Isso o torna um dos algoritmos mais eficientes no reconhecimento geral de linguagens livres de contexto. Entretanto, algoritmos mais rápidos e especializados existem para certos subconjuntos de linguagens livres de contexto.

Algoritmo

Em pseudocódigo

Segue abaixo uma definição do algoritmo em pseudocódigo:

ROTINA CYK(
    $Texto:a[1\ldots n]$,     -- cadeia de caracteres a ser testada
    $Gramatica:R[1\ldots r]$, -- gramática contendo símbolos terminais e não-terminais
    $Vetor<Simbolo>:R_{s}$,      -- símbolos de início da gramática
    $Vetor<Booleano>:P[n,n,r]$—vetor de booleanos inicializado em $Falso$
    )
    PARA CADA i DE 1 A n FAÇA
        PARA CADA $Producao:R_{j}\to a_{i}$ FAÇA
            $P[i,1,j]\gets Verdadeiro$
    PARA CADA i DE 2 A n FAÇA
        PARA CADA j DE 1 A n-i+1 FAÇA
            PARA CADA k DE 1 A i-1 FAÇA
                PARA CADA Produção($R_{A}\to R_{B}R_{C}$) FAÇA
                    SE $P[j,k,B]\land P[j+k,i-k,C]$ ENTÃO
                        $P[j,i,A]\gets Verdadeiro$
    PARA CADA x EM $Indices:R_{s}$ FAÇA
        SE $P[1,n,x]=Verdadeiro$ ENTÃO
            RETORNE "membro da linguagem"
        SENÃO
            RETORNE "não-membro da linguagem"

Em prosa

Em termos informais, esse algoritmo considera cada possível subsequência da sequência de palavras e conjuntos $P[i,j,k]$ ser verdadeira se a subsequência de palavras de tamanho $i$ começando de $j$ poder ser gerada de $R_{k}$. Após avaliar as subsequências de tamanho 1, avalia as de tamanho 2, e assim sucessivamente. Para subsequências de tamanho 2 ou maior, considera cada possível partição da subsequência em duas partes e verifica se existe uma produção $P\to Q\;R$ tal que $Q$ coincide com a primeira parte e $R$ coincide com a segunda parte. Caso sim, ele grava $P$ como coincidindo com a subsequência inteira. Quando esse processo é terminado, a sentença é reconhecida pela gramática se a subsequência contendo a sentença inteira coincide a partir do símbolo inicial.

Exemplo

Esse é um exemplo de gramática:

${\begin{array}{lcl}{\mathit {S}}&\to &{\mathit {NP}}\;{\mathit {VP}}\\{\mathit {VP}}&\to &{\mathit {VP}}\;{\mathit {PP}}\\{\mathit {VP}}&\to &{\mathit {V}}\;{\mathit {NP}}\\{\mathit {VP}}&\to &{\textit {come}}\\{\mathit {PP}}&\to &{\mathit {P}}\;{\mathit {NP}}\\{\mathit {NP}}&\to &{\mathit {Det}}\;{\mathit {N}}\\{\mathit {NP}}&\to &{\textit {ela}}\\{\mathit {V}}&\to &{\textit {come}}\\{\mathit {P}}&\to &{\textit {com}}\\{\mathit {N}}&\to &{\textit {peixe}}\\{\mathit {N}}&\to &{\textit {garfo}}\\{\mathit {Det}}&\to &{\textit {um}}\end{array}}$

A sentença ela come um peixe com um garfo é analisada utilizando o algoritmo CYK. Na tabela a seguir, em $P[i,j,k]$, $i$ é o número da linha (começando inferiormente em 1) e $j$ é o número da coluna (começando pela esquerda em 1).

Tabela CYK

S
	VP
S
	VP			PP
S		NP			NP
NP	V, VP	Det.	N	P	Det	N
ela	come	um	peixe	com	um	garfo

A tabela CYK para P é representada aqui como uma matriz bidimensional M contendo um conjunto de símbolos não terminais, tais que R_k está em M[i,j] se e somente se P[i,j,k]. No exemplo acima, como o símbolo inicial S está em M[7,1], a sentença pode ser gerada pela gramática.

Extensões

Gerando uma árvore sintática

O algoritmo acima é somente um reconhecedor que somente determina se uma sentença está na linguagem. No entanto, é trivial estender o algoritmo para determinar não somente se uma sentença pertence a uma linguagem, mas também a árvore de análise sintática, armazenando-se os nós como elementos do vetor ao invés de somente valores booleanos. O nó é conectado aos elementos do vetor que foram usados para produzi-lo para assim produzir a estrutura de árvore. Apenas um nó em cada elemento do vetor é necessário se apenas uma árvore sintática será produzida. No entanto, se todas as árvores sintáticas de uma sentença ambígua precisarem ser mantidas, é necessário guardar no elemento do vetor uma lista de todos os caminhos que o nó correspondente pode ser obtido no processo de análise sintática. Isso é as vezes feito com uma segunda tabela B[n,n,r] de apontadores. O resultado final, então, é uma floresta de árvores possíveis, onde partes comuns de árvores são consideradas entre as várias análises. Essa floresta de árvores pode ser convenientemente lida como uma gramática ambígua gerando apenas a sentença analisada, mas com mesma ambiguidade que a gramática original, e as mesmas árvores sintáticas até um simples renomeamento de não terminais, como mostrado por Lang (1994).

Analisando gramáticas livre de contexto que não estão na CNF

Como mostrado por Lange & Leiß (2009), a desvantagem de todas as transformações conhecidas para a Forma Normal de Chomsky é que elas podem conduzir a um inchaço indesejado no tamanho da gramática. O tamanho da gramática é a soma dos tamanhos de suas regras de produção, onde o tamanho de uma regra é um mais o tamanho de seu lado direito. Usando $g$ para denotar o tamanho da gramática original, o aumento de tamanho no pior caso pode variar de $g^{2}$ até $g^{2g}$, dependendo do algoritmo de transformação utilizado. Para uso didático, Lange e Leiss trazem uma generalização leve do algoritmo CYK, sem comprometer a eficiência do algoritmo, claridade ou simplicidade de provas (Lange & Leiß 2009).

Analisando gramáticas livre de contexto com pesos

Também é possível estender o algoritmo CK para analisar cadeias de caracteres usando gramáticas livre de contexto estocásticas e com pesos. Os pesos (probabilidades) são armazenados na tabela P ao invés de booleanos, então P[i,j,A] conterá o peso mínimo (maior probabilidade) que a substring de i a j pode ser derivada de A. Extensões do algoritmo permitem análises de uma cadeia de caracteres ser enumerada do menor para o maior peso (da maior para a menor probabilidade).

Algoritmo de Valiant

O pior caso do CYK é de complexidade $\Theta (n^{3}\cdot |G|)$, onde n é o tamanho da cadeia analisada e |G| o tamanho da gramática CNF G. Isso significa que é um dos algoritmos mais eficientes para reconhecer gramáticas livres de contexto na prática. Valiant (1975) fez uma extensão ao algoritmo CYK. O algoritmo dele computa a mesma tabela que o algoritmo CYK, mas ele mostrou que algoritmos de multiplicação eficiente de matrizes com entradas 0-1 podem ser utilizados para realizar essa computação.

Utilizando o Algoritmo de Coppersmith-Winograd para multiplicar essas matrizes, isso dá uma complexidade no pior caso de $O(n^{2.38}\cdot |G|)$. No entanto, o termo constante escondido pela notação assintótica é tão grande que o Algoritmo Coppersmith-Winograd é apenas válido para matrizes que são grandes demais para manusear nos computadores dos dias atuais (Knuth 1997), e essa abordagem requer subtração e então é apenas válida para reconhecimento. A dependência de uma multiplicação de matrizes eficiente não pode ser evitada: Lee (2002) provou que qualquer analisador para gramáticas livre-de-contexto que executem em tempo $O(n^{3-\varepsilon }\cdot |G|)$ pode ser efetivamente convertido em um algoritmo computando o produto de matrizes $n\times n$ com entradas 0-1 em tempo $O(n^{3-\varepsilon /3})$.

Ver também

• John Cocke
• Analisador sintático GLR
• Algoritmo Earley
• Gramática de análise sintática de expressão

Referências

• Lange, Martin; Leiß, Hans (2009). «To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm». Informatica Didactica. 8. Consultado em 14 de dezembro de 2015. Arquivado do original em 29 de novembro de 2014 
• Lee, Lillian (2002). «Fast context-free grammar parsing requires fast Boolean matrix multiplication». J. ACM. 49 (1): 1–15. doi:10.1145/505241.505242 
• Sipser, Michael (1997). Introduction to the Theory of Computation 1st ed. [S.l.]: IPS. p. 99. ISBN 0-534-94728-X 
• Valiant, Leslie G. (1975). «General context-free recognition in less than cubic time». J. Comput. Syst. Sci. 10 (2): 308–314. doi:10.1016/s0022-0000(75)80046-8 
• Younger, Daniel H. (fevereiro de 1967). «Recognition and parsing of context-free languages in time n³». Inform. Control. 10 (2): 189–208. doi:10.1016/s0019-9958(67)80007-x 

Ligações externas

• Demonstração do CYK em JavaScript
• Applet interativo da Universidade de Leipzig que demonstra o algoritmo CYK (Site em alemão)
• Exorciser é uma aplicação Java para gerar exercícios no algoritmo CYK bem como Máquinas de Estados Finitos, algoritmos de Markov etc