|
Abstract:
|
O acesso rápido a léxicos eletrônicos é fundamental para muitas aplicações de Processamento de Linguagem Natural. Uma forma de garantir isto é a representação de léxicos grandes através de autômatos finitos determinísticos minimizados, que permitem manter o léxico na memória principal. Em 1991, na sua tese de doutorado, Dominique Revuz apresentou um algoritmo que gera em tempo linear um autômato mínimo acíclico que representa um léxico. Para reduzir o problema da explosão de estados, Revuz apresentou também um algoritmo com reutilização de sufixos, por ele chamado pseudo-minimização, que supõe o léxico em ordem lexicográfica inversa. Em 1998, Maurel & Chauvier apresentaram um algoritmo de pseudo-minimização que não faz exigências de ordenação ao léxico. Jan Daciuk e Stoyan Mihov desenvolveram, independentemente, um algoritmo que mantém o autômato minimal durante a sua geração, por eles chamado de algoritmo incremental. Este algoritmo não utiliza a clonagem de estados, mas exige o léxico em ordem lexicográfica. Além disso, Bruce Watson, também em 1998, apresentou um algoritmo que mantém o autômato, durante a geração, em um tamanho limitado, acima do autômato minimal. Este algoritmo, que exige o léxico em ordem decrescente do tamanho das palavras, foi classificado pelo autor como algoritmo semi-incremental. O presente trabalho apresenta um algoritmo para geração de autômatos mínimos, a partir das características desejáveis dos algoritmos de Revuz, Maurel & Chauvier, Daciuk & Mihov e Watson, resultando num algoritmo semi-incremental com pseudo-minimização que exige o léxico na forma de uma k-partição, sendo esta uma estrutura mais fácil de obter do que a ordem lexicográfica. Para desenvolver este algoritmo, apresenta-se na tese uma versão modificada do algoritmo de Maurel & Chauvier, que divide a palavra em prefixo, meio e sufixo de forma diferente do algoritmo Maurel & Chauvier e que não utiliza a clonagem na inserção do meio da palavra. A tese apresenta uma análise comparativa preliminar dos algoritmos utilizando léxicos em inglês, polonês, francês e português. Esta análise mostra que o algoritmo semi-incremental com pseudo-minimização proposto consegue gerar uma representação de um léxico grande sem necessitar um espaço significativamente maior. |
