Mostrar código-fonte de 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 (computação)|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 computacional|complexidade]] <math>\Theta(n^3 \cdot |G|)</math>, em que <math>n</math> é o comprimento da cadeia de caracteres e <math>|G|</math> o tamanho da gramática CNF <math>G</math>. Isso o torna um dos algoritmos mais eficientes no reconhecimento geral de [[Linguagem livre de contexto|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(
     <math>Texto:a[1 \ldots n]</math>,     -- cadeia de caracteres a ser testada
     <math>Gramatica:R[1 \ldots r]</math>, -- gramática contendo símbolos terminais e não-terminais
     <math>Vetor<Simbolo>:R_s</math>,      -- símbolos de início da gramática
     <math>Vetor<Booleano>:P[n,n,r]</math>—vetor de booleanos inicializado em <math>Falso</math>
     )
     PARA CADA i DE 1 A n FAÇA
         PARA CADA <math>Producao:R_j \to a_i</math> FAÇA
             <math>P[i,1,j] \gets Verdadeiro</math>
     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(<math>R_A \to R_B R_C</math>) FAÇA
                     SE <math>P[j,k,B] \land P[j+k,i-k,C]</math> ENTÃO
                         <math>P[j,i,A] \gets Verdadeiro</math>
     PARA CADA x EM <math>Indices:R_s</math> FAÇA
         SE <math>P[1,n,x] = Verdadeiro</math> 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 <math>P[i,j,k]</math> ser verdadeira se a subsequência de palavras de tamanho <math>i</math> começando de <math>j</math> poder ser gerada de <math>R_k</math>. 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 <math>P \to Q \; R</math> tal que <math>Q</math> coincide com a primeira parte e <math>R</math> coincide com a segunda parte. Caso sim, ele grava <math>P</math> 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:

:<math>\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}</math>

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

{| class="wikitable"
|+Tabela CYK
|-
| '''S'''
|-
|       || VP
|-
|       || &nbsp;||
|-
| '''S'''     ||       ||      ||
|-
|       || VP    ||      ||      || PP
|-
| '''S'''||       || NP   ||      ||       || NP
|-
| NP    || V, VP || Det. || N    || P     || Det || N
|- style="border-top:3px solid grey;"
| 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<sub>k</sub> 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 [[booleano]]s. 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 {{harvtxt|Lang|1994}}.

===Analisando gramáticas livre de contexto que não estão na CNF===
Como mostrado por {{harvtxt|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 <math>g</math> para denotar o tamanho da gramática original, o aumento de tamanho no pior caso pode variar de <math>g^2</math> até <math>g^{2 g}</math>, 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'' {{harv|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 [[gramática livre de contexto estocástica|estocásticas]] e [[gramática livre de contexto com pesos|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 computacional|complexidade]] <math>\Theta(n^3 \cdot |G|)</math>, 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. {{harvtxt|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 [[Matriz booliana|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 <math>O(n^{2.38} \cdot |G|)</math>. No entanto, o termo constante escondido pela [[Grande-O|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 {{harv|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: {{harvtxt|Lee|2002}} provou que qualquer analisador para gramáticas livre-de-contexto que executem em tempo <math>O(n^{3-\varepsilon} \cdot |G|)</math> pode ser efetivamente convertido em um algoritmo computando o produto de matrizes <math>n \times n</math> com entradas 0-1 em tempo <math>O(n^{3 - \varepsilon/3})</math>.

== Ver também ==
*[[John Cocke]]
*[[Analisador sintático GLR]]
*[[Algoritmo Earley]]
*[[Gramática de análise sintática de expressão]]

{{Referências}}
{{Reflist}}
{{Refbegin}}

*{{citar livro|último1 =Knuth |primeiro1 =Donald E. |authorlink1=Donald Knuth |título=[[The Art of Computer Programming]] Volume 2: Seminumerical Algorithms |publicado=Addison-Wesley Professional |edição=3rd |data=14 de novembro de 1997 |isbn=0-201-89684-2 |páginas=501 |ref=harv}}
*{{citar periódico|último1 =Lang |primeiro1 =Bernard |título=Recognition can be harder than parsing |periódico=[[Computational Intelligence (journal)|Comput. Intell.]] |ano=1994 |volume=10 |número=4 |páginas=486–494 |id={{citeseerx|10.1.1.50.6982}} |doi=10.1111/j.1467-8640.1994.tb00011.x |ref=harv}}
{{Refend}}
*{{citar periódico |último1=Lange |primeiro1=Martin |último2=Leiß |primeiro2=Hans |título=To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm |ano=2009 |periódico=Informatica Didactica |volume=8 |url=http://www.informatica-didactica.de/cmsmadesimple/index.php?page=LangeLeiss2009 |ref=harv |acessodata=2015-12-14 |arquivourl=https://web.archive.org/web/20141129231153/http://www.informatica-didactica.de/cmsmadesimple/index.php?page=LangeLeiss2009 |arquivodata=2014-11-29 |urlmorta=yes }}
*{{citar periódico|último1 =Lee |primeiro1 =Lillian |título=Fast context-free grammar parsing requires fast Boolean matrix multiplication |periódico=[[Journal of the ACM|J. ACM]] |volume=49 |número=1 |páginas=1–15 |ano=2002 |doi=10.1145/505241.505242 |ref=harv}}
*{{citar livro|último1 =Sipser |primeiro1 =Michael |authorlink1=Michael Sipser |título=Introduction to the Theory of Computation |publicado=IPS |ano=1997 |edição=1st |página=99 |isbn=0-534-94728-X |ref=harv}}
*{{citar periódico|último1 =Valiant |primeiro1 =Leslie G. |authorlink1=Leslie Valiant |título=General context-free recognition in less than cubic time |periódico=[[Journal of Computer and System Sciences|J. Comput. Syst. Sci.]] |volume=10 |número=2 |ano=1975 |páginas=308–314 |doi=10.1016/s0022-0000(75)80046-8 |ref=harv}}
*{{citar periódico|último1 =Younger |primeiro1 =Daniel H.  |data=fevereiro de 1967 |título=Recognition and parsing of context-free languages in time ''n''<sup>3</sup> |periódico=[[Information and Computation|Inform. Control]] |volume=10 |número=2 |páginas=189–208 |doi=10.1016/s0019-9958(67)80007-x}}

== Ligações externas ==
* [http://martinlaz.github.io/demos/cky.html Demonstração do CYK em JavaScript]
* [https://web.archive.org/web/20090401210244/http://www.informatik.uni-leipzig.de/alg/lehre/ss08/AUTO-SPRACHEN/Java-Applets/CYK-Algorithmus.html Applet interativo da Universidade de Leipzig que demonstra o algoritmo CYK (Site em alemão)]
* [http://www.swisseduc.ch/compscience/exorciser/ Exorciser é uma aplicação Java para gerar exercícios no algoritmo CYK bem como Máquinas de Estados Finitos, algoritmos de Markov etc]

[[Categoria:Algoritmos|CYK]]