Algoritmo CYK

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

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 , em que é o comprimento da cadeia de caracteres e o tamanho da gramática CNF . 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[editar | editar código-fonte]

Em pseudocódigo[editar | editar código-fonte]

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

ROTINA CYK(
    ,     -- cadeia de caracteres a ser testada
    , -- gramática contendo símbolos terminais e não-terminais
    ,      -- símbolos de início da gramática
     -- vetor de booleanos inicializado em 
    )
    PARA CADA i DE 1 A n FAÇA
        PARA CADA  FAÇA
            
    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() FAÇA
                    SE  ENTÃO
                        
    PARA CADA x EM  FAÇA
        SE  ENTÃO
            RETORNE "membro da linguagem"
        SENÃO
            RETORNE "não-membro da linguagem"

Em prosa[editar | editar código-fonte]

Em termos informais, esse algoritmo considera cada possível subsequência da sequência de palavras e conjuntos ser verdadeira se a subsequência de palavras de tamanho começando de poder ser gerada de . 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 tal que coincide com a primeira parte e coincide com a segunda parte. Caso sim, ele grava 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[editar | editar código-fonte]

Esse é um exemplo de gramática:

A sentença ela come um peixe com um garfo é analisada utilizando o algoritmo CYK. Na tabela a seguir, em , é o número da linha (começando inferiormente em 1) e é 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 Rk 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[editar | editar código-fonte]

Gerando uma árvore sintática[editar | editar código-fonte]

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[editar | editar código-fonte]

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 para denotar o tamanho da gramática original, o aumento de tamanho no pior caso pode variar de até , 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[editar | editar código-fonte]

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[editar | editar código-fonte]

O pior caso do CYK é de complexidade , 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 . 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 pode ser efetivamente convertido em um algoritmo computando o produto de matrizes com entradas 0-1 em tempo .

Ver também[editar | editar código-fonte]

Referencias[editar | editar código-fonte]


Links externos[editar | editar código-fonte]