UNIVERSIDADE TÉCNICA DE LISBOA
INSTITUTO SUPERIOR TÉCNICO
Análise Sintáctica de Superfı́cie
Fernando Manuel Marques Batista
(Licenciado)
Dissertação para obtenção do Grau de Mestre em
Engenharia Electrotécnica e de Computadores
Orientador:
Doutor Nuno João Neves Mamede
Presidente:
Vogais:
Doutor Nuno João Neves Mamede
Doutora Irene Pimenta Rodrigues
Doutor Carlos Jorge da Conceição Teixeira
Doutor António Paulo Teles de Menezes Correia Leitão
Julho de 2003
Resumo
Esta dissertação apresenta um algoritmo de análise sintáctica de superfı́cie, que permite reconhecer, não só as fronteiras dos constituintes sintácticos, como também as respectivas estruturas
internas e categorias sintácticas. Com base neste algoritmo, foi desenvolvido um módulo que permite processar corpora não restrito.
O algoritmo faz uso de uma gramática cuja informação pode ser obtida a partir de um conjunto
de propriedades independentes, que caracterizam uma lı́ngua. Além da definição das estruturas
sintácticas, a gramática comporta uma hierarquia de sı́mbolos e um conjunto de restrições, designado por preferências.
A análise é realizada com base na construção de um grafo dirigido, que permite representar a
sequência de operações, para que sejam realizadas apenas uma vez. O algoritmo tem complexidade
, sendo o número de unidades lexicais do segmento, e pode ser facilmente alterado de forma
a ter as caracterı́sticas de um algoritmo anytime.
A implementação do módulo teve em consideração a integração em sistemas de processamento
de lı́ngua natural, suportando parametrização que permite considerar ou desprezar um conjunto
de princı́pios e regras na realização da análise, e extrair diferentes tipos e formatos de resultados.
Foram desenvolvidas ferramentas, para usar o módulo em plataformas cliente/servidor.
Abstract
This thesis presents a shallow parsing algorithm that recognizes, not only the boundaries, but
also the internal structure and syntactic category for the syntactic constituents. A module was developed, based on the algorithm, that is capable of performing syntactic analysis over unrestricted
text.
The algorithm uses a grammar whose information can be derived from a set of independent
properties, that characterize a language. The grammar supports, in addition to the definition of
syntactic structures, a hierarchy of symbols and a set of restrictions known as preferences.
The analysis uses a directed graph for representing all the operations, preventing redundant
computation. The algorithm has
segment and can be easily adapted to an
complexity, where
is the number of lexical units in the
algorithm.
Integrating the analyzer within larger natural language processing systems was a major concern. The module supports a set of options both for analysis and result extraction. Analysis options
are used for considering or discarding sets of linguistic principles and optional grammar rules, thus
allowing for parameterized analyses and production of different types of results. Tools were also
developed for using the module in client/server platforms.
Palavras Chave
Keywords
Palavras chave
Processamento de Lı́ngua Natural
Análise Sintáctica
Análise de Superfı́cie
Análise Robusta
Gramática de Superfı́cie
Keywords
Natural Language Processing
Syntactic Analysis
Shallow Parsing
Robust Analysis
Surface Grammar
Agradecimentos
Esta tese não teria certamente sido possı́vel, sem o apoio, motivação e encorajamento, que fui tendo
ao longo da sua realização. Expresso aqui os meus agradecimentos a todos, que de uma forma ou
de outra, contribuı́ram para a sua realização.
Ao meu orientador, Professor Nuno Mamede, pela sua orientação, disponibilidade, exigência e acompanhamento sempre constante. O meu profundo agradecimento por tudo o que com ele aprendi.
À Professora Caroline Hagège que, mesmo distante, nunca deixou de estar presente para esclarecer
todas as minhas questões.
À Professora Isabel Trancoso, pela ajuda e amizade que mostrou desde o inı́cio desta tese.
Ao David, Ricardo, Luisa e Joana, pela amizade, inúmeros comentários, crı́ticas e sugestões que
tanto contribuı́ram para o enriquecimento deste trabalho. O meu muito obrigado ao David, Ricardo
e Luisa pela leitura atenta desta tese, e à Joana, companheira de mestrado, pela sua companhia em
inúmeras noitadas de trabalho.
Aos meus colegas do L F, pelos comentários, crı́ticas construtivas e pelo bom ambiente de trabalho
que sempre me proporcionaram.
Aos meus colegas do ISCTE, pelo bom ambiente que me proporcionaram e pela motivaç ão que
transmitiram ao longo do meu percurso.
Ao pessoal do sexto andar, Nuno Santos, João Nuno, Sérgio, Jorge, Professor Rito, Alfonso, pela
amizade e companheirismo.
Por fim, aos meus pais e irmãos, pela sua ajuda incondicional, imensurável apoio e confiança que
em mim depositaram. Dedico-lhes este trabalho.
Lisboa, 11 de Julho de 2003
Fernando Manuel Marques Batista
Francis Bacon
There are and can exist but two ways of investigating
and discovering truth. The one hurries on rapidly
from the senses and particulars to the most general
axioms, and from them... derives and discovers the
intermediate axioms. The other constructs its axioms from the senses and particulars, by ascending
continually and gradually, till it finally arrives at the
most general axioms.
– Novum Organum Book I.19 (1620)
Victor H. Yngne (1960)
This is the malt that the rat that the cat that the dog
worried killed ate.
This is the dog, that worried the cat, that killed the
rat, that ate the malt, that lay in the house that Jack
Built.
– Mother Goose, The House that Jack Built
Douglas E. Appel
Shallow parsing makes mistakes. Get used to it.
– in Introduction to Information Extraction Technology
Conteúdo
1 Introdução
1
1.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.2 O domı́nio da sintaxe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2.1 Análise sintáctica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2.2 Análise de superfı́cie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
1.2.3 Identificação de fragmentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2.4 Análise robusta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
1.2.5 Teorias psicolinguı́sticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6
1.3 Objectivos e Estratégia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1.4 Contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
1.5 Estrutura da dissertação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
2 Enquadramento
13
2.1 As gramáticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.1.1 Gramáticas regulares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.1.2 Gramáticas livres de contexto (CFG) . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.1.3 Gramáticas sensı́veis ao contexto . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
2.1.4 Gramáticas tipo 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
2.1.5 Gramáticas baseadas em formalismos de unificação . . . . . . . . . . . . . . . .
16
2.2 Técnicas de análise sintáctica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.2.1 Estratégias básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.2.2 Análise Esquerda-Direita (LR) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.2.3 Análise com transdutores de estados finitos . . . . . . . . . . . . . . . . . . . . .
18
2.2.4 Algoritmos eficientes de análise sintáctica . . . . . . . . . . . . . . . . . . . . . .
19
2.2.5 Análise em gramáticas moderadamente sensı́veis ao contexto . . . . . . . . . .
19
2.2.6 Análise sintáctica como processo dedutivo . . . . . . . . . . . . . . . . . . . . . .
19
2.2.7 Análise com preferências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
i
2.3 Analisadores orientados para texto não restrito . . . . . . . . . . . . . . . . . . . . . . .
20
2.3.1 Analisador de superfı́cie da Xerox . . . . . . . . . . . . . . . . . . . . . . . . . . .
21
2.3.2 Analisador GREYC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
22
2.3.3 Os analisadores da universidade de Helsı́nquia . . . . . . . . . . . . . . . . . . .
22
2.3.4 Analisador Fidditch
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.3.5 Sistema ANLT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
2.3.6 Sistema PEG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
2.3.7 Analisador PALAVRAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
2.3.8 Conclusões . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
2.4 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3 Análise Sintáctica por Folhas
27
3.1 A descrição linguı́stica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
27
3.1.1 Caracterização da lı́ngua . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
3.1.2 Fonte declarativa do analisador por folhas . . . . . . . . . . . . . . . . . . . . . .
29
3.2 AF - Protótipo de Análise por folhas . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
3.2.1 Funcionamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
3.2.2 Dados de entrada - tratamentos . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
3.2.3 Resultados produzidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
3.2.4 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
3.2.5 A questão da ambiguidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
3.2.6 Casos de tratamento particular . . . . . . . . . . . . . . . . . . . . . . . . . . . .
36
3.3 Extracção de sintagmas nominais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
3.3.1 Sintagma Nuclear . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
3.3.2 O extractor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
39
3.3.3 Condições de avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
3.3.4 Resultados da avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
40
3.4 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
4 Gramática do SuSAna
43
4.1 Elementos da gramática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
4.1.1 Modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
43
4.1.2 Modelo de topo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
4.1.3 Comportamento dos modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
4.1.4 Hierarquia de modelos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
46
4.1.5 Preferências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
ii
4.2 Conversão de gramáticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
4.2.1 Conversão de BNF para Blocos . . . . . . . . . . . . . . . . . . . . . . . . . . . .
48
4.2.2 Conversão de Blocos para BNF . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
4.3 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
5 SuSAna: Analisador de superfı́cie
53
5.1 Objectivos e estratégia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
5.2 Aspectos de funcionamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
5.2.1 Dados de entrada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
5.2.2 Resultados produzidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
5.2.3 Formas de utilização . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
5.3 Funcionamento interno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
5.3.1 Arquitectura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
5.3.2 Repositório . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
61
5.4 O processo de análise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
5.4.1 Criação de novos fragmentos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
5.4.2 Continuação de fragmentos já iniciados . . . . . . . . . . . . . . . . . . . . . . .
66
5.4.3 Validação de modelos candidatos e atribuição de custos . . . . . . . . . . . . . .
66
5.4.4 Registo de caminhos e vértices no repositório . . . . . . . . . . . . . . . . . . . .
67
5.4.5 Parametrizações da análise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
5.4.6 Restrição de resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
5.4.7 Análise da complexidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
73
5.5 Processo de extracção de resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
5.5.1 Elemento de topo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
. . . . . . . . . . . . . . . . . . . .
75
5.5.3 Formatos de saı́da . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
5.5.4 Previsão de modelos em estruturas incompletas . . . . . . . . . . . . . . . . . .
78
5.5.5 Desambiguação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
5.6 Casos de utilização do sistema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
5.6.1 ATA: Aquisição Automática de Termos . . . . . . . . . . . . . . . . . . . . . . . .
79
5.6.2 Poeta: sistema de auxı́lio a escrita de poemas . . . . . . . . . . . . . . . . . . . .
79
5.6.3 Extracção de sintagmas nominais . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
5.6.4 Testes sobre corpus com e sem ambiguidade . . . . . . . . . . . . . . . . . . . .
79
5.7 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
81
5.5.2 Re-definição dos parâmetros
e
iii
6 Avaliação
83
6.1 Condições de avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
6.2 Gramática . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
6.3 Comparação entre o AF e o SuSAna . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
6.3.1 Preparação dos dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
6.3.2 Preparação e parametrização dos analisadores . . . . . . . . . . . . . . . . . . .
86
6.3.3 Corpus utilizado na avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86
6.3.4 Processo para extracção de resultados . . . . . . . . . . . . . . . . . . . . . . . .
87
6.3.5 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
6.4 Desempenho do SuSAna em corpus alargado . . . . . . . . . . . . . . . . . . . . . . . .
90
6.4.1 Parâmetros de avaliação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
6.4.2 Caracterı́sticas do corpus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
6.4.3 Preparação dos dados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
6.4.4 Os resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
6.5 Sumário . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
99
7 Conclusões e trabalho futuro
101
7.1 Trabalho futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
A Descrição das categorias e modelos
105
Glossário
109
Bibliografia
113
Índice Remissivo
119
iv
Lista de Figuras
1.1 Cadeia de processamento de um sistema de lı́ngua natural. . . . . . . . . . . . . . . . .
4
3.1 Constituição da metodologia 5P. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28
3.2 Exemplos de propriedades de existência, que definem o sintagma nominal nuclear. . .
28
3.3 Excerto da definição linguı́stica utilizada pelo AF. . . . . . . . . . . . . . . . . . . . . .
29
3.4 Regras que produzem uma hierarquia de categorias para os nomes. . . . . . . . . . . .
31
3.5 Diagrama representativo de uma hierarquia de categorias para os nomes. . . . . . . .
31
3.6 Forma de produção de informação adequada à entrada do AF. . . . . . . . . . . . . . .
33
3.7 Exemplo de uma frase com duas alternativas. . . . . . . . . . . . . . . . . . . . . . . . .
34
3.8 Análise da frase “as minhas muito belas raparigas”, incluindo flechagem. . . . . . . .
35
3.9 Representação gráfica da análise de uma frase, incluindo flechagem. . . . . . . . . . .
35
3.10 Diagrama de funcionamento da análise por folhas. . . . . . . . . . . . . . . . . . . . . .
36
3.11 Cadeia de processamento do sistema de extracção de SN. . . . . . . . . . . . . . . . . .
38
4.1 DTD da gramática do SuSAna. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
4.2 Exemplo de uma mini-gramática em formato BNF. . . . . . . . . . . . . . . . . . . . . .
48
4.3 Regras com a estrutura de blocos correspondente à mini-gramática. . . . . . . . . . . .
49
5.1 Cadeia de processamento utilizada em testes com o SuSAna. . . . . . . . . . . . . . . .
55
5.2 Extracto de informação produzida pelo PaSMo. . . . . . . . . . . . . . . . . . . . . . . .
56
5.3 Extracto de Informação convertido no formato de leitura do SuSAna. . . . . . . . . . .
57
5.4 Código XSL para converter informação no formato do SuSAna. . . . . . . . . . . . . . .
58
5.5 DTD dos elementos processados pelo SuSAna. . . . . . . . . . . . . . . . . . . . . . . .
59
5.6 Análise sintáctica da frase “A água gela em os carreiros”. . . . . . . . . . . . . . . . . .
60
5.7 Utilização do SuSAna como módulo, num sistema de processamento da lı́ngua. . . . .
60
5.8 Utilização do SuSAna numa plataforma cliente/servidor através de RPC. . . . . . . . .
61
5.9 Árvores de análise da frase: “A água gela em os carreiros”. . . . . . . . . . . . . . . . .
61
5.10 SuSAna – arquitectura interna. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
62
v
5.11 Estrutura do repositório de dados. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
5.12 Diagrama de funcionamento da análise. . . . . . . . . . . . . . . . . . . . . . . . . . . .
64
5.13 Procura de possı́veis caminhos entre modelos. . . . . . . . . . . . . . . . . . . . . . . . .
65
5.14 Análise de múltiplas estruturas, sem sobreposição e sem desprezar unidades lexicais.
70
5.15 Análise de múltiplas estruturas, com sobreposição e sem desprezar unidades lexicais.
71
5.16 Análise de múltiplas estruturas, com possibilidade de desprezar unidades lexicais. . .
71
5.17 DAG – Possibilidades de construção de um fragmento. . . . . . . . . . . . . . . . . . . .
72
5.18 DAG – Processo utilizado na desactivação de arcos. . . . . . . . . . . . . . . . . . . . .
73
5.19 Representação da análise de uma frase constituı́da por quatro hipóteses. . . . . . . . .
75
5.20 Análise em formato XML, da frase: A ainda mais bela rapariga. . . . . . . . . . . . . .
76
5.21 Extracto da análise de segmentos, no formato: contagens. . . . . . . . . . . . . . . . . .
76
5.22 Resultado da análise de um segmento em formato: texto. . . . . . . . . . . . . . . . . .
77
5.23 Resultado da análise de um segmento em formato: sintagmas. . . . . . . . . . . . . . .
77
5.24 Grafo de análise da frase: O Jorge disse que o João saiu em o carro. . . . . . . . . . . .
78
6.1 Produção de informação adequada ao processamento pelo AF e pelo SuSAna. . . . . .
85
6.2 Diagrama de processamento de resultados produzidos pelo AF e pelo SuSAna. . . . .
88
6.3 Tipos de diferenças obtidas na análise dos textos de constituição. . . . . . . . . . . . .
89
6.4 Distribuição de segmentos por número de unidades lexicais. . . . . . . . . . . . . . . .
92
6.5 Distribuição do número de alternativas obtidas em cada análise. . . . . . . . . . . . .
95
6.6 Número médio de soluções por segmento do corpus, em função do seu tamanho. . . . .
96
6.7 Distribuição das análises em função do seu tamanho. . . . . . . . . . . . . . . . . . . .
96
6.8 Distribuição do número de soluções em função do número de unidades lexicais. . . . .
97
6.9 Tempo de análise dos segmentos em função do seu tamanho. . . . . . . . . . . . . . . .
98
6.10 Tempo de análise por palavra, em função do tamanho do seu segmento. . . . . . . . .
98
vi
Lista de Tabelas
2.1 Resumo das caracterı́sticas dos analisadores de superfı́cie. . . . . . . . . . . . . . . . .
25
3.1 Avaliação do quanto à existência de sintagmas nominais. . . . . . . . . . . . . . . . . .
41
3.2 classificação quanto ao teor dos SNs correctamente identificados. . . . . . . . . . . . .
41
5.1 Comparação do tempo de processamento do SuSAna com base na ambiguidade. . . . .
80
5.2 Comparação do número de soluções por cada resultado em função da ambiguidade. . .
80
6.1 Caracterı́sticas da máquina usada na avaliação. . . . . . . . . . . . . . . . . . . . . . .
83
6.2 Caracterı́sticas dos textos utilizados para comparar os analisadores. . . . . . . . . . .
87
6.3 Comparação do desempenho do AF com o SuSAna. . . . . . . . . . . . . . . . . . . . . .
90
6.4 Resumo das caracterı́sticas do corpus usado na avaliação do SuSAna . . . . . . . . . .
91
6.5 Resultados obtidos na análise do corpus.
93
vii
. . . . . . . . . . . . . . . . . . . . . . . . . .
viii
Lista de Algoritmos
1
2
3
C ONVERTER B NF E M B LOCOS(gramática) . . . . . . . . . . . . . . . . . . . . . . . . . . .
C RIAR B LOCO( ,
) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
M APEAR B LOCOS E M B NF( 49
49
) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
4
C OMPLETAR R EGRA B NF(
, ) . . . . . . . . . . . . . . . . . . . . . . . . . . . .
50
5
C ALC -M ODELS( , ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
6
G ET-S IBLING -M ODELS( , , ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
66
7
8
9
,
C ALC -B RANCHES( , , ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
G ET-D AG -V ERTICE( ,
, ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
D O-A NALYSIS(
,
,
,
,
ix
) . . . . . . . . . . . . . . . . . . . .
69
x
O aumento significativo da quantidade de informação em suporte digital que se tem verificado
durante os últimos anos, em especial devido à proliferação da Internet e ao desenvolvimento dos
meios de comunicação social, tem permitido a criação de repositórios de corpora cada vez mais
abrangentes, que constituem recursos de extrema importância para o processamento da lı́ngua.
Estes corpora cobrem uma grande variedade de domı́nios e muitas vezes as construções nelas presentes não são contempladas pelas gramáticas tradicionais. Surge assim a necessidade de desenvolver sistemas de processamento e manipulação de corpora que tenham a capacidade de lidar com
grandes quantidades de texto não restrito.
Os sistemas de tratamento de informação ao nı́vel morfossintáctico encontram-se num estado
de desenvolvimento avançado, permitindo a produção de resultados bastante fiáveis. Os analisadores morfológicos de ampla cobertura têm, hoje em dia, taxas de erro muito baixas e os sistemas
de desambiguação encontram-se em pleno desenvolvimento, proporcionando taxas de erro cada vez
mais baixas. Vão surgindo, assim, as condições necessárias para o processamento da lı́ngua aos
nı́veis sintáctico e semântico.
A análise sintáctica de uma frase, no contexto de uma dada linguagem, consiste em reconhecer
essa frase como fazendo parte da linguagem e em associar-lhe uma estrutura, designada por estrutura sintáctica. A análise sintáctica é especialmente útil para tarefas de verificação gramatical
em sistemas de processamento de lı́ngua natural, pois a impossibilidade de atribuir uma estrutura sintáctica a uma dada frase, é um indicador que esta pode conter erros gramaticais ou ser de
difı́cil leitura. O processamento sintáctico tem aplicação nas mais variadas áreas, como é o caso
da sı́ntese e reconhecimento de fala, pesquisa e extracção de informação e tradução automática. É
também um ponto de partida para sistemas de processamento semântico, na medida em que estabelece um importante nı́vel de representação intermédio. Em suma, a análise sintáctica torna visı́vel
uma grande quantidade de informação, que leva ao desenvolvimento de aplicações mais complexas
e poderosas.
No âmbito desta tese, foram estudados sistemas de análise sintáctica de superfı́cie, cujas principais caracterı́sticas são, por um lado, a capacidade de lidar com texto real em diferentes domı́nios
e, por outro, a capacidade de processar grandes quantidades de texto. A capacidade de lidar com
texto real em diferentes domı́nios relaciona-se com a capacidade de conseguir processar algumas
construções não gramaticais e simultaneamente evitar a explosão de análises, de forma a manter
os resultados utilizáveis por outras aplicações. Esta dissertação apresenta um módulo de análise
sintáctica de superfı́cie que permite tratar corpora não restritos, identificando nesses corpora, fronteiras, categoria sintáctica e a estrutura sintáctica dos seus constituintes sintácticos. O módulo
utiliza um algoritmo eficiente e suporta um conjunto de opções que lhe permitem, por um lado
CAPÍTULO 1. INTRODUÇÃO
2
realizar a análise considerando ou não certos princı́pios e regras gramaticais e, por outro, extrair
diferentes tipos de resultados de forma a contemplar um possı́vel conjunto de requisitos por parte
de outras aplicações. O desempenho foi um aspecto importante na concepção do algoritmo, de forma
a que o módulo pudesse ser utilizado no processamento de grandes quantidades de corpora.
1.1 Motivação
O desenvolvimento dos meios de comunicação social, bem como a crescente utilização dos sistemas computacionais como meios de comunicação, tem conduzido a um aumento de informação em
suporte digital. As tarefas de identificar, classificar e organizar, assumem um papel fundamental
para que a quantidade de informação não seja um obstáculo à sua consulta. Como a informação
se encontra em suporte digital, torna-se importante a criação de ferramentas para seu o processamento automático. Contudo, devido aos inúmeros formatos em que se pode encontrar, a sua
identificação e classificação pode ser apenas feita com base no seu conteúdo, surgindo assim a necessidade de criar ferramentas para o processamento da lı́ngua natural que sirvam de suporte a esse
tipo de tarefas. Os sistemas de análise sintáctica de superfı́cie adequam-se a este contexto, pois são
indicados para o processamento de grandes quantidades de informação, permitindo identificar os
elementos sintácticos que aı́ se encontram.
Um dos principais objectivos do Laboratório de Sistemas de Lı́ngua Falada (L F) do INESC-ID
tem sido a criação, manutenção, validação e disseminação de recursos essenciais ao processamento
da lı́ngua portuguesa falada, nomeadamente: corpora, léxicos e ferramentas computacionais. A
investigação e desenvolvimento em sistemas de processamento de lı́ngua falada tem conduzido à
utilização da investigação efectuada ao nı́vel do processamento da lı́ngua escrita, tais como a morfologia, sintaxe e semântica. Com o propósito de desenvolver um sistema integrado de processamento
da lı́ngua, têm vindo a ser criados vários módulos que executam tarefas como análise morfológica,
tratamento de informação morfológica e desambiguação morfossintáctica. Foi igualmente proposta
a criação de um módulo de análise sintáctica de superfı́cie a que foi dado o nome SuSAna (Surface
Syntactic Analyser), que corresponde ao sistema descrito nesta tese. Cada uma destas ferramentas
pode ser utilizada de forma isolada, ou eventualmente integrada noutros sistemas ou ferramentas,
pelo que devem ser independentes para facilitar o processo de integração. Esta caracterı́stica é essencial se se tiver em consideração que, por vezes, é importante substituir módulos de um sistema
por outros mais fiáveis ou mais eficientes.
As principais motivações para o desenvolvimento de um analisador sintáctico de superfı́cie,
estão ligadas aos projectos em curso e às áreas onde actualmente se faz investigação dentro do Laboratório. Por exemplo, no âmbito do projecto ATA (Paulo e Mamede, 2001), está a ser desenvolvido
um sistema de aquisição automática de termos, que faz uso de um módulo de análise sintáctica
para extrair o conjunto de candidatos a termos ou sintagmas nominais de um corpus. A informação
sintáctica assume, assim, um papel fundamental na produção dos seus resultados (Paulo et al.,
2002), sendo, para isso, necessário utilizar um sistema que permita fazer o tratamento de grandes quantidades de corpora não restrito. O módulo de análise sintáctica constitui também uma
plataforma para o desenvolvimento de trabalho na áreas da sintaxe e da semântica, também em
investigação no L F (Coheur e Mamede, 2002).
O módulo de análise de superfı́cie poderá também ser aplicado a outras áreas do Laboratório,
1.2. O DOMÍNIO DA SINTAXE
3
tais como a produção de indicadores para a variação da prosódia num sistema de sı́ntese de fala;
pesquisa e extracção de informação (Appelt e Israel, 1999); e tradução automática. Os analisadores
sintácticos podem também ser utilizados em lexicografia para a produção de dicionários online.
No que diz respeito à sı́ntese de fala em sistemas texto-para-fala (text-to-speech), vários trabalhos mostram que o processamento da lı́ngua ao nı́vel sintáctico pode trazer melhorias significativas. Koehn et al. (2000) conclui que a introdução de informação sintáctica pode melhorar
significativamente a qualidade da separação entonacional. Fach (1999) apresenta resultados experimentais de uma comparação entre a divisão prosódica e sintáctica que levam a assumir que
a informação sobre fronteiras prosódicas pode ser derivada da estrutura sintáctica. Abney (1992)
propõe estruturas independentes, baseadas em divisões sintácticas, que designa por chunks, para
dar conta da prosódia e conclui que a estrutura sintáctica pode ser um bom preditor para as estruturas prosódicas.
No que diz respeito aos sistemas de reconhecimento de fala, é possı́vel produzir representações
baseadas em fragmentos sintácticos (chunks) para o reconhecimento de fala espontânea em
domı́nios não restritos, com elevado nı́vel de precisão (Zechner e Waibel, 1998), apesar de Fach
(1999) reportar resultados pouco satisfatórios nas suas experiências.
1.2 O domı́nio da sintaxe
Esta secção introduz o conceito de análise sintáctica, as condições para a sua realização e os
resultados que daı́ advêm. São mencionados alguns aspectos a ter em conta na realização da análise
quando as suas condições são difı́ceis e apresenta a análise de superfı́cie como alternativa à análise
sintáctica tradicional. É também abordada a identificação de fragmentos de análise, usualmente
conhecidos na comunidade cientı́fica como chunks. Finalmente, apresentam-se algumas teorias
psicolinguı́sticas que se enquadram na tentativa de tornar a análise mais eficiente e melhorar a
sua qualidade.
1.2.1
Análise sintáctica
A estrutura sintáctica de uma frase indica de que forma as suas unidades lexicais se relacionam entre si, isto é, como é que as palavras são agrupadas em sintagmas, que palavras modificam
outras palavras e quais as palavras que têm maior importância na frase. De uma forma geral, o
processamento sintáctico de um texto é realizado com base em informação morfossintáctica previamente atribuı́da às unidades lexicais desse texto. A figura 1.1 mostra um sistema de processamento
de lı́ngua natural, que realiza processamento sintáctico. O resultado produzido por cada um dos
módulos que compõem a análise morfológica pode servir de base à etapa da análise sintáctica, o que
corresponde a realizar a análise com base em informação desambiguada ou não.
O processamento sintáctico de um texto pode ser realizado a vários nı́veis, dependendo do tipo
de resultados pretendidos e dos recursos disponı́veis para a obtenção desses resultados. Os sistemas
que tentam fazer análise em profundidade, tendem a respeitar a pureza da linguı́stica, tentam
resolver problemas complexos da lı́ngua e identificam todos os constituintes sintácticos de uma
frase gramaticalmente aceite.
CAPÍTULO 1. INTRODUÇÃO
4
Figura 1.1: Cadeia de processamento de um sistema de lı́ngua natural.
A análise sintáctica tradicional, que consiste em realizar uma análise em profundidade, exige
bases de dados lexicais de ampla cobertura, implicando muitas vezes sobre-análise e inadequação à
análise de textos reais. Comparativamente a este tipo de análise, a análise sintáctica de superfı́cie,
pode ser aplicada a variados domı́nios e com tempos de processamento mais baixos, embora produzindo resultados menos fiáveis.1 A análise de superfı́cie adequa-se ao processamento de grandes quantidades de texto, que pode ser ou não restrito, e à produção de resultados para posterior
utilização numa vasta gama de aplicações.
1.2.2
Análise de superfı́cie
O termo sintaxe de superfı́cie, do inglês shallow syntax, é uma designação genérica para a
análise que não tem em consideração aspectos linguı́sticos complexos. A saı́da de uma análise de
superfı́cie não é uma árvore de estrutura sintagmática no sentido tradicional, pois pode consistir
apenas na identificação de alguns constituintes sintagmáticos, tais como frases nominais, sem indicar a sua estrutura interna e a sua função na frase; ou na identificação do papel funcional de
algumas unidades lexicais, tais como o verbo principal e os seus argumentos directos.
Os sistemas de análise de superfı́cie, do inglês shallow parsers, usualmente operam com base
em informação morfológica, desambiguada ou não e, procuram identificar sintagmas e relações
núcleo/modificador (head/modifier). De uma forma geral este tipo de analisadores permite a an álise
de grandes quantidades de corpora. Uma vez que estes corpora contém frequentemente fenómenos
que tornam difı́cil a análise, tais como omissões de palavras e palavras incorrectas, as análises parciais são por vezes permitidas no caso do analisador não ser capaz de resolver todos os problemas.
A análise de superfı́cie compreende pelo menos a resolução dos três problemas seguintes, de
difı́cil tratamento pela análise sintáctica convencional.
Segmentação apropriada do texto, em unidades sintácticas;
Desambiguação, que consiste em seleccionar um conjunto reduzido de análises correctas do
ponto de vista semântico e pragmático, a partir de um número potencialmente elevado de
análises, que se podem produzir a partir das restrições impostas pela gramática;
1 Fenómenos linguı́sticos, que tornam a análise demasiado complexa e ocorrem um número reduzido de vezes, podem ser
ignorados de forma a reduzir a complexidade da análise.
1.2. O DOMÍNIO DA SINTAXE
5
Sub-geração, que consiste em lidar com casos de entradas fora da cobertura lexical ou
sintáctica dos sistemas.
1.2.3
Identificação de fragmentos
A análise e identificação de fragmentos (chunks), tem sido tratada por vários investigadores
e em variados contextos (Abney, 1991, 1996). A noção de chunk, não foi até agora definida formalmente em qualquer um desses contextos, tem sido sempre apresentada intuitivamente, atrav és
de exemplos. De uma forma geral, um chunk é uma sequência de unidades lexicais onde se verificam determinadas propriedades linguı́sticas, correspondendo a estruturas sintácticas relativamente simples, na medida em podem ser descritas por exemplo com gramáticas livres de contexto
(CFG) (Abney, 1996). A forma mais simples para reconhecimento de fragmentos, consiste em considerar como fragmentos, tudo o que estiver delimitado por palavras funcionais ou palavras chave.
Ross e Tukey utilizaram esta técnica e introduziram também a noção de chink que corresponde a
conjuntos de stop-words (Abney, 1996).
Abney (1996) considera que chunks são sintagmas contı́guos não recursivos, indicando que uma
gramática livre de contexto é suficiente para definir a sua estrutura. Os chunks de Abney podem
ser vistos com árvores não ligadas ao nó de topo da frase, que implica uma análise sintáctica em
dois tempos: a delimitação dos chunks e a sua junção. De uma forma geral os chunks correspondem
a porções de constituintes sintácticos tradicionais, como é o caso dos sintagmas nominais (SNs)
ou sintagmas verbais (SVs), embora também se encontrem algumas excepções, como é o caso dos
sintagmas verbais complexos (SVC) (Zechner e Waibel, 1998), que não são usados nos paradigmas
linguı́sticos tradicionais. Nos seus trabalhos, Giguet (1998) utiliza estruturas semelhantes aos
chunks de Abney, designadas por sintagmas minimais.
O trabalho que se pretende realizar no âmbito desta tese, será inicialmente aplicado à
identificação de domı́nios sintácticos designados por sintagmas nucleares, introduzidos e tratados
por Hagège (2000). Os sintagmas nucleares são caracterizados por constituı́rem um meio-termo
entre os conceitos do texto e os sintagmas tradicionais. Estes domı́nios linguı́sticos constituem
subconjuntos do sintagma tradicional, podendo por vezes confundir-se com ele. Os sintagmas nucleares apresentam propriedades particulares que são mais simples de descrever e reconhecer do
que os sintagmas tradicionais. Embora semelhantes aos chunks de Abney e aos sintagmas minimais de Giguet, distinguem-se destes últimos por, além de poderem ser constituı́dos por categorias,
poderem também conter outros sintagmas nucleares.
1.2.4
Análise robusta
Muitas vezes, os dados linguı́sticos sobre os quais é efectuada a análise encontram-se incompletos ou incorrectos: por exemplo, a passagem da um corpus de fala para texto, através de transcrição
fonética, poderá dar origem a um conjunto de erros tais como falta, inserção ou identificação incorrecta de palavras, ou simplesmente ruı́do. Torna-se difı́cil a atribuição de caracterı́sticas morfológicas, sintácticas ou semânticas a esses textos. Os pedaços incompletos ou fragmentados podem
ser compreensı́veis num contexto, mas dificilmente poderão ser analisados por gramáticas convencionais concebidas apenas para processar informação sem erros. Um sistema poderá ser considerado
CAPÍTULO 1. INTRODUÇÃO
6
robusto se o seu funcionamento tiver em consideração alguns ou todos os problemas mencionados
(Salton, 1989).
A utilização de rotinas de correcção ortográfica pode resolver alguns problemas relacionados
com palavras isoladas, tais como erros ortográficos e utilização de palavras desconhecidas. Em alternativa, podem ser associados marcadores sintácticos e semânticos, a essas palavras, de acordo
com as expectativas originadas pelo contexto. A existência de sufixos e outras especificações morfológicas fornecem, por vezes, pistas acerca da função de determinadas palavras. Um dos processos
que pode ser aplicado a uma variedade entradas incomuns, consiste em usar uma gramática convencional para analisar todas as possibilidades para essas entradas. Quando a entrada é ambı́gua
e são produzidas várias análises diferentes, aplica-se um processo de limitaç ão de resultados, realizando, por exemplo, uma ordenação das interpretações em termos de preferência, através de um
processo de atribuição de pesos.
O trabalho que se pretende realizar no âmbito desta tese compreende essencialmente a análise
de textos não restritos, onde podem existir unidades lexicais desconhecidas e onde podem ocorrer
construções pouco comuns do ponto de vista gramatical. Um dos requisitos mais importantes para
sistemas de processamento de textos reais, será conseguir extrair o maior conjunto possı́vel de
informação sobre esses textos e, simultaneamente, manter essa informação tratável por outras
aplicações. Assim, o trabalho a realizar deverá ser de tal forma robusto, que permita seleccionar as
análises mais prováveis de um conjunto de análises possı́veis e em simultâneo, e permitir também
contornar a ocorrência de palavras desconhecidas.2
1.2.5
Teorias psicolinguı́sticas
A ambiguidade é um problema inerente ao processamento da lı́ngua natural. Este tema
relaciona-se com as formas de tornar a análise mais eficiente e por vezes determinista, envolvendo
técnicas de escolha entre diferentes interpretações que o analisador possa encontrar.
As gramáticas associam mais do que um significado a sequências de palavras, que usualmente podem ser expressos de várias formas. Assim, os sistemas de análise têm de decidir as
interpretações correctas de uma dada construção e seleccioná-las de um conjunto de múltiplas
hipóteses (Strzalkowski, 1994). De uma forma geral, a análise estrutural de uma frase consiste
em encontrar todas as suas possı́veis interpretações, contudo esses processos de análise nem sempre correspondem ao processo intuitivo que as pessoas realizam no processamento sint áctico da
linguagem. Em particular, a análise realizada por um humano é, na maioria das vezes, um processo determinı́stico, isto é, não consiste numa procura extensiva de todas as possibilidades, mas
sim em utilizar o conhecimento que dispõe no momento, para indicar a interpretação adequada.
Segundo Allen (1995), têm sido realizadas experiências de forma a perceber como frases são
analisadas pelos seres humanos. Psicolinguistas têm utilizado uma grande variedade de técnicas,
que vão desde a utilização da intuição para escolha das possı́veis interpretações até a experiências
de monitorização passo-a-passo de como as pessoas lêem e ouvem a sua lı́ngua. Jurafsky e Martin
(2000) indicam que não existe ainda acordo entre os investigadores acerca da forma correcta de
modelar a análise pelos humanos, contudo as experiências têm revelado alguns princı́pios gerais
2 Palavras
que não puderam ser etiquetadas pelo analisador ou etiquetador morfossintáctico.
1.2. O DOMÍNIO DA SINTAXE
7
acerca de como as pessoas resolvem a ambiguidade. Um dos mais importantes resultados destas experiências é a conclusão de que os humanos não atribuem peso igual a todas as possı́veis
interpretações sintácticas. Os tópicos seguintes apresentam algumas heurı́sticas e técnicas que
derivam destes estudos e podem ser aplicadas à análise para a tornar mais precisa e eficiente.
Aposição mı́nima
Frazier e Fodor (1978) introduziram o princı́pio designado por aposição mı́nima (minimal attachment), que estipula que na falta de outra informação, os constituintes da frase devem ser associados de forma a minimizar a complexidade da análise. Em termos de resultados, o princı́pio
defende que se preferem as análises sintácticas cujas árvores sintácticas correspondentes contenham o menor número de nós. A aplicação deste princı́pio ao processo de análise, corresponde a
preferir adicionar a próxima palavra ao nó actual do que tentar criar um novo nó, aquando da
construção da árvore sintáctica.
Associação à direita
O segundo princı́pio designado por associação à direita (right association) ou fecho tardio (late
closure) foi introduzido por Kimball (1973). O princı́pio diz que, os novos constituintes são preferencialmente interpretados como fazendo parte do constituintes em construç ão, em alternativa a fazer
parte de outro constituinte de nı́vel superior na árvore. Por exemplo, para a frase:
O Jorge disse que o Henrique saiu no carro.
a interpretação preferida é a de que o Henrique saiu no carro em alternativa a que o Jorge falou no
carro, embora ambas as interpretações sejam válidas do ponto de vista sintáctico.
Incompatibilidade dos princı́pios
Allen (1995) refere que em certos casos os dois princı́pios anteriores são incompatı́veis, situação
em que as unidades lexicais podem influenciar as preferências da análise. Nestes casos podem
ser apenas aplicadas preferências ao nı́vel do léxico. Por exemplo, se um verbo sub-categoriza um
sintagma preposicional então o sintagma preposicional deve ser acoplado ao sintagma verbal (Allen,
1995).
Dowty et al. (1988) refere que o debate acerca da formulação e interacção dos princı́pios anteriores é causado pela sua falta de precisão e, ao mesmo tempo, pelo facto de serem demasiado
especı́ficos. Dowty et al. (1988) propõe uma plataforma de trabalho na qual se podem formular
versões melhoradas destes princı́pios. A plataforma proposta, mostra que os princı́pios correspondem a duas regras precisas acerca da escolha entre as acções alternativas de análise.
CAPÍTULO 1. INTRODUÇÃO
8
1.3 Objectivos e Estratégia
O tratamento automático de lı́nguas segue actualmente várias tendências. Algumas delas privilegiam a aplicação de um formalismo gramatical particular, no qual se mostra como resolvem
um conjunto de fenómenos linguı́sticos especı́ficos, através de uma série de exemplos que ilustram
esses mesmos fenómenos. No que diz respeito ao tratamento de textos não restritos, este tipo de
aproximação é muitas vezes inapropriado, pelas seguintes razões:
Os exemplos que utilizam são dados em contextos particulares, contrariamente ao que se
passa em textos reais;
Em textos reais há muitos desvios relativamente às formas canónicas previstas nas
gramáticas (Chanod, 2000);
A lı́ngua não é considerada como um todo, mas como um conjunto não exaustivo de fenómenos
linguı́sticos. A ilustração de cada um dos fenómenos tratados por uma gramática em particular é feita para cada construção particular deixada em aberto, dando ideia de esquecer
todas as outras construções. Não há uma tentativa de integrar as diferentes descrições e as
gramáticas formais que deveriam ter uma cobertura linguı́stica razoável perdem-se na “pureza” do seu formalismo (Hagège, 2000).
Na corrente dos formalismos gramaticais baseados na unificação, a noção de “cobertura mais
abrangente possı́vel” relaciona-se com a capacidade de tratar caso a caso a maioria dos problemas
sintácticos da lı́ngua, e torna-se inadequada ao processamento de textos reais. Em contraposição,
nas correntes de engenharia o objectivo é o de aplicar métodos genéricos e automáticos ao tratamento dos textos, ignorando por vezes certos casos particulares. As correntes de engenharia pecam
pela falta de observação real dos textos.
No âmbito desta tese, pretendem-se desenvolver mecanismos adequados ao tratamento de textos não restritos, partindo do trabalho realizado por Hagège (2000). Este trabalho consistiu em
observar as realizações da lı́ngua na tentativa de as generalizar para, por um lado, tentar descrever
o seu funcionamento, e por outro, utilizar os resultados das suas descrições em algoritmos orientados para textos reais. Assim, o trabalho desta tese enquadra-se numa das correntes linguı́sticas,
conhecida como a corrente realista, que se distingue pela realidade dos textos e na qual o objectivo
é a capacidade de processar textos efectivamente produzidos, sem correcções de ı́ndole linguı́sticas
prévias (Hagège, 2000).
O interesse de tratar texto não restrito é evidente, tento em conta que a quantidade de corpora
armazenados electronicamente tem vindo a aumentar nos últimos anos. Os corpora fornecem um
vasto conjunto de informação, razão pela qual é importante ter ferramentas que permitam facilitar
a obtenção e tratamento dessa informação. Em geral, os analisadores sintácticos apoiam-se sobre
uma gramática que lhes permite descriminar as sequências gramaticais e agramaticais. Assim, a
sua utilização no processamento de textos reais é dificultada pelos seguintes motivos:
Não existem dicionários completos. A análise de texto não restrito implica o tratamento de
elementos desconhecidos que compõem a análise, em oposição a uma análise tradicional que
pressupõe que todos os elementos sejam conhecidos;
1.3. OBJECTIVOS E ESTRATÉGIA
9
Não existe uma gramática completa, em especial se as frases a tratar não são canónicas. É
difı́cil prever numa gramática todas as construções possı́veis na lı́ngua;
As frases longas, apresentado ambiguidade lexical e estrutural, geram uma explosão combinatória de possı́veis análises.
Qualquer analisador que pretenda tratar textos reais terá de se confrontar com estes problemas.
Os analisadores de superfı́cie (shallow parsers) ou parciais (partial parsers) são, de uma forma
geral, orientados ao processamento de textos reais, sobre os quais podem produzir o que se designa por uma análise de superfı́cie, por vezes parcial. Análise parcial porque produzem por vezes
análises incompletas e linguisticamente pouco refinadas; de superfı́cie dado que não procuram dar
uma profunda descrição da estrutura sintáctica (sintagmas intrincados uns nos outros) da entrada
analisada. Os analisadores de superfı́cie ou parciais são também por vezes dotados de robustez, na
medida em que processam qualquer tipo de sequências incluindo as mal formadas e com palavras
desconhecidas.
No âmbito desta tese, são estudados sistemas de análise sintáctica de superfı́cie, bem como
técnicas de análise robusta. É estudado, o funcionamento do protótipo de análise de superfı́cie
AF (analisador por folhas) (Hagège, 2000), no que diz respeito ao seu algoritmo e à informação
por ele utilizada e produzida. São também abordados outros sistemas de análise sintáctica de
superfı́cie existentes, de forma a enquadrar os métodos empregues e a dar conta de aspectos de
difı́cil tratamento na análise de superfı́cie. O resultado deste estudo é aplicado no desenvolvimento
de um módulo de análise de superfı́cie, com vista à futura integração em sistemas de processamento
de lı́ngua. O módulo a desenvolver possui as seguintes caracterı́sticas:
Capacidade de lidar com corpora não restritos (também designado por texto real), que corresponde a textos não previamente corrigidos a nı́vel linguı́stico;
Dar conta de fenómenos, como são o caso de construções pouco comuns e palavras desconhecidas. Para este efeito é necessário dotar o analisador de alguma robustez;
Utilização de mecanismos de restrição de análises, de forma a impedir a explosão de hipóteses
para uma dada análise, mantendo assim o resultado utilizável por outras aplicações;
Possibilidade de integração e funcionamento dentro de outros sistemas;
Capacidade de processar grandes quantidades de corpora de uma forma eficiente.
Além das caracterı́sticas acima mencionadas, o módulo foi desenvolvido na linguagem de
programação C++. Numa primeira fase, foi implementado um módulo que permite produzir os mesmos resultados produzidos pelo protótipo AF, utilizando um algoritmo não optimizado. Posteriormente, foi desenvolvida uma versão com um algoritmo optimizado, que permite produzir os mesmos
resultados, com maior eficiência. A versão final manipula toda a informação em formato XML (Bray
et al., 2000). Paralelamente ao desenvolvimento do módulo, foi desenvolvida uma aplicação que permite a utilização isolada desse módulo, a partir de informação previamente preparada, permitindo
assim a realização de testes e análises de forma autónoma. Finalmente, foi também desenvolvido
um módulo servidor de RPC (Remote Procedure Call), que inclui o módulo de análise de superfı́cie e
permite a sua utilização numa plataforma cliente/servidor, através de outro módulo cliente, também
desenvolvido.
CAPÍTULO 1. INTRODUÇÃO
10
1.4 Contribuições
A aplicação do trabalho efectuado no âmbito desta tese poderá vir a ser marcante, tendo em
conta o desenvolvimento dos meios de comunicação e o aumento significativo da quantidade de
informação em suporte digital. O processamento corpora deste tipo, implica a utilizaç ão ferramentas orientadas para o processamento de textos reais, domı́nio para o qual esta tese se encontra
especialmente orientada.
O processamento da lı́ngua portuguesa é também um aspecto a realçar. Sobre este ponto é
importante destacar as necessidades especı́ficas e os fenómenos linguı́sticos particulares aı́ presentes. A lı́ngua portuguesa juntamente com as suas variantes é uma das lı́nguas mais utilizadas no
mundo, com cerca de 182 milhões de falantes3 merecendo por isso especial atenção.
Esta tese proporciona uma ferramenta computacional para o processamento da lı́ngua portuguesa, que poderá constituir uma plataforma de investigação nesse domı́nio.
1.5 Estrutura da dissertação
O capı́tulo 2 situa o trabalho efectuado no âmbito desta tese, face aos formalismos e métodos
utilizados no contexto da análise sintáctica e em particular da análise sintáctica de superfı́cie.
Aborda as gramáticas como mecanismos formais utilizados para descrever a estrutura de uma
lı́ngua e apresenta as aproximações utilizadas no tratamento da lı́ngua natural ao nı́vel sintáctico.
O capı́tulo descreve alguns dos sistemas existentes, orientados para o tratamento de textos reais
e termina com um quadro resumo, onde se estabelece uma comparação entre os vários sistemas
descritos.
O capı́tulo 3 foca os detalhes da análise por folhas, tal como foi introduzida e realizada no
âmbito dos trabalhos de Hagège (2000). A primeira parte do capı́tulo foca a gramática utilizada na
análise por folhas, descrevendo os seus elementos. A segunda parte do capı́tulo descreve o protótipo
de análise por folhas AF, caracterizando o tipo de análise que executa e destacando casos de tratamento particular. A parte final do capı́tulo descreve o processo de extracção de sintagmas nominais
a partir de texto, partindo de elementos mais fáceis de descrever, designados por sintagmas nucleares. Apresentam-se resultados sobre a avaliação deste processo.
O capı́tulo 4 descreve a gramática que serve de fonte de dados para o algoritmo de análise
sintáctica de superfı́cie do SuSAna, apresentado no capı́tulo 5. Sendo derivada da estrutura da
gramática utilizada pelo AF, mostram-se as alterações efectuadas e descreve-se a sua sintaxe
e semântica. Este capı́tulo estabelece também a relação entre os elementos que constituem a
gramática e a informação utilizada em gramáticas de outros formalismos.
O módulo de análise sintáctica de superfı́cie concebido e implementado no âmbito desta tese
– SuSAna – é apresentado no capı́tulo 5. O capı́tulo aborda aspectos relativos à sua utilização,
integração noutros sistemas e em diferentes plataformas, tanto localmente como numa plataforma
cliente/servidor. Descrevem-se aspectos relativos ao seu funcionamento, em particular os formatos
3 Fonte
de informação: http://www.historiageral.hpg.ig.com.br/quadro 2/artigos/linguas faladas.htm
1.5. ESTRUTURA DA DISSERTAÇÃO
11
utilizados na representação de dados e o tipo de dados que processa. O capı́tulo descreve a arquitectura interna do SuSAna e a representação interna da informação. A secção 5.4 descreve o processo
de análise, mecanismos de restrição e os algoritmos utilizados, apresentando também uma análise
de complexidade relativa a esses algoritmos. A secção 5.5 aborda os aspectos relativos à extracção
de informação sobre segmentos previamente analisados, e finalmente descreve o contexto actual de
utilização do módulo.
O capı́tulo 6 apresenta a avaliação do sistema, incluindo testes de comparação entre o AF e o
SuSAna, considerando: facilidade de utilização; tolerância a falhas; e fiabilidade dos resultados. A
segunda parte do capı́tulo mostra os resultados da aplicação do SuSAna a corpus alargado.
O capı́tulo 7 apresenta as conclusões e o trabalho futuro, no contexto do qual se faz um balanço
relativamente ao trabalho realizado e se descrevem algumas extensões a este trabalho, que se pretendem realizar ou poderiam ser realizadas, de forma a torná-lo mais abrangente e útil.
12
CAPÍTULO 1. INTRODUÇÃO
A análise computacional da estrutura sintáctica de uma frase deve ter em consideração dois
aspectos importantes: a gramática, uma especificação formal das estruturas permitidas na lı́ngua;
e a técnica de análise ou método de análise, cujo propósito é determinar a estrutura da frase de
acordo com a gramática. Este capı́tulo apresenta alguns dos tipos de gramáticas e técnicas mais
utilizados na análise sintáctica e descreve alguns dos sistemas que utilizam esses recursos para o
processamento de textos não restritos.
A secção 2.1 apresenta os vários tipos de gramáticas utilizadas ao nı́vel sintáctico, no processamento da lı́ngua natural. A secção 2.2 apresenta algumas técnicas de análise sintáctica focando as
vantagens e os problemas a elas associados. Descrevem-se alguns métodos eficientes utilizando, por
exemplo, estruturas de suporte à análise tais como autómatos e mecanismos tais como programação
dinâmica, que oferecem geralmente elevados nı́veis de eficiência. A secção 2.3 descreve alguns analisadores sintácticos de superfı́cie, apresentando para cada um deles, os pontos fortes e fracos. Finalmente, a secção 2.4 apresenta algumas conclusões e linhas de orientação para o trabalho desta
tese.
2.1 As gramáticas
As gramáticas são mecanismos formais utilizados para descrever a estrutura de uma lı́ngua.
Segundo Jurafsky e Martin (2000), estas podem ser caracterizadas pelo seu poder generativo, calculado com base no conjunto de linguagens que cada formalismo consegue descrever. Uma gram ática
tem um maior poder generativo ou complexidade do que outra, se puder definir uma linguagem
que a outra não possa definir. Nenhuma linguagem natural pode ser precisamente caracterizada
de forma a definir a sua capacidade generativa, por oposição às linguagens formais que permitem
uma caracterização matemática precisa. O trabalho na teoria das linguagens formais iniciou-se
com Chomsky (1956), que definiu uma hierarquia de linguagens, à qual se chama Hierarquia de
Chomsky. A Hierarquia de Chomsky revela que as linguagens geradas por gramáticas regulares
são um subconjunto das linguagens geradas pelas gramáticas livres de contexto (CFG), que por sua
vez são um subconjunto das linguagens sensı́veis ao contexto, que por sua vez são um subconjunto
das linguagens do tipo 0.
Esta secção descreve alguns dos tipos de gramáticas mais conhecidos e utilizados no processamento de lı́ngua natural, em particular as gramáticas regulares, livres de contexto, sensı́veis
ao contexto, dentro das quais se incluem as gramáticas moderadamente sensı́veis ao contexto. A
secção termina com uma abordagem à unificação.
CAPÍTULO 2. ENQUADRAMENTO
14
2.1.1
Gramáticas regulares
Os sı́mbolos que se usam numa linguagem dividem-se normalmente em duas classes: sı́mbolos
terminais que correspondem a palavras na linguagem; e sı́mbolos não terminais que correspondem
a agrupamentos ou generalizações dos sı́mbolos terminais. Uma gramática regular é constituı́da
por regras, tais que o lado direito de cada regra consiste num sı́mbolo terminal seguido de um
sı́mbolo não terminal.
A aplicação das gramáticas regulares ao processamento sintáctico de lı́ngua natural, é bastante
simples, pois permitem um fácil reconhecimento, porém, apresentam um poder generativo limitado,
equivalente ao poder expressivo de um autómato finito.
2.1.2
Gramáticas livres de contexto (CFG)
As gramáticas livres de contexto, também conhecidas como gramáticas de estrutura sintagmática,1 são muito úteis no que respeita à descrição de gramáticas em lı́ngua natural. Sendo
o sistema matemático mais utilizado para modelar a estrutura constituinte de uma lı́ngua, são,
em geral, mais poderosas do que as gramáticas regulares, permitindo a representação de linguagens com estrutura mais complexa. A ideia de basear uma gramática na estrutura constituinte,2
remonta ao psicolinguista Wilhelm Wundt (1900), mas só foi formalizada por Chomsky (1956), e
mais tarde por Backus (1959), de forma independente. O formalismo utilizado é equivalente ao que
também se designa por BNF (Backus Naur Form).
Uma CFG é constituı́da por um conjunto de regras ou produções, cada uma delas expressando
de que forma os sı́mbolos da linguagem podem ser agrupados e ordenados, e por um léxico de palavras e sı́mbolos. A linguagem formal definida por uma CFG é o conjunto de sequências que se
podem derivar de um sı́mbolo inicial, ou sı́mbolo de topo.
Um dos maiores problemas em utilizar as CFGs, está na dificuldade em exprimir dependências
simples, como por exemplo, concordância entre verbo e sintagma nominal. As abordagens puramente baseadas em CFGs não são geralmente suficientemente poderosas para captar a descrição
adequada à lı́ngua natural. Podem, contudo, usar-se linguagens formais, tais como DCG (Definite
Clause Grammars), disponı́vel em Prolog, para definir gramáticas livres de contexto de forma a
realizar a análise (Allen, 1995).
2.1.3
Gramáticas sensı́veis ao contexto
Grande parte dos problemas de dependência associados às CFGs, são resolvidos pelas
gramáticas sensı́veis aos contexto. Contudo, esta classe de gramáticas não aborda satisfatoriamente
o tratamento de restrições gramaticais. O problema relativo à sua utilização reside fundamentalmente na tarefa de reconhecimento, pois o processo de verificar se a estrutura de uma frase pode
ser obtida por estas gramáticas, é numa função exponencial sobre o tamanho da frase, tornando a
sua implementação uma questão dispendiosa do ponto de vista computacional.
1 Do
inglês phrase-structure.
na palavra constituinte no sentido de “componente da estrutura de uma frase”.
2 Usa-se
2.1. AS GRAMÁTICAS
15
Gramáticas moderadamente sensı́veis ao contexto
A definição de uma linguagem formal como um conjunto de sequências de palavras sugere que
se possa verificar a equivalência de duas gramáticas, simplesmente verificando se os conjuntos de
sequências que se podem gerar em cada uma delas são iguais. De uma forma geral, distinguemse dois tipos de equivalência entre gramáticas: fortemente e fracamente equivalentes. As
gramáticas fortemente equivalentes geram o mesmo conjunto de sequências e atribuem a mesma
estrutura a cada frase. As gramáticas fracamente equivalentes, são gramáticas que geram o mesmo
conjunto de sequências na linguagem mas não atribuem a mesma estrutura a cada frase.
Entre os formalismos que se introduziram nos últimos anos, existe uma classe de gramáticas
designada por gramáticas moderadamente sensı́veis ao contexto (mildly context-sensitive grammars)
que foram e têm sido intensamente investigadas sobre o ponto de vista matemático. Em particular, foi demonstrado que os formalismos pertencentes a esta classe são fracamente equivalentes
(Cole et al., 1995). A secção 2.2.5 abordará as técnicas utilizadas no tratamento desta classe de
gramáticas.
Como exemplos de gramáticas fracamente equivalentes temos, TAG (Tree-Adjoing Grammars),
CCG (Combinatorial Categorial Grammars), LIG (Linear Indexed Grammars), e HG (Head Grammars). Embora estas gramáticas sejam fracamente equivalentes e para elas tenham sido desenvolvidas técnicas de análise uniformes, as noções do que constitui uma análise são diferentes em cada
uma delas.
Numa TAG, a análise de uma frase constitui a chamada árvore de derivação, que consiste num
registo de como as árvores elementares de uma TAG se juntam pelas operações de substituição
e de junção de forma a obter a árvore derivada cujo resultado é a análise de uma sequência. Os
nós da árvore de derivação são etiquetados com os nomes das árvores elementares e os arcos são
etiquetados pelo endereço da árvore que etiqueta o nó superior, no qual as árvores que etiquetam os
nós filhos são ou substituı́das ou agrupadas. Enquanto numa árvore de derivação para uma CFG,
as noções de árvore de derivação e árvore derivada são as mesmas, para as TAG essas noções são
distintas.
Nas HG, a noção de árvore de derivação é diferente da anterior. Existe apenas a noção de
árvore de derivação, que é apenas um registo de como as sequências elementares (headed strings)
se relacionam e quais as operações usadas nesse processo. Os nós terminais são etiquetados pelas
operações que foram utilizadas para combinar as sequências usadas para etiquetar os nós filhos e
também pela sequência resultante da execução dessa operação. Assim, esta árvore de derivação é
muito diferente da árvore de estructura de sintagmas.
Para as CCG, a análise de uma frase é a árvore de prova da derivação. É semelhante à árvore de
estrutura de sintagmas, no sentido em que os nós são etiquetados por categorias em CCG. Contudo,
o nome da operação usada ao fazer a redução para cada nó tem também de ser indicado no nó. Neste
aspecto, são semelhantes às HG.
2.1.4
Gramáticas tipo 0
A Hierarquia de Chomsky classifica como sendo Gramáticas do Tipo 0, ou gramáticas com
Estrutura de Frase, as gramáticas às quais nenhuma limitação é imposta. Todo o universo das
CAPÍTULO 2. ENQUADRAMENTO
16
linguagens, que se pode definir através dos mecanismos generativos das gramáticas, corresponde
ao conjunto das linguagens que esta classe de gramáticas é capaz de gerar. As linguagens que
podem ser geradas por alguma gramática do tipo 0, designam-se linguagens do tipo 0.
2.1.5
Gramáticas baseadas em formalismos de unificação
A unificação é uma forma de implementar a integração de conhecimento a partir de restrições
diferentes. Para duas entradas de estruturas de caracterı́sticas (features) compatı́veis, a unificação
produz uma estrutura mais geral, que contém toda a informação das entradas. No caso das estruturas serem incompatı́veis, a unificação não pode ser aplicada (Jurafsky e Martin, 2000). Quase todas
as gramáticas computacionais incorporam estruturas de caracterı́sticas (estruturas atributo-valor).
Essas estruturas são manipuladas pela operação de unificação, daı́ o termo gramáticas baseadas
em unificação. Embora grande parte das gramáticas possam servir de suporte para gramáticas
baseadas em unificação, Shieber (1986) refere que as CFGs são as mais utilizadas para este fim.
As estruturas de caracterı́sticas e a unificação, fornecem uma forma elegante de exprimir restrições
sintácticas que seriam difı́ceis de exprimir usando apenas os mecanismos das CFGs, por exemplo.
Assim que se introduzem estruturas de caracterı́sticas e unificação, as gramáticas resultantes deixam de ser analisáveis em tempo polinomial. Na prática, podem ser introduzidas condições nas
possı́veis estruturas de caracterı́sticas que permitem voltar a conseguir a complexidade polinomial
(Cole et al., 1995). Uma importante propriedade das gramáticas baseadas na unificação é o facto de
se poder codificar a recursividade nas estruturas de caracterı́sticas (Cole et al., 1995).
2.2 Técnicas de análise sintáctica
Esta secção apresenta alguns dos vários algoritmos existentes para associar uma árvore de
estrutura sintagmática a uma frase. Os métodos empregues variam desde as estratégias básicas de
procura até à programação dinâmica. Para gramáticas livres de contexto, os algoritmos de Earley
(1970), Cocke-Younger-Kasami (CYK) (Kasami, 1965; Younger, 1966) e Graham-Harrison-Ruzzo
(GHR) (Graham et al., 1980), são exemplos de programação dinâmica com complexidade muito
reduzida.
2.2.1
Estratégias básicas
O objectivo de uma análise sintáctica consiste em encontrar todas as árvores de estrutura sintagmática, a partir de um sı́mbolo de partida T, que contemplem as palavras da frase e analisar.
Independentemente do algoritmo de procura, é sempre necessário respeitar dois tipos de restrições:
o primeiro provém dos dados; o segundo, provém da gramática. A árvore final deve conter uma
raiz que começa com o sı́mbolo T, e um conjunto de folhas que devem corresponder às palavras da
frase. Estes dois tipos de restrições levam a dois tipos de estratégias de procura, presentes em muitos analisadores, nomeadamente: a estratégia de procura descendente (top-down) e a estratégia de
procura ascendente (bottom-up) ou procura orientada pelos dados.
Um analisador top-down procura construir uma árvore, partindo do nó raiz em direcção às suas
folhas. O algoritmo começa por assumir que a entrada pode ser derivada a partir do sı́mbolo inicial,
2.2. TÉCNICAS DE ANÁLISE SINTÁCTICA
17
e o passo seguinte consiste em encontrar os nós de topo de todas as árvores que podem começar
com T, encontrando todas as regras da gramática com T no seu lado esquerdo. Em cada nı́vel da
análise, usam-se os lados direitos das regras para fornecer novos conjuntos de possibilidades para o
analisador, que por sua vez são usadas recursivamente para gerar as restantes árvores. As árvores
vão crescendo até chegarem a uma das categorias da frase de entrada. Neste ponto, as árvores cujas
folhas não se identificam com todas as palavras da frase são rejeitadas.
O algoritmo de análise bottom-up é o mais simples algoritmo de análise sintáctica conhecido
(Jurafsky e Martin, 2000). Foi sugerido pela primeira vez por Yngve (1955) e é muitas vezes utilizado em analisadores de Deslocamento e Redução (shift-reduce), habitualmente utilizados para
linguagens computacionais. Na análise do tipo bottom-up, o analisador começa com as palavras que
compõem a frase em análise e tenta construir a árvore da análise até ao nó de topo. O analisador
é bem sucedido se conseguir gerar a árvore com o sı́mbolo T na raiz e cobrir todas as palavras da
frase.
As estratégias top-down e bottom-up têm ambas vantagens e desvantagens. A primeira nunca
explora árvores que não podem ocorrer em T, uma vez que começa por gerar apenas as árvores que
podem ocorrer em T. Por oposição, a estratégia bottom-up gera árvores que não levam a T e podem
vir a ser eliminadas. Embora a estratégia top-down não construa árvores que não levam a T, pode
construir árvores que não são consistentes com os dados de entrada. As deficiências da aproximação
top-down resultam de serem geradas árvores antes de se terem examinado os dados de entrada. Por
seu lado, a estratégia bottom-up nunca sugere árvores que não provenham dos dados de entrada.
Mesmo dotado de estratégias como a filtragem bottom-up, o analisador top-down apresenta um
conjunto de problemas que o tornam uma solução ineficiente para o problema da análise. Esses
problemas são a recursão à esquerda, ambiguidade e análise repetida de sub-árvores.
O problema da recursão à esquerda manifesta-se no uso de gramáticas recursivas à esquerda,
em analisadores top-down esquerda-direita de procura em profundidade. Em termos formais,
uma gramática diz-se recursiva à esquerda se contém pelo menos um sı́mbolo não terminal A,
tal que
, para algum e e
. O sı́mbolo A pode levar o analisador a uma
expansão infinita da árvore;
O tratamento da ambiguidade é feito de uma forma ineficiente quando utilizado um analisador
top-down. Além da ambiguidade ao nı́vel da classificação morfossintáctica, existe também
outro tipo de ambiguidade que provém das estruturas sintácticas usadas na análise que se
designa por ambiguidade estrutural. Este tipo de ambiguidade ocorre quando a gramática
permite mais do que uma análise para uma dada frase;
O analisador constrói por vezes porções válidas de árvores, que são desprezadas devido a retrocesso (backtracking) e possivelmente reconstruı́das. Este processo é claramente ineficiente.
Note-se que embora este problema seja especı́fico da análise top-down, ocorrem problemas
similares nos analisadores bottom-up.
2.2.2
Análise Esquerda-Direita (LR)
Os algoritmos de análise Esquerda-Direita (Aho e Ullman, 1972) foram introduzidos inicialmente para as linguagens de programação e revelou-se útil para construção de compiladores. O
18
CAPÍTULO 2. ENQUADRAMENTO
algoritmo LR é um dos algoritmos de análise sintáctica mais eficientes, totalmente determinista,
que não usa retrocesso. Contudo, não se pode utilizar directamente às lı́nguas naturais, pois é apenas aplicável a um pequeno sub-conjunto das CFGs, designado por gramáticas LR (Tomita, 1987).
Os analisadores LR processam a sua entrada usando uma estratégia bottom-up, da esquerda
para a direita e devolvendo a derivação mais à direita possı́vel. Este tipo de analisadores são conduzidos por uma tabela de acções para a análise que foi previamente compilada a partir da gramática.
Nas gramáticas orientadas para os analisadores LR, as tabelas de análise compiladas são deterministas, resultando em analisadores eficientes, com tempos de execução lineares. Estes analisadores
seguem diversas variantes: o núcleo comum de todos eles é um analisador com Deslocamento e
Redução (Shift-Reduce), que não é mais do que um autómato de estados finitos pushdown (PDA). O
analisador lê uma dada entrada da esquerda para a direita, palavra a palavra. Em cada passo, o
analisador pode deslocar a próxima palavra para a sua pilha, reduzir a pilha actual de acordo com
uma regra da gramática, ou aceitar/rejeitar a entrada. Uma tabela de acções pré-compilada a partir
da gramática guia o processo de análise das entradas. A tabela especifica a próxima acção que o
analisador deve tomar como uma função do estado actual e da próxima palavra a analisar (Lavie,
1996). Tal como o analisador de Earley, a análise LR usa items para saber qual foi o progresso das
derivações enquanto é processada a entrada. O analisador de Earley constrói todo o conjunto de
possı́veis items no momento, seguindo todas as derivações parciais. Um analisador LR, tem acesso
a uma lista completa de conjuntos de possı́veis items calculados previamente, limitando-se a seguir as transições entre esses conjuntos. Os conjuntos de items são conhecidos como “estados” do
analisador LR. Uma gramática é adequada para a análise LR se as transições puderem ser executadas deterministicamente, considerando-se apenas o próximo elemento da entrada e os conteúdos
de uma pilha Deslocamento e Redução.
O algoritmo LR generalizado é uma extensão do algoritmo LR, que permite tracking paralelo
e transições de estados múltiplos e acções de pilha usando uma pilha do tipo grafo estruturado
(Stolcke, 1995). Tomita (1987) apresenta um algoritmo LR generalizado eficiente para CFGs aumentadas, que permite o processamento de qualquer gramática CFG, com base numa pilha do tipo
grafo estruturado.
2.2.3
Análise com transdutores de estados finitos
Os dispositivos de estados finitos sempre tiveram um papel chave no processamento da lı́ngua
natural. O seu interesse é renovado devido ao seu bem sucedido uso na análise morfológica, ao
representar, por um lado, grandes dicionários com autómatos de estados finitos (FSA) e, por outro,
regras de dois nı́veis e informação lexical com transdutores de estados finitos (FST). Os FSA foram
já usados, tanto para aproximar CFGs, como para realizar analise sintáctica. O maior problema
inerente ao uso dos FSA está na dificuldade de representar a estrutura hierárquica, podendo originar análises incompletas. Nos últimos anos, tem havido algum trabalho teórico em autómatos
de estados finitos no que diz respeito ao seu uso em análise sintáctica. Os analisadores podem ser
muito eficientes e são adequados para gramáticas muito lexicalizadas.
2.2. TÉCNICAS DE ANÁLISE SINTÁCTICA
2.2.4
19
Algoritmos eficientes de análise sintáctica
Para as gramáticas livres de contexto, são conhecidos algoritmos de complexidade polinomial,
tais como o algoritmo CKY, de Cocke, Kasami e Younger (1965, 1967), e o de Earley (1970). Todos os
algoritmos que operam com as CFGs estão relacionados com estes dois de alguma forma. No que diz
respeito à complexidade, esses algoritmos são
, sendo o tamanho da frase. Existe um factor
multiplicativo
, que depende do tamanho da gramática , expresso em termos de regras e
do número de sı́mbolos não terminais. Embora se tenham introduzido optimizações aos expoentes
de e , elas estabelecem análises polinomiais. Não existem casos matemáticos de complexidade
média: todos os que são anunciados são empı́ricos. Na prática, a generalidade dos algoritmos são
executados em tempos muito inferiores ao pior caso e o factor real de limitaç ão é o tamanho da
gramática (Cole et al., 1995).
2.2.5
Análise em gramáticas moderadamente sensı́veis ao contexto
Os formalismos pertencentes à classe das gramáticas moderadamente sensı́veis ao contexto, já
abordados na secção 2.1.3, são fracamente equivalentes. Do ponto de vista da análise sintáctica,
a fraca equivalência não é por si só muito interessante, pois sozinha não pode garantir que uma
técnica de análise desenvolvida para uma classe de gramáticas possa ser estendida para ser usada
noutra classe, ou que um procedimento uniforme possa ser desenvolvido para tratar esse conjunto de gramáticas. Contudo, é sempre possı́vel adaptar um algoritmo que funcione com uma
das gramáticas desse conjunto a qualquer outra gramática deste conjunto.
Segundo Joshi Aravind (Cole et al., 1995), foi mostrado que é possı́vel estender o algoritmo
CKY (algoritmo de reconhecimento de CFGs) para analisar LIGs (gramáticas lineares indexadas).
Consequentemente, este analisador pode também ser adaptado à analise gramáticas do tipo TAG
(Tree-Adjoing Grammars), HG (Head Grammars) e CCG (Combinatorial Categorial Grammars).
. Um algoritmo do tipo do de Earley
O novo algoritmo é polinomial e a sua complexidade é
também foi desenvolvido para as gramáticas TAG e foi mostrado que a sua complexidade é
(Cole et al., 1995).
2.2.6
Análise sintáctica como processo dedutivo
A operação de análise pode ser vista como um processo dedutivo, tal como no caso das CCG. O
cálculo de Lambek é uma formulação bastante antiga da análise como dedução. A relação entre o
cálculo de Lambek e as CFG foi uma questão em aberto durante mais de 30 anos. Recentemente
foi provado que as Gramáticas de Lambek são fracamente equivalentes às CFGs (Pentus, 1993).
A demonstração desta equivalência não parece, no entanto, sugerir a construção de um algoritmo
polinomial de análise para as gramáticas de Lambek, o que mantém uma importante questão em
aberto. A plataforma da análise como dedução permite uma separação modular dos aspectos lógicos
da gramática e a demonstração do procedimento de procura, fornecendo uma plataforma para a
investigação de uma gama maior de algoritmos de análise. Estas investigações teóricas levaram
ao desenvolvimento de um programa para o teste rápido de novos algoritmos de análise e foram
também usadas para o desenvolvimento de algoritmos para as gramáticas CCG, TAG e CFG (Shieber et al., 1995).
CAPÍTULO 2. ENQUADRAMENTO
20
2.2.7
Análise com preferências
A ambiguidade é um problema persistente no processamento da lı́ngua natural, pois geralmente, as gramáticas associam mais do que uma estrutura às frases e existe usualmente mais do
que uma forma de exprimir a sua estrutura (Strzalkowski, 1994). Assim, os sistemas de an álise devem decidir as estruturas correctas de entre múltiplas possibilidades. As heurı́sticas usadas para
realizar essas escolhas são designadas por preferências, que podem ser vistas como funções que
comparam pares de estruturas indicando qual a que se prefere.
São vários os tipos de preferências que se podem considerar, por exemplo: preferências derivadas de princı́pios psicolinguı́sticos e preferências indicadas por regras que definem a preferência
de uma estrutura sobre outra. Neste último caso, as regras podem ser indicadas manualmente
ou derivadas de métodos probabilı́sticos baseados na frequência em corpus. A forma mais fácil de
considerar preferências é executar o algoritmo de análise, obter os seus resultados e ordená-los de
acordo com pesos atribuı́dos previamente pelas preferências consideradas. Este processo conduz a
um resultado correcto, mas é potencialmente ineficiente, dado que todas as interpretações têm de
ser criadas antes que possam ser ordenadas.
James Barnett (Strzalkowski, 1994) apresenta uma plataforma para lidar com a ambiguidade.
No seu trabalho, Barnett examina várias propriedades que as preferências devem possuir, de forma
a produzir pesos coerentes, e apresenta um algoritmo para aplicar essas prefer ências durante a
análise. A plataforma de Barnett agrupa as preferências em várias classes de equivalência, com diferentes nı́veis de complexidade de aplicação. Esta plataforma, na sua versão mais simples, permite
implementar preferências simples como é o caso de Low Attachement e Function Composition. Preferências mais complexas, como é o caso da resolução de anáforas, são contempladas numa extensão
que Barnett faz à sua plataforma, na qual explora parcialmente o espaço de procura. A plataforma
de Barnett assume uma representação baseada em DAGs (grafos dirigidos acı́clicos) sendo assim
independente de uma teoria em particular.
Petitepierre et al. (1987) apresentam um tratamento semelhante a Barnett, considerando as
preferências como predicados que comparam pares de interpretações. Segundo Barnett, este trabalho não tem em consideração as questões de comensurabilidade e monotonicidade, o que leva
a uma incapacidade de garantir a coerência do resultado.3 Barnett acrescenta que este trabalho
não permite aplicar preferências incrementalmente obrigando à construção do conjunto de todas as
possı́veis interpretações.
2.3 Analisadores orientados para texto não restrito
Os sistemas de análise sintáctica trabalham, normalmente, com base em etiquetagem morfológica desambiguada ou não. Os analisadores sintácticos tradicionais, onde também se incluem
os analisadores estocásticos simples, procuram obter análises completas e exactas. Como resultado
disso, não se comportam bem quando aplicados a textos reais. Este tipo de textos cont ém por vezes
uma grande quantidade e variedade de ruı́do, que associado a possı́veis erros e à inexistência de
gramáticas e léxicos que cubram todos os domı́nios, tornam difı́cil a sua análise. Por outro lado,
3A
ordenação pode incluir incoerências nas quais x ¡ y e y ¡ x.
2.3. ANALISADORES ORIENTADOS PARA TEXTO NÃO RESTRITO
21
devido ao tamanho das frases e à ambiguidade das gramáticas, é também difı́cil fazer uma análise
eficiente. Os analisadores sintácticos de superfı́cie, também conhecidos como shallow parsers são
uma resposta a estas dificuldades. Embora produzam análises menos completas e profundas do que
aquelas produzidas por um analisador convencional, têm como objectivo obter informação sintáctica
válida, mesmo que seja parcial. Geralmente fazem-no de uma forma eficiente.
Uma das caracterı́sticas comuns a uma grande parte de analisadores de superfı́cie é a sua
aplicação a grandes quantidades de corpora. Muitas vezes, sempre que não é possı́vel atribuir uma
estrutura válida à frase, permite-se a análise parcial. O propósito da análise parcial consiste em
inferir a maior estrutura sintáctica possı́vel, a partir da informação morfossintáctica. A análise
de superfı́cie pode ser utilizada para diversas finalidades, tais como detectar frases ou identificar
alguns constituintes da frase, tais como frases nominais, sem indicar a sua estrutura interna e as
suas funções na frase. Outro tipo de análise de superfı́cie consiste em identificar o papel funcional
de algumas palavras, tal como o verbo principal e os seus argumentos directos.
Embora já se faça investigação na área há três décadas, segundo Cole et al. (1995) não teria
sido desenvolvido até 1995 nenhum analisador independente do domı́nio, para texto não restrito,
de carácter prático. Nos recentes anos este panorama é posto em causa devido, fundamentalmente:
a um aumento de poder de cálculo computacional, que permite testar e analisar diferentes técnicas
de cálculo; e à crescente facilidade de acesso a corpora, que permite realizar observações e produzir
informação valiosa para o processamento da lı́ngua.
2.3.1
Analisador de superfı́cie da Xerox
O analisador de superfı́cie desenvolvido na Xerox consiste numa cascata de autómatos de estados finitos. A utilização da tecnologia de estados finitos na Xerox, tem como objectivo fornecer uma
plataforma de trabalho para o desenvolvimento de ferramentas de tratamento linguı́stico. O objectivo da sintaxe dos estados finitos é expandir a tecnologia dos estados finitos ao nı́vel dos sintagmas
e das frases. Pretendem desenvolver um sistema que desambigue categorias gramaticais e associe
funções sintácticas assim como tratar documentos reais (Schulze et al., 1994).
Partindo de um texto etiquetado e desambiguado, este analisador aplica uma série de transdutores compilados a partir de expressões regulares, que vão permitir adicionar informação sintáctica
às sequências iniciais do texto etiquetado. Cada transdutor é responsável por uma dada tarefa
linguı́stica e ao resultado da aplicação de cada transdutor é aplicado outro transdutor. As duas
operações principais efectuadas pelos transdutores são a segmentação e a marcação sintáctica.
A segmentação consiste em delimitar e etiquetar as sequências de constituintes adjacentes.
Estas sequências correspondem a sintagmas minimais, chunks, ou sintagmas não recursivos, que
se encontram em alguns dos trabalhos mais recentes (Giguet, 1998; Abney, 1991, 1996; Ejerhed,
1996). Consideram-se igualmente no seguimento deste trabalho, unidades sintácticas semelhantes,
designadas por sintagmas nucleares.
A marcação sintáctica consiste em atribuir as funções sintácticas aos segmentos não recursivos.
A técnica para obter as funções sintácticas dos domı́nios sintácticos delimitados é semelhante à utilizada no analisador por restrições de Helsı́nquia (ver 2.3.3). Uma das vantagens deste analisador,
segundo os seus autores, é a sua não-monotonicidade.
CAPÍTULO 2. ENQUADRAMENTO
22
Depois de efectuada a etiquetagem, um conjunto suplementar de transdutores, aplicados às
sequências segmentadas e marcadas, tenta ligar os segmentos delimitados entre si (ligaç ões entre
governadores e dependências). Estas ligações não se estabelecem entre unidades lexicais (como
no caso dos formalismos baseados nas dependências) mas entre segmentos. Por exemplo entre os
segmentos marcados como objecto, queremos determinar de que verbo esse segmento é objecto. Esta
marcação sintáctica preliminar é um meio de limitar a sobre-geração de ligações de dependência.
Este analisador de superfı́cie foi inicialmente desenvolvido para o francês, existindo já uma
versão do analisador para o espanhol, que segundo Pavia (1999), chega a conseguir processar cerca
de 115 palavras por segundo4, incluindo o pré-processamento. Testes efectuados em corpora jornalı́stico, para identificar o sujeito do verbo e o seu objecto directo, revelam uma precis ão entre 70%
e 80% e uma cobertura entre 60% e 75% (Pavia, 1999).
2.3.2
Analisador GREYC
O analisador GREYC, desenvolvido por Jacques Vergne do laboratório CREYC, efectua uma
análise de superfı́cie baseada em dependências (Vergne e Giguet, 1988). Este analisador participou
na acção de avaliação comparativa de etiquetadores GRACE, obtendo uma cobertura de 100% e
cerca de 95% de precisão, ficando em primeiro lugar (LIMSI, 2002).
Definem-se dois nı́veis de tratamento que são o nı́vel de tratamento de palavras e o nı́vel de
tratamento de sintagmas não recursivos. Entre estes dois nı́veis existe uma interacção que vai
permitir, num outro nı́vel, afinar as decisões tomadas. Esta maneira de decompor o problema,
faz da delimitação de sintagmas não recursivos uma extensão da etiquetagem. As operações de
desambiguação morfológica e de parentetização sintáctica, efectuam-se numa única etapa.
Além das etiquetas consideradas existe outro tipo de etiquetas que marcam o inı́cio e o fim dos
sintagmas não recursivos. A etiquetagem faz-se em duas etapas: numa primeira etapa calculam-se
as etiquetas mais prováveis para as palavras gramaticais do texto; a segunda etapa designada fase
de dedução, consiste em rever ou confirmar a primeira etiquetagem, usando as regras contextuais.
A etiquetagem do inı́cio e fim dos sintagmas não recursivos são calculadas neste primeiro nı́vel de
tratamento.
O segundo nı́vel de tratamento diz respeito ao estabelecimento de dependências entre sintagmas não recursivos. Estas dependências são calculadas, não só, a partir de conhecimento estático,
mas também dinâmico, a partir de outras ligações de dependência que se estabelecem entre outros
sintagmas não recursivos da sequência. Embora cada um dos nı́veis constitua um processo separado, as duas representações são construı́das em simultâneo, cada uma podendo interagir com a
outra. Com efeito, algumas ambiguidades deixadas no 1o nı́vel só podem ser resolvidas no segundo
nı́vel.
2.3.3
Os analisadores da universidade de Helsı́nquia
Os dois analisadores reducionistas da universidade de Helsı́nquia, ENGCC e Functional Dependency Parser, são analisadores robustos e baseiam-se em obter todas as construções possı́veis,
4 Testes
realizados numa máquina SPARCstation-10.
2.3. ANALISADORES ORIENTADOS PARA TEXTO NÃO RESTRITO
23
para numa segunda etapa, através de restrições, eliminar as improváveis.
O analisador de gramática de restrições para o Inglês, ENGCG (Voutilainen et al., 1992; Karlsson et al., 1995) é baseado numa gramática de restrições, que consiste numa plataforma de trabalho
proposta por Fred Karlsson. Desenvolvido entre 1989 e 1993 na universidade de Helsı́nquia, por
Atro Voutilainen, Juha Heikkilä e Arto Anttila, foi mais tarde melhorado no que diz respeito à
sua descrição sintáctica, e Pasi Tapanainen escreveu uma nova e mais eficiente implementação do
algoritmo de análise por restrições.
A componente de análise morfológica e lexical é baseada num modelo de dois nı́veis (Koskenniemi, 1983). O léxico, além de empregar um conjunto de etiquetas morfológicas, emprega também
inflexão, derivação e até mesmo categoria sintáctica. Inicialmente, certas categorias podem ter uma
série de funções sintácticas, sobre as quais são aplicadas restrições contextuais não ordenadas, que
vão agir sobre essas sequências de unidades lexicais etiquetadas, a fim de desambiguar a etiquetagem morfológica e a função sintáctica. A desambiguação da função sintáctica de cada palavra é feita
da mesma forma que é feita a desambiguação morfossintáctica, aplicando regras de reconhecimento
de padrões para eliminar as etiquetas incorrectas.
O analisador Functional Dependency Parser, calcula, a partir de unidades lexicais etiquetadas
de forma não ambı́gua, as dependências entre essas unidades lexicais ao mesmo tempo que se
efectua a desambiguação de etiquetas de função sintáctica.
Depois da etiquetagem, o ENGCG determina um número limitado de funções sintácticas para
as palavras na frase desambiguada: sujeito; object finit verb; objecto de uma preposição, entre
outros. Depois de aplicar cerca de 250 restrições para resolução de ambiguidades sintácticas, cerca
de 75 a 85% de todas as palavras tornam-se sintacticamente não ambı́guas, conseguindo-se uma
taxa de erro entre 2 e 4.5%.
O analisador morfológico é baseado de autómatos de estados finitos e escrito em linguagem C
por Pasi Tapanainen. Segundo (Schulze et al., 1994) não trata fenómenos linguı́sticos mais profundos tais como ligações de frases proposicionais, subordinação e resolução de pronomes.
Para o português, existe um analisador robusto, na linha dos analisadores de Helsı́nquia, desenvolvido na Dinamarca que procede à desambiguação da etiquetagem morfossintáctica, etiquetagem em funções sintácticas e etiquetagem em classes semânticas (Bick, 1996).
2.3.4
Analisador Fidditch
Fiddich (Hindle, 1983, 1994) é um analisador de superfı́cie bastante antigo, sendo também o
mais bem sucedido em muitos aspectos. Foi originalmente concebido para tratar textos n ão restritos, incluindo textos com bastante ruı́do, como é o caso das transcrições de fala.
Sendo um analisador determinı́stico, toma decisões baseadas no estado do parser, sem retrocesso. O estado do analisador consiste numa pilha de constituintes incompletos e um buffer de tr ês
constituintes completos. As regras são seleccionadas por padrões que descrevem tais configurações,
e executa acções transformando o estado do parser.
Encontra-se em uso nos laboratórios AT&T e não se encontra disponı́vel para utilização. Fornecendo uma estrutura de superfı́cie anotada, especialmente árvores de estrutura sintagmática, foi
CAPÍTULO 2. ENQUADRAMENTO
24
aplicado a milhões de palavras (Cole et al., 1995). É um dos analisadores mais rápidos existentes,
chegando a processar cerca de 1200 palavras por segundo5 (Abney, 1996).
2.3.5
Sistema ANLT
O sistema ANLT (Alvey Natural Language Tools) (Ritchie et al., 1987; Grover et al., 1993),
resultado da fusão de três projectos das universidades de Cambridge, Edimburgo e Lancaster, é
um conjunto de ferramentas desenvolvidas para a investigação em processamento de lı́ngua natural. Estas ferramentas consistem num analisador morfológico, um analisador por grafo (chart
parser), gramática e um léxico derivado semi-automaticamente de um dicionário. A gramática, de
larga cobertura para o inglês, foi desenvolvida num meta-formalismo gramatical derivado do GPSG
(Generalized Phrase Structure Grammar), e lida tanto com análise sintáctica como com análise
semântica. Estas ferramentas podem ser usadas independentemente, ou integradas numa plataforma de desenvolvimento de gramáticas (Carroll et al., 1991).
O sistema permite implementar uma variedade de formalismos gramaticais, sendo a sua
aproximação baseada em unificação. As regras descrevem as estruturas dos sintagmas e frases
reconhecidas, podem ser estendidas por unificação de caracterı́sticas na parte esquerda e direita de
uma regra, permitindo impor restrições sobre as estruturas sintácticas criadas.
Em temos de cobertura, o sistema ANLT é mais uma ferramenta para teste de teorias gramaticais do que para exploração de corpora, no sentido em que é necessário encontrar uma estrutura
coerente para toda a frase, para que a análise sintáctica seja bem sucedida. É necessário efectuar a
criação de regras para a cobertura da lı́ngua a ser tratada, tendo em consideração que um conjunto
de regras de cobertura alargada, pode deixar a frase com milhares de analisadores.
2.3.6
Sistema PEG
PEG (Jensen et al., 1993) é um sistema de larga cobertura para análise lexical, morfológica e
sintáctica de texto em inglês não restrito (Cole et al., 1995). Fornece análises mesmo se nem toda a
informação necessária se encontra presente e utiliza regras para ordenar análises alternativas.
2.3.7
Analisador PALAVRAS
O PALAVRAS (Bick, 2000) é um analisador automático para português, desenvolvido por
Eckhard Bick na Universidade de Århus (Dinamarca). O sistema apoia-se num léxico de 50.000
lemas e milhares de regras gramaticais para fornecer uma análise completa, tanto morfológica
como sintáctica, de qualquer texto. O formalismo aplicado integra-se na tradição da Gramática por
Restrições (CG), introduzido por Fred Karlsson (Universidade de Helsı́nquia, Finlândia) em 1992.
Embora usando um conjunto de etiquetas gramaticais bastante diversificado, o parser alcança um
nı́vel de correcção de 99% em termos de morfologia, e 97-98% em termos de sintaxe.
5 Testes
realizados numa máquina: SUN Sparc 1
2.3. ANALISADORES ORIENTADOS PARA TEXTO NÃO RESTRITO
Xerox
Textos Reais
Robusto
Análises parciais
Larga cobertura
Sintágmas não recursivos
Refina os resultados
Autómatos finitos
Unificação
Restrições
Baseado em dependências
Determinista
Reducionista
Sem retrocesso
Texto desambiguado
Não-monotonicidade
GREYC
Helsı́nquia
Fiddich
25
ANLT
PEG
PALAVRAS
Tabela 2.1: Resumo das caracterı́sticas dos analisadores de superfı́cie.
Embora não tendo as caracterı́sticas de um analisador sintáctico de superfı́cie, este analisador
foi utilizado para a construção de um banco de árvores (treebank), no âmbito do projecto “Floresta
Sintá(c)tica” Afonso et al. (2002). O banco de árvores consiste num conjunto de items sintacticamente analisados, e encontra-se disponı́vel para utilização através da Internet.
2.3.8
Conclusões
A tabela 2.1 apresenta, um resumo das caracterı́sticas dos analisadores apresentados. Numa
óptica puramente aplicativa, os sistemas apresentam bons resultados, tendo em conta o estado da
arte deste domı́nio. Se, por um lado, o custo do trabalho linguı́stico é um parâmetro importante,
então muitos dos sistemas estatı́sticos6 são adequados, permitindo obter bons resultados de forma
automática. Se, por outro lado, se procuram generalizações sobre lı́nguas nas descrições linguı́sticas
nesses sistemas, então esses sistemas não são suficientes.
Pode-se lamentar a não visibilidade da informação linguı́stica utilizada nestes sistemas e talvez
o facto da informação linguı́stica não ser absolutamente declarativa:
Não visibilidade da informação linguı́stica: Os sistemas apresentados não permitem por vezes
estabelecer onde é declarada a informação linguı́stica e qual a sua natureza, transmitindo a
ideia de que se encontra distribuı́da por todo o sistema. Isto pode dever-se ao facto da sintaxe
das informações linguı́sticas declarativas não ser independente da sintaxe declarativa das
regras. Torna-se difı́cil examinar as gramáticas ou heurı́sticas utilizadas por esses sistemas e
por conseguinte é difı́cil chegar a generalizações sobre o funcionamento das lı́nguas.
Não declaratividade: A não declaratividade é um problema que se emparelha com a não visibilidade. Se os dados linguı́sticos usados por um sistema são declarativos a informação
linguı́stica utilizada deverá ser mais fácil de observar e apreender.
6 sistemas
que se baseiam em elementos probabilı́sticos obtidos a partir processamento de corpora.
CAPÍTULO 2. ENQUADRAMENTO
26
As descrições linguı́sticas detalhadas são dispendiosas, problema que se agrava se, para cada novo
sistema, for necessário criar uma nova descrição. Se for possı́vel criar descrições linguı́sticas detalhadas, independente de um formalismo e de um analisador, então essas descrições só têm de ser
feitas uma única vez. O trabalho a realizar no âmbito desta tese orienta-se para o tratamento de
texto real, considerando que a descrição de uma lı́ngua não deve ser dependente do algoritmo. Esta
é a razão fundamental pela qual o trabalho se distancia das abordagens das análises de superfı́cie
vistas anteriormente.
2.4 Sumário
A primeira parte do capı́tulo aborda os vários formalismos em que se enquadram as gramáticas
utilizadas no processamento de lı́ngua natural. As gramáticas, mecanismos formais utilizados para
descrever a estrutura de uma lı́ngua, podem ser caracterizadas pelo seu poder generativo, isto é,
a sua capacidade de gerar frases de uma linguagem. A escolha de um formalismo depende da expressividade e da complexidade de análise pretendida. As gramáticas regulares embora bastante
simples, apresentam um poder generativo limitado. Para as CFGs por seu lado, embora adequadas
ao tratamento computacional, não se chegou ainda a acordo acerca da possibilidade serem suficientes para descrever todas as possı́veis construções de uma lı́ngua (Jurafsky e Martin, 2000). Os
formalismos baseados em restrições podem modelar fenómenos mais complexos do que as CFGs. Em
particular, as estruturas caracterı́sticas e a unificação oferecem uma forma elegante de descrever
propriedades que seriam difı́ceis de representar usando os mecanismos das CFGs. As gramáticas
baseadas em unificação permitem codificar a recursividade nas estruturas de caracterı́sticas. Foi
demonstrado que os formalismos pertencentes à classe de gramáticas moderadamente sensı́veis
ao contexto, são fracamente equivalentes. As gramáticas TAG, CCG, LIG e HG são exemplos de
gramáticas fracamente equivalentes.
A segunda parte deste capı́tulo aborda as aproximações utilizadas no tratamento da lı́ngua
natural ao nı́vel sintáctico. Para as gramáticas livres de contexto, são conhecidos algoritmos de
complexidade polinomial, tais como o algoritmo CKY de Cocke, Kasami e Younger (1965, 1967) e
o de Earley (1970). Todos os algoritmos que operam com as CFGs estão relacionados com estes
dois de alguma forma. No que diz respeito à complexidade, esses algoritmos são
, sendo o
tamanho da frase, existindo um factor multiplicativo
, que depende do tamanho da gramática
, expresso em termos de regras e do número de sı́mbolos não terminais. Conclui-se que a análise
sintáctica de lı́ngua natural, especialmente a lı́ngua escrita, embora também a falada, pode ser
tratada por aproximações relativamente simples.
A última parte do capı́tulo descreve alguns analisadores desenvolvidos e orientados para o processamento de texto não restrito. É necessário algum tipo de analisador que permita lidar com
suficientes casos, de forma a permitir o processamento de corpora não restrito, mantendo um baixo
ı́ndice de erro para a significância estatı́stica. Os analisadores descritos apresentam bons resultados, contudo exigem que lexicógrafo tenha de estar com atenção aos resultados produzidos. Observase que é importante conceber e implementar módulos integráveis, de forma a que a construção de
ferramentas computacionais seja facilitada, permitindo ajustes necessários à obtenção de resultados mais fiáveis.
Este capı́tulo aborda a análise por folhas tal como foi concebida e conduzida por Hagège (2000),1
cuja finalidade foi testar e demonstrar a possibilidade de separação entre propriedades linguı́sticas
e a informação que é utilizada pelos algoritmos, e proceder à extracção de sintagmas nominais
de corpora não restrito. Este trabalho enquadra-se na análise sintáctica de superfı́cie e orientase para o processamento de textos não restritos, isto é, que não foi previamente tratado, podendo
conter erros, pausas preenchidas e agramaticalidades. Em termos de abordagem, foca a utilizaç ão
do conhecimento linguı́stico e a manutenção da declaratividade, indicando uma visão diferente e
uma reformulação do conceito habitual de gramática, de forma a facilitar a sua manipulação e
actualização.
Este trabalho constituiu um dos pontos de partida para o trabalho realizado no âmbito desta
tese, constituindo também uma importante base para a sua avaliação. Este capı́tulo aborda a metodologia empregue para a caracterização de uma lı́ngua e descreve um conjunto de regras produzidas
com essa metodologia, que constituem a fonte declarativa para um algoritmo de análise por folhas.
Descreve-se também o protótipo de análise por folhas AF, desenvolvido por Hagège (2000), no que
diz respeito ao funcionamento, tipos de dados que processa, resultados que produz e algoritmo empregue. O capı́tulo descreve ainda o processo de extracção de sintagmas nominais a partir de texto
e apresenta alguns resultados relativos à avaliação deste processo.
3.1 A descrição linguı́stica
Esta secção descreve a metodologia empregue por Hagège na construção de descrições
linguı́sticas que, sendo inscrita no paradigma 5P, permite compreender melhor os pontos de convergência ou divergência relativamente às tendências apresentadas no capı́tulo anterior.
O paradigma 5P tenta aplicar o método cientı́fico ao estudo da linguagem natural (Bès et al.,
1999). No quadro do 5P são definidos cinco nı́veis, tal como mostra a figura 3.1 , que constituem
uma plataforma para o processamento da lı́ngua natural. Os processos (P5) correspondem à parte
de implementação e realizam o trabalho efectivo sobre as sequências linguı́sticas, utilizando os
algoritmos desenvolvidos. A fonte declarativa utilizada pelos algoritmos não é necessariamente
constituı́da pela formalização das caracterı́sticas linguı́sticas (P2) ou pelas suas generalizações (P3),
mas sim calculável a partir destas (Hagège e Bès, 1999). Isto leva a uma clara separação entre a
1 Uma vez que grande parte das referências utilizadas se referem a (Hagège, 2000), será referido apenas o autor Hagège
em substituição destas.
CAPÍTULO 3. ANÁLISE SINTÁCTICA POR FOLHAS
28
Figura 3.1: Constituição da metodologia 5P.
nc s
det : algum : cada : qualquer : certo1 : nenhum : tanto :
q3 : tal : outro
Um nome comum no singular, exige um determinante dentro do snn.
mesmo
dem : artd
É sempre necessário que um artigo definido ou demonstrativo, contenha a categoria mesmo, dentro de um snn. (Ex. o/este mesmo rapaz).
det
nenhum
Não se permite a presença conjunta de um determinante e de um nenhum.
(Ex. *este/um/o nenhum (rapaz)).
Figura 3.2: Exemplos de propriedades de existência, usados para definir o sintagma nominal nuclear para o português.
especificação de fenómenos linguı́sticos e a sua utilização. Este aspecto é importante para que a
formalização das caracterı́sticas da lı́ngua não seja influenciada por pormenores de implementação.
3.1.1
Caracterização da lı́ngua
A caracterização de uma lı́ngua é realizada, no quadro do paradigma 5P, através de um conjunto de propriedades que expressam as caracterı́sticas descritivas das expressões dessa lı́ngua
(Bès et al., 1999).2 As propriedades são estipulações que indicam o comportamento de unidades
linguı́sticas dentro de sequências da lı́ngua, podendo ser vistas como axiomas que definem modelos.
Modelos são sequências de sı́mbolos que satisfazem um conjunto de propriedades. Estas propriedades são formuladas através do uso de categorias3 e identificadores de modelos. O conjunto de
propriedades, designado por descrição da lı́ngua, não forma uma gramática uma vez que as propriedades não têm uma relação de ordem entre elas, são desprovidas de qualquer noção algorı́tmica e
cada propriedade é independente (Hagège e Bès, 1999). A figura 3.2 apresenta alguns exemplos de
2 Neste
contexto, expressões de uma lı́ngua correspondem a sequências de unidades lexicais ou palavras, nessa lı́ngua.
morfossintáctica de uma palavra.
3 Classificação
3.1. A DESCRIÇÃO LINGUÍSTICA
29
modele top(ph). % Definição do modelo de topo
remplace(n,[nc,npr,nadj]).
remplace(nadj,[nadj s,nadj p]).
remplace(nc,[nc s,nc p]).
est modele(m nn).
est modele(m nn12).
bloc(m an1,m nn,2,2,[n]).
feuille( ,’nc’,m nc,1,1,[]).
Figura 3.3: Excerto da definição linguı́stica utilizada pelo AF.
propriedades.
Definem-se três tipos de propriedades: propriedades de existência, linearidade e flechagem,
que expressam, respectiva e independentemente: a existência de entidades linguı́sticas num modelo (categorias ou identificadores de modelo); as relações de ordem linear entre essas entidades; e
as relações de flechagem (ou de dependência) entre essas entidades. A relações de dependência permitem identificar e representar relações semânticas entre e dentro de unidades sintagmáticas. As
estruturas linguı́sticas utilizadas pelos algoritmos não são directamente constituı́das por estas propriedades, mas sim deriváveis a partir delas e das suas generalizações. Em particular, a gramática
que o AF utiliza, é derivável deste conjunto de propriedades.
3.1.2
Fonte declarativa do analisador por folhas
As estruturas que o AF identifica são designadas por modelos, que, tal como foi visto na subsecção anterior, se definem a partir de um conjunto de propriedades.
O comportamento do analisador é definido por uma gramática cujas regras são descritas sob
a forma de predicados escritos em Prolog. Essas regras são de 6 tipos diferentes: definição de
modelos, definição do modelo de topo, folhas, blocos, preferências e hierarquia de categorias. A figura
3.3 mostra um excerto da gramática utilizada no AF. Note-se que ao longo de toda esta secção, os
predicados serão mencionados tal como se encontram definidos na gramática utilizada pelo AF.
Identificação dos modelos
As regras utilizadas pelo AF definem propriedades e impõem restrições sobre modelos e categorias. Tanto os modelos como as categorias podem ser utilizados de forma indistinta em determinados tipos de regras, pois a diferença entre eles reside no facto de um modelo poder conter modelos
ou categorias e uma categoria não. O predicado est modele é utilizado para indicar as etiquetas
da gramática que são modelos, e todas as que não são contempladas por este predicado, são consideradas categorias. Por exemplo, a regra est modele(m nn) indica que m nn (modelo nominal
nuclear) é um modelo.
A inı́cio da análise é feito com base num modelo inicial, que corresponde à estrutura linguı́stica
que a gramática identifica, e de uma forma geral corresponde à frase. O predicado modele top é
CAPÍTULO 3. ANÁLISE SINTÁCTICA POR FOLHAS
30
usado para a sua declaração e utiliza-se uma única vez em toda a gramática. Por exemplo, para
definir o modelo ph como sendo de topo, é utilizada a expressão modele top(ph).
Comportamento de categorias e modelos
O comportamento das categorias e dos modelos é definido à custa de um conjunto de regras designadas por folhas e blocos, que tendo uma sintaxe muito próxima, distinguem-se essencialmente
pelas entidades a que estão ligadas. Uma folha encontra-se ligada a uma categoria maximal4 e
define o seu comportamento dentro de um modelo. Um bloco por sua vez, encontra-se ligado a um
modelo e indica o seu comportamento dentro de outro modelo, onde pode ocorrer. Dada uma ca
tegoria e um modelo , se ocorre dentro de , existirá uma e uma só folha que descreverá o
comportamento da categoria dentro do modelo . De igual forma, dados dois modelos
e
, se
ocorre dentro do modelo
, existe um e um só bloco que descreve o seu comportamento dentro
do modelo
.
A folha que descreve o comportamento de uma categoria dentro de um modelo , cont ém
informação acerca da forma como inicia ou termina . Uma categoria pode iniciar sempre (1),
nunca (0), ou por vezes (2), um modelo em que ocorre; e pode terminar esse modelo por vezes (2),
sempre (1) ou nunca (0). No caso da categoria não terminar sempre o modelo, a folha correspondente
deve ter também informação acerca das categorias ou modelos que se podem seguir. A lista de
categorias ou modelos que podem seguir uma dada categoria, pode conter categorias n ão maximais.
Os blocos contêm o mesmo tipo de informação, embora aplicado ao comportamento de um modelo
dentro de outro.
O exemplo seguinte indica a forma como a categoria artd p (artigo definido, no plural) ocorre
dentro do modelo m nn (modelo nominal nuclear). A categoria artd s começa por vezes (2) o modelo
m nn, nunca o acaba (0) , e pode ser seguida por nc (nome comum), adj (adjectivo) etc. As etiquetas
nc e adj correspondem a categorias não maximais, e são generalizações de categorias como nc1 s,
nc1 p (nomes comuns contáveis, singular e plural), nc2 s (nomes comuns massivos), etc.
feuille(’artd p’, m nn, 2, 0, [ nc, nadj, adj, ... ]).
O exemplo seguinte apresenta um bloco que define o comportamento do modelo m nn (modelo
nominal nuclear) dentro do modelo ph (frase). Observa-se que o modelo m nn pode começar (2) e pode
terminar (2) o modelo ph, isto é, pode ocorrer em qualquer posição do modelo ph. O bloco indica
também que m nn pode ser seguido pelos modelos m an2q, m an2nq (modelos adjectivais nucleares
do tipo 2, quantificáveis e não quantificáveis), etc, dentro do modelo ph. Note-se que não existe para
os modelos, o equivalente às categorias não maximais, impedindo, por exemplo, de se poder utilizar
m an2 como generalização de m an2 e m an2nq.
bloc(m nn, ph, 2, 2, [ m an2q, m an2nq, ... ]).
4 Uma categoria maximal é tal que, considerando o conjunto de traços morfossintácticos de uma hierarquia de traços,
não se pode atribuir mais nenhum traço a essa categoria (Hagège, 2000, pág. 63). Por exemplo: artd s (artigo definido no
singular) é considerada uma categoria maximal, contudo a categoria artd não o é.
3.1. A DESCRIÇÃO LINGUÍSTICA
31
remplace(n, [nc, npr, nadj]).
remplace(nc, [nc1, nc2]).
remplace(nc, [nc s, nc p]).
remplace(nc1, [nc1 s, nc1 p]).
remplace(nc2, [nc2 s, nc2 p]).
remplace(nc s, [nc1 s, nc2 s]).
remplace(nc p, [nc1 p, nc2 p]).
Figura 3.4: Regras que produzem uma hierarquia de categorias para os nomes.
Figura 3.5: Diagrama representativo de uma hierarquia de categorias para os nomes.
Hierarquia de categorias
As categorias podem ser organizadas numa estrutura hierárquica utilizando para esse efeito
o predicado remplace. Esta estrutura hierárquica, pode ser vista como um grafo dirigido (DAG).
No nı́vel mais baixo da hierarquia encontram-se as categorias maximais e nos restantes nı́veis
encontram-se as categorias não maximais. O exemplo seguinte mostra que um nome (n) pode ser
um nome comum (nc), um nome próprio (npr), ou um nome/adjectivo (nadj).
remplace(n, [nc, npr, nadj]).
O exemplo da figura 3.4 mostra um extracto da hierarquia de categorias para os nomes. A figura
3.5 mostra uma representação gráfica das relações definidas no exemplo. As categorias maximais
e não maximais que constem da hierarquia de categorias, podem ser usadas na lista de elementos
seguintes das folhas e dos blocos, tal como foi anteriormente dito.
Preferências
A utilização de preferências permite fazer a escolha de certas categorias em detrimento de outras, quando consideradas em determinado contexto. Este mecanismo permite reduzir as ambiguidades tanto ao nı́vel das categorias como ao nı́vel dos modelos. A sua utilização no AF é facultativa,
CAPÍTULO 3. ANÁLISE SINTÁCTICA POR FOLHAS
32
pelo que a análise pode ser realizada sem considerar esta informação, originando assim um conjunto
mais alargado de possı́veis resultados. Uma das consequências da utilização das preferências é a
possı́vel redução da ambiguidade ao nı́vel da classificação das palavras, no caso da informação analisada pelo AF não se encontrar já desambiguada do ponto de vista morfossintáctico. A gramática
permite indicar quatro tipos de preferências:
em qualquer contexto ou dentro de um dado modelo;
para uma unidade lexical, em qualquer contexto ou dentro de determinado modelo;
à direita de um modelo;
à direita de um modelo, quando a palavra em análise possui uma determinada categoria.
Preferência dentro de um modelo. A forma mais simples de indicar uma preferência é através
do predicado pref cat ds mod. O exemplo seguinte indica que, se a análise chegar a um estado
tal que o modelo superior5 seja um modelo nominal nuclear (m nn), as categorias nc1 s e adj3 s
estiverem associadas à unidade lexical actual e for possı́vel produzir um resultado tanto para o
primeiro como para o segundo caso, vai-se preferir o resultado que incluir a categoria nc1 s.
pref cat ds mod(nc1 s, adj3 s, m nn).
Preferência considerando a unidade lexical. O predicado pref cat sig é utilizado para o
caso da preferência só se aplicar a determinada palavra ou unidade lexical. O exemplo seguinte indica que, sempre que o resultado na análise incluir duas hipóteses em que ocorre a palavra “caso”,
dentro do modelo m nn (modelo nominal nuclear), com as classificaç ões nc1 s (nome comum, singular) e conj (conjunção), se deve eliminar a segunda.
pref cat sig([caso,nc1 s],[caso,conj],m nn).
Preferência após um modelo. O predicado pref mod suiv é utilizado para indicar a preferência entre dois modelos, depois da ocorrência de determinada categoria ou modelo, designado
por modelo anterior6 . O exemplo seguinte indica que se prefere o modelo m an2q (modelo adjectival
quantificado) ao modelo m nn (modelo nominal nuclear), após ocorrer m prepn (modelo preposicional
nuclear).
pref mod suiv(m an2q,m nn,m prepn).
5 O modelo superior é o último modelo aberto que ainda não foi fechado, isto é, o modelo dentro do qual a análise está a
ser efectuada. Por exemplo, imediatamente após o inı́cio da análise, o modelo superior fica a ser o modelo de topo.
6 Durante a análise, o modelo anterior corresponde ao último modelo fechado.
3.2. AF - PROTÓTIPO DE ANÁLISE POR FOLHAS
33
Figura 3.6: Forma de produção de informação adequada à entrada do AF.
Preferência após um modelo, tendo em consideração a categoria da palavra. É também
permitido indicar uma preferência tendo em consideração, não só a categoria ou modelo anterior,
mas também a unidade lexical actual. Para isso, é utilizado o predicado pref mod suiv cat. A
regra apresentada no exemplo seguinte indica que se prefere o modelo m an2nq ao modelo m nn,
após o fecho do modelo copv n, se a categoria gramatical da palavra actual for nc1 p.
pref mod suiv cat(m an2nq, m nn, copv n, nc1 p).
3.2 AF - Protótipo de Análise por folhas
O AF é um protótipo de análise sintáctica de superfı́cie desenvolvido no âmbito do doutoramento de Hagège (2000). Este analisador permite identificar constituintes sintácticos presentes
num texto e estabelecer relações sintácticas dentro e entre esses constituintes. Em particular, foi
utilizado para identificar sintagmas nucleares (ver secção 3.3.1) e estabelecer a flechagem no interior e entre esses sintagmas nucleares. Esta secção descreve o funcionamento do AF, tipo de dados
que processa, tipo de análise que efectua e o algoritmo que utiliza.
3.2.1
Funcionamento
De forma a produzir os dados na forma de entrada utilizada pelo AF, a partir de um documento,
é necessário efectuar o processamento morfossintáctico desse documento. A estratégia seguida para
esta fase, ilustrada na figura 3.6, consistiu em separar o texto em unidades lexicais, fazer a sua
anotação morfossintáctica, adaptar as etiquetas previamente atribuı́das através de um tratamento
pós-análise morfológica e, caso fosse necessário, desambiguar os resultados obtidos. O resultado
produzido na fase de pós-análise morfológica corresponde à entrada do analisador sintáctico. No
âmbito do trabalho de Hagège, a classificação morfossintáctica foi realizada pelo analisador morfológico SMORPH (Aı̈t-Mokhtar, 1998). O tratamento pós-análise morfológica foi efectuado com a
ferramenta MPS, que uniformiza as etiquetas, aplica um conjunto de regras morfossint ácticas e
divide o texto em frases.
CAPÍTULO 3. ANÁLISE SINTÁCTICA POR FOLHAS
34
Os dados que o AF recebe consistem em sequências de frases. Cada frase pode ser constituı́da
por várias alternativas, que correspondem a diferentes segmentações em termos de unidades lexicais. A análise sintáctica é feita com o auxı́lio de uma operação designada por folhagem, que
consiste em associar para cada unidade lexical o conjunto das possı́veis regras a aplicar, com base
na suas classificações morfossintácticas. Esta operação é efectuada por um utilitário designado por
Jonction que produz, a partir da saı́da do MPS, um conjunto de predicados Prolog.
3.2.2
Dados de entrada - tratamentos
Os dados processados pelo AF consistem em texto segmentado em frases, cada uma delas constituı́da por unidades lexicais etiquetadas morfossintaticamente, com ambiguidade ou não. Uma
frase pode ser segmentada em diferentes unidades lexicais. Assim, cada frase pode ser constituı́da
por uma ou várias hipóteses de segmentação, que correspondem a diferentes sequências de unidades lexicais. A estrutura que representa uma unidade lexical, é composta por uma lista das suas
possı́veis classificações. A figura 3.7 apresenta um exemplo de uma frase que segue essa estrutura.
[ F78
[ A1
’Depois’, [’depois’,’adv’],
’adormecem’, [’adormecer’,’vc’],
’cansadas’, [’cansar’,’ppas’ , ’cansado’,’adj1 p’],
’...’, [’...’,’eliminer’]
] A1
[ A2
’Depois’, [’depois’,’adv’],
’adormecem’, [’adormecer’,’vc’],
’cansadas’, [’cansar’,’ppas’ , ’cansado’,’adj1 p’],
’..’, [’..’,’eliminer’],
’.’, [’.’,’eliminer’]
] A2
] F78 %fim da frase número 78
Figura 3.7: Exemplo de uma frase com duas alternativas.
3.2.3
Resultados produzidos
Os resultados produzidos são o conjunto de sequências que correspondem à análise de cada
frase. De uma forma geral, a análise produzida para cada frase consiste no conjunto de uma ou
mais possibilidades de análise, em que cada modelo aberto foi também fechado. Por outro lado, se
não for possı́vel produzir uma análise total, obtém-se uma análise parcial até ao ponto em que a
análise falhou e neste caso alguns modelos permanecerão abertos.
Para cada frase, pode também ser produzido um conjunto de relações entre cada unidade lexical
do texto, processo que se designa por flechagem. A figura 3.8 mostra o resultado da an álise de
uma frase em que se inclui a flechagem e a figura 3.9 mostra um diagrama representativo desse
resultado. Os argumentos do predicado fl são os ı́ndices das unidades lexicais presentes na frase,
no exemplo da figura fl(1,5) indica que a unidade lexical as flecha sobre raparigas.
3.2. AF - PROTÓTIPO DE ANÁLISE POR FOLHAS
35
Análise:
ph(
m nn (
as(artd)
minhas(poss)
m an1 (
m advn1 (
muito(adv2 1)
) m advn1
belas(adj1 p)
) m an1
raparigas (nc1 p)
) m nn
) ph
Flechagem:
fl(1,5). # as
raparigas
fl(2,5). # minhas
raparigas
fl(4,5). # belas
raparigas
fl(3,4). # muito
belas
Figura 3.8: Análise da frase “as minhas muito belas raparigas”, incluindo flechagem.
Figura 3.9: Representação gráfica da análise de uma frase, incluindo flechagem.
3.2.4
Algoritmo
Em termos gerais, o algoritmo da análise por folhas consiste em analisar cada um dos elementos
que constituem a frase, através da concatenação sucessiva de folhas, cada uma das quais impondo
restrições à concatenação que se sucederá. A figura 3.10 mostra o diagrama de funcionamento do
algoritmo. A cada instante são mantidas listas com os modelos que se encontram abertos, conjunto
das categorias e modelos que se podem seguir. A análise consiste em concatenar unidades lexicais
com a categoria associada, abrir e fechar modelos, e a cada concatenação introduzir uma flechagem
ou instanciar uma flechagem já existente. No fim, se existirem várias análises possı́veis, selecciona uma delas. A operação descrita como criar folhas, consiste em, utilizando os padrões de folhas
(derivados das propriedades linguı́sticas), associar à palavra corrente as folhas correspondentes às
suas classificações morfossintácticas. A operação seleccionar folhas candidatas consiste em seleccionar, do conjunto das folhas associadas à palavra, o conjunto de todas as folhas compatı́veis com
o estado actual da análise. No caso se existirem duas folhas associadas à mesma categoria, dá-se
preferência à folha cujo modelo é o modelo actual (princı́pio do modelo mais comprido possı́vel). A
36
CAPÍTULO 3. ANÁLISE SINTÁCTICA POR FOLHAS
Figura 3.10: Diagrama de funcionamento da análise por folhas.
operação Tratar Folha, consiste em proceder a eventuais aberturas e fechos de modelos de acordo
com a folha que se está a tratar, actualizar lista de modelos abertos, concatenar a unidade lexical
e a categoria a que se refere a folha em tratamento à análise actual, actualizar lista de categorias
seguintes, tratar da flechagem da unidade lexical, efectuar eventuais fechos de modelos e actualizar
a lista de modelos abertos.
3.2.5
A questão da ambiguidade
A ambiguidade, no contexto da análise por folhas, pode existir tanto ao nı́vel das categorias
como ao nı́vel dos modelos. A ambiguidade entre categorias é uma consequência da ambiguidade da análise morfológica, isto é, ao nı́vel morfossintáctico pode ser atribuı́da mais do que uma
classificação a cada unidade lexical. A ambiguidade entre modelos é introduzida pelo processo de
Jonction e deve-se ao facto de determinadas categorias poderem ocorrer em mais do que um modelo.
Este caso de dupla ambiguidade pode ser inicialmente entendido como um problema que se coloca
à análise. Contudo, a aproximação utilizada, que consiste em delimitar as frases de um texto em
sintagmas nucleares, funciona como um prolongamento da etiquetagem morfossintáctica (Hagège,
2000). A realização da etapa de desambiguação entre a análise morfológica e a análise sintáctica,
contribui para uma redução da ambiguidade nos resultados finais.
3.2.6
Casos de tratamento particular
O tratamento de textos reais, em especial utilizando um léxico reduzido, implica a identificação
e tentativa de tratamento das palavras que não constam desse léxico. Por outro lado, a lı́ngua
apresenta um conjunto de fenómenos de difı́cil tratamento computacional. Os tópicos seguintes
descrevem as opções escolhidas por Hagège relativamente ao tratamento destes casos particulares.
3.2. AF - PROTÓTIPO DE ANÁLISE POR FOLHAS
37
Palavras desconhecidas
É na fase da análise morfológica que estas palavras são detectadas e etiquetadas como desconhecidas. No caso particular do trabalho de Hagège, estes resultados são depois manipulados na
fase da pós-análise morfológica, através de regras de recomposição, de forma a facilitar a tarefa da
análise sintáctica. Determinadas sequências de palavras desconhecidas em combinação com unidades lexicais circundantes, são muitas vezes candidatas a nomes próprios e, nesse caso, o tratamento
fica resolvido antes da entrada no analisador sintáctico. No entanto, a entrada do analisador pode
ainda conter palavras desconhecidas que têm de ser tratadas, de forma a não parar a análise. Esse
tratamento é efectuado ao nı́vel da gramática e consiste em indicar, entre outras coisas, que uma
palavra desconhecida, pode ocorrer dentro de qualquer modelo e seguida por qualquer outro modelo
e que qualquer modelo pode ser seguido de um modelo desconhecido, constituı́do pela palavra ou
sequência de palavras desconhecidas.
feuille(’inconnu’, m inc, 1, 1, []).
feuille(’inconnu’, VAR1, 0, 2, [VAR1]).
Coordenação
O tratamento da coordenação coloca vários problemas às propriedades dos sintagmas nucleares.
O seu tratamento poderá implicar uma revisão da actual noção de núcleo, dado que a coordenação
pode levar à criação de dois ou mais núcleos num sintagma nuclear. O limitado conhecimento do
contexto anterior da análise, em determinado instante, impede de determinar, em muitos casos, o
que deve ser coordenado com o quê. O tratamento da flechagem não se encontra adaptado aos casos
de coordenação, pelo que terá de ser também revisto (Hagège, 2000). No contexto dos trabalhos de
Hagège, este problema foi minimizado de forma a não impedir a análise automática. A estratégia
usada para efectuar correctamente a extracção de sintagmas nominais a partir da análise, consistiu
em contornar a coordenação, usando, tanto informação presente na gramática, como como fazendo
parte do seu tratamento ao nı́vel do algoritmo.
As duas regras seguintes permitem dar conta da coordenação, tanto externa aos sintagmas
nucleares, como dentro dos sintagmas nucleares:
feuille(coord, m conj, 1, 1, []).
feuille(coord, SUPERIOR, 0, 0, [SEGUINTES]).
A primeira folha indica que a unidade lexical etiquetada de coord, constituirá sozinha o modelo
m conj. O modelo m conj pode ocorrer em ph, e nesse contexto pode seguir ou ser seguido por
qualquer outro modelo. A segunda folha indica que a categoria coord pode ocorrer em qualquer
modelo, e ser seguida por qualquer outra categoria ou modelo. Note-se porém que, a categoria
coord não pode começar nem terminar um modelo em que ocorra, excepto o modelo m conj.
Além das duas folhas apresentadas anteriormente, (Hagège, 2000) indica que o analisador
efectua um conjunto de operações adicionais quando se encontra perante um caso de possı́vel
coordenação. Assim, sempre que se encontra uma unidade lexical, etiquetada como sendo
coordenação, são aplicadas as seguintes regras:
CAPÍTULO 3. ANÁLISE SINTÁCTICA POR FOLHAS
38
Figura 3.11: Cadeia de processamento do sistema de extracção de SN.
1. A folha anterior nunca fecha o modelo. Neste caso será utilizada a segunda folha, fazendo com
que a variável SUPERIOR seja instanciada com o modelo corrente.
2. A folha anterior fecha sempre o modelo. Neste caso, verifica-se se a folha que segue a
coordenação pode pertencer ao modelo corrente. Em caso afirmativo utiliza-se novamente
a segunda folha, caso contrário utiliza-se a primeira folha.
3. A folha anterior fecha por vezes o modelo em que ocorre. Neste caso, tamb ém se verifica se
a folha que segue a coordenação pode pertencer ao modelo corrente. No caso de não poder
pertencer utiliza-se a primeira folha.
3.3 Extracção de sintagmas nominais
O trabalho realizado por Hagège (2000) seguiu duas linhas de orientação. A primeira linha
compreende um aspecto descritivo, segundo a qual formaliza descrições para as construções da
lı́ngua portuguesa. A segunda linha compreendeu o tratamento dessas construções, tratamento
esse que se fixou no objectivo de reconhecer os sintagmas nominais presentes num texto. O processo
de reconhecimento de sintagmas nominais (SNs) foi realizado numa cadeia de tratamentos (ver
figura 3.11 ), cuja última etapa consistiu em construir sintagmas nominais a partir de elementos
mais simples, definidos como sintagmas nucleares. Os próximos tópicos apresentam os resultados
obtidos na avaliação efectuada por Hagège, usando a cadeia de tratamentos para a extracção de
SNs.
3.3.1
Sintagma Nuclear
Hagège define sintagmas nucleares como domı́nios linguı́sticos, onde se verificam determinadas
propriedades, e se situam entre a unidade lexical e o conceito tradicional de sintagma, designados
adiante apenas por sintagmas. Normalmente, os sintagmas nucleares são constituintes dos sintagmas tradicionais mas, por vezes, podem ser equivalentes. O exemplo seguinte faz a divis ão de uma
frase, que neste caso corresponde a um sintagma nominal, em sintagmas nucleares.
3.3. EXTRACÇÃO DE SINTAGMAS NOMINAIS
39
(Esta bela amiga) (portuguesa) (do Pedro)
Neste exemplo, a primeira demarcação corresponde a um sintagma nominal nuclear, a segunda a
um sintagma adjectival nuclear e a terceira a um sintagma preposicional nuclear. Cada um desses
sintagmas nucleares organiza-se em torno de um núcleo ou cabeça lexical. Neste caso, os núcleos dos
sintagmas nucleares são, respectivamente, o nome amiga, o adjectivo portuguesa e o nome próprio
Pedro.
O motivo que leva à utilização dos sintagmas nucleares prende-se com a existência de propriedades particulares no interior destes domı́nios sintácticos que são muito mais fáceis de descrever
e ligar do que os sintagmas. A análise de uma frase pode consistir, por um lado, na delimitação
de sintagmas nucleares aı́ presentes e, por outro, em colocar em evidência as relações que existem
entre esses sintagmas nucleares.
Os sintagmas nucleares utilizados são em tudo semelhantes aos sintagmas minimais utilizados
por Giguet (1998) e também aos chunks de Abney (1991). Os sintagmas nucleares apresentam
uma caracterı́stica que os distingue dos sintagmas minimais e dos chunks, que é o facto de que
um sintagma nuclear além de ser constituı́do por categorias poder também conter outros sintagmas
nucleares. Este caso está presente no exemplo seguinte, em que o sintagma nominal nuclear contém
um sintagma adjectival nuclear que por sua vez contém um sintagma adverbial nuclear.
( A ( ( ainda mais ) bela ) rapariga ) Os sintagmas nucleares constituem unidades prosódicas na frase, contrariamente aos sintagmas
(Hagège, 2000).
3.3.2
O extractor
A tarefa de extracção de SNs constitui uma forma de utilização directa da análise produzida
pelo AF. Hagège desenvolveu uma aplicação, que recebe como entrada as análises obtidas do AF,
contendo sintagmas nucleares, e produz um ficheiro em formato HTML constituı́do pelos SN extraı́dos para cada frase.
A expressão regular utilizada para a extracção dos SNs é a seguinte:7
Sintagma Nominal = NN COMPL*
NN = m nn | m nnt | mnn rel
COMPL = CP1 + (COORD CP2)* CP1*
CP1 = m an2nq | m an2q | mpp n | m prepn
COORD = coord | virg
CP2 = m prepn | m an2 unique.8
Como se pode verificar, a extracção de SNs é feita por meio da identificação de sintagmas nucleares, em particular de sintagmas nominais nucleares, sintagmas adjectivais nucleares e sintagmas
7 Os
elementos seguintes encontram-se descritos no apêndice A desta dissertação.
adjectivais do tipo 2 constituı́dos por uma única palavra.
8 Modelos
CAPÍTULO 3. ANÁLISE SINTÁCTICA POR FOLHAS
40
preposicionais nucleares. De uma forma geral, define-se SN como sendo uma sequ ência composta de,
pelo menos, um sintagma nominal nuclear (que constitui a cabeça do SN) e todos os complementos
e/ou modificadores dessa cabeça, que são por sua vez os sintagmas preposicionais nucleares e adjectivais nucleares, bem como os complementos e/ou modificadores destes últimos. Assim, designa-se
por complemento de um SN, todo o sintagma adjectival nuclear ou preposicional nuclear que é complemento ou modificador da cabeça do SN ou de um dos núcleos do sintagma nuclear complementar
dessa cabeça (Hagège, 2000).
3.3.3
Condições de avaliação
A avaliação foi feita com base na confrontação de resultados obtidos na extracção de SN efectuada pela cadeia de tratamentos apresentada na figura 3.11, e na extracção de SN feita manualmente
seguindo os mesmos critérios.
O corpus usado para a avaliação é constituı́do por cerca de 4000 segmentos lexicais e é composto
por textos retirados da Constituição Portuguesa, jornais e teses cientı́ficas.
Foram realizados dois tipos de avaliação:
REAL, avaliação de resultados obtidos pela cadeia de tratamentos, sem qualquer tipo de
intervenção exterior em qualquer fase desse tratamento.
IDEAL, avaliação sobre texto bem etiquetado, desambiguado manualmente e no qual não
existem palavras desconhecidas (idealmente etiquetado). Para efectuar esta avaliação a partir
da saı́da produzida pelo MPS, procedeu-se à verificação manual da etiquetagem feita pelo
sistema, e sempre que necessário, fez-se uma correcção manual, de forma a obter uma correcta
etiquetagem sem ambiguidade.
As medidas de precisão e cobertura utilizadas de seguida, correspondem à sua definição habitual.
Assim, precisão é definida como sendo o número de respostas correctas, calculadas por um sistema, sobre o número total de respostas, dadas por esse sistema. Cobertura é definida como sendo
o número de respostas correctas, calculadas por um sistema, sobre o número de respostas correctamente esperadas.
3.3.4
Resultados da avaliação
Dos elementos obtidos por Hagège no âmbito da avaliação do AF, importa aqui mencionar apenas os que não se relacionam com a flechagem, dado que esta não é tratada no âmbito desta tese.
Assim, de forma a conhecer em que medida a cadeia de tratamentos permite identificar os SN
presentes no texto inicial, apresentam-se resultados relativos à verificação de existência de SN.
Apresentam-se também resultados relativos ao teor dos SN, isto é, em que medida se teve êxito a
extrair o SN de uma forma integral, ou de outra forma, se o elemento extraı́do corresponde a um
SN, apenas a uma parte do SN, ou inclui elementos adicionais.
No que diz respeito ao número de palavras desconhecidas pelo analisador morfológico: no conjunto de 3602 segmentos analisados, cerca de 5,25% de palavras são identificadas como desconhecidas. Por outro lado, na saı́da do MPS, que corresponde à entrada do AF, para um total de 3867
3.3. EXTRACÇÃO DE SINTAGMAS NOMINAIS
41
segmentos, 0,85% foram identificados como desconhecidos, 2,77% foram incorrectamente classificados e 20,04% tinham ambiguidade. Quanto à desambiguação em relação à categoria, o AF conseguiu
uma taxa de desambiguação próxima dos 94%.
Existência de SNs
Um SN considera-se correcto se, no texto tratado manualmente foi identificado um SN, tal que
um deles é uma sub-sequência do outro (eventualmente igual), isto é, um SN considera-se correcto
mesmo que o número de complementos seja insuficiente ou demasiado.
A tabela 3.1 apresenta de forma resumida os resultados relativos à identificação de SNs no
Existência de SN
Texto real
Texto classificado idealmente
Precisão
89,61%
96,12%
Cobertura
82,93%
89,42%
Tabela 3.1: Avaliação do quanto à existência de sintagmas nominais.
texto. A medida de precisão indicada na tabela, corresponde à percentagem de SN extraı́dos e
dados como correctos sobre o número total de SN extraı́dos pela cadeia de tratamento. A cobertura,
por seu lado, corresponde à percentagem de SN extraı́dos e dados como correctos, sobre o número
de SN identificados manualmente no texto.
Os erros relativos ao tratamento de texto idealmente anotado e desambiguado devem-se sobretudo ao tratamento insatisfatório da coordenação e a estruturas, que não tendo sido previstas, não
foram analisadas.
Teor dos SN
A partir dos SN extraı́dos, cuja cabeça lexical foi correctamente identificada, foi calculada: a
taxa de SNs cujo número de complementos é exactamente o esperado; a taxa de SNs demasiado
longos, para os quais a cadeia de tratamentos extraiu complementos que não são complementos
desses SNs; a taxa de SNs demasiado curtos, para os quais a cadeia de tratamentos não foi capaz de
extrair todos os complementos. A tabela 3.2 apresenta os resultados obtidos, que, como se verifica,
Teor dos SN
Texto real
Texto classificado idealmente
Completos
87,32%
89,78%
Demasiado longos
6,49%
6,73%
Curtos
6,19%
3,49%
Tabela 3.2: classificação quanto ao teor dos SNs correctamente identificados.
são muito semelhantes tanto no que respeita ao texto real como ao texto correctamente anotado e
desambiguado.
42
CAPÍTULO 3. ANÁLISE SINTÁCTICA POR FOLHAS
3.4 Sumário
Este capı́tulo foca os detalhes da análise por folhas, tal como foi concebida e realizada no âmbito
dos trabalhos de Hagège.
A primeira parte do capı́tulo descreve a gramática utilizada na análise por folhas, cujos elementos indicados à custa de: folhas – que definem o comportamento de categorias dentro de modelos;
blocos – que definem o comportamento de modelos dentro de outros modelos; hierarquia de categorias – que permitem organizar as categorias maximais e definir categorias não maximais, permitindo simultaneamente reduzir a dimensão das regras e torná-las mais claras. A gramática permite
também definir vários tipos de preferências que são utilizados posteriormente para seleccionar um
conjunto de resultados desejáveis do conjunto de resultados possı́veis.
A secção 3.2 descreve protótipo de análise por folhas AF. A análise que executa é caracterizada por ser simples, consistindo em sucessivas concatenações de elementos. Destacam-se alguns
casos de tratamento particular, como é a questão das palavras desconhecidas e da coordenação. O
tratamento da coordenação coloca vários problemas às propriedades dos sintagmas nucleares, em
particular porque a coordenação poderá levar à criação de dois núcleos. Nos trabalhos de Hagège
este problema é contornado usando mecanismos, tanto ao nı́vel da gramática como ao nı́vel do algoritmo.
Finalmente, descreve-se o processo de extracção de sintagmas nominais a partir de texto, que
se baseia na identificação de sintagmas nucleares, mais fáceis de identificar e descrever do que os
sintagmas tradicionais. Apresentam-se resultados sobre a avaliação deste processo.
Este capı́tulo descreve a gramática que serve de fonte de dados para o algoritmo de análise
sintáctica de superfı́cie do SuSAna, que será apresentado no próximo capı́tulo. Sendo derivada
da estrutura da gramática utilizada pelo AF, mostram-se as alterações efectuadas e descreve-se
a sua sintaxe e semântica. O capı́tulo indica de que forma a gramática do SuSAna permite uma
manipulação mais fácil da informação e um conjunto de restrições mais alargado, comparativamente à gramática do AF. Este capı́tulo apresenta também a relação da gramática do SuSAna com
gramáticas de outros formalismos, apresentando uma metodologia para conversão informação, de e
para, gramáticas livres de contexto.
4.1 Elementos da gramática
A gramática utiliza três tipos de estruturas: a estrutura bloco permite definir o comportamento
de modelos dentro de outros modelos; as preferências, opcionais, permitem impor restrições aos
resultados da análise com base em elementos probabilı́sticos; e uma hierarquia para os sı́mbolos
da gramática, que permite simplificar a escrita de regras e simultaneamente reduzir o tamanho da
gramática.
O formato que se utilizou para a representação da gramática é o XML. O formato XML é um
standard flexı́vel e adequado para a representação de dados, que se tem vindo a tornar cada vez
mais atraente devido ao conjunto de parsers e aplicações de validação, disponı́veis para várias plataformas. Esta opção vai também de encontro ao esforço tem sido conduzido no sentido pelo L F
no sentido de uniformizar o formato da informação. A figura 4.1 mostra o Definição do Tipo de
Documento (DTD) da gramática, constituı́do por quatro elementos básicos com que se descrevem as
propriedades de uma lı́ngua. O elemento topmodel não tem atributos e é utilizado para definir o
elemento de topo por omissão, uma única vez. A definição do comportamento da lı́ngua é feita apenas com três tipos de regras, que permitem especificar: a hierarquia dos modelos e das categorias,
o comportamento dos modelos dentro de outros modelos e as restriç ões à análise.
4.1.1
Modelos
As estruturas que o SuSAna identifica, a partir de um conjunto de propriedades, designam-se
por modelos. Uma sequência de sı́mbolos que satisfaz um conjunto de propriedades, constitui um
modelo para essas propriedades (Hagège, 2000). No contexto da análise sintáctica, considerando
como sı́mbolos as caracterı́sticas morfossintácticas das palavras, um modelo para um conjunto de
44
CAPÍTULO 4. GRAMÁTICA DO SUSANA
<?xml version="1.0" encoding="iso-8859-1"?>
<!ELEMENT LangSpec (topmodel,(superclass|block|preference)+)>
<!ELEMENT topmodel EMPTY>
<!ATTLIST topmodel name CDATA #REQUIRED>
<!ELEMENT superclass (subclass)*>
<!ATTLIST superclass name CDATA #REQUIRED>
<!ELEMENT subclass EMPTY>
<!ATTLIST subclass name CDATA #REQUIRED>
<!ELEMENT block (nextmod)*>
<!ATTLIST block
name
CDATA #REQUIRED
sup
CDATA #REQUIRED
start
(0|1|2) #REQUIRED
end
(0|1|2) #REQUIRED
>
<!ELEMENT nextmod EMPTY>
<!ATTLIST nextmod name CDATA #REQUIRED>
<!ELEMENT preference EMPTY>
<!ATTLIST preference
prefmod
CDATA #REQUIRED
discmod
CDATA #REQUIRED
supmod
CDATA #IMPLIED
prevmod
CDATA #IMPLIED
word
CDATA #IMPLIED
cat
CDATA #IMPLIED
confidance CDATA #IMPLIED <!-- float in [0-1] -->
>
Figura 4.1: DTD da gramática do SuSAna.
propriedades linguı́sticas, é uma sequência de descrições morfossintácticas que satisfazem essas
propriedades.
De forma a simplificar a notação, estendeu-se a noção de modelo, de forma a abranger também
as categorias morfológicas, que constituem a base da análise. Em oposição à utilização de folhas e
blocos, apresentada no capı́tulo 3 para descrever o comportamento das categorias dentro de modelos
e dos modelos dentro de modelos, na gramática do SuSAna é feita uma fusão entre folhas e blocos.
Assim, as categorias passam também a ser identificadas e tratadas como modelos, dando origem
à utilização dos termos modelo terminal e modelo não terminal para distinguir as categorias dos
modelos.
Na gramática aqui descrita, deixou de haver a necessidade de se utilizar o predicado est modele
(utilizado na gramática do AF) para distinguir as categorias dos modelos. A distinção entre modelos
terminais e não terminais é feita em tempo de execução, com base na informação presente nos
blocos: uma vez que os blocos especificam o comportamento de modelos dentro de modelos, para
verificar se um dado modelo m é terminal, basta verificar se algum bloco especifica comportamento
de outro modelo dentro de m; se isso acontecer m é não terminal. Esta possibilidade de deduzir o
tipo dos modelos elimina a redundância e a possı́vel incoerência de dados.
4.1. ELEMENTOS DA GRAMÁTICA
4.1.2
45
Modelo de topo
O modelo de topo indica o modelo pelo qual se inicia a análise e corresponde à estrutura
linguı́stica que se pretende analisar. Este modelo é definido pelo elemento topmodel, como se pode
verificar pelo DTD da gramática (figura 4.1). O elemento tem apenas um atributo, define o modelo de topo por omissão e é declarado apenas uma vez na gramática. Por exemplo, o identificador
sentence poderia ser utilizado para fazer a análise de frases, o identificador address seria usado
para identificar endereços e o identificador par poderia ser usado para processar par ágrafos. Este
elemento pode ser alterado em tempo de execução de forma a permitir fazer a análise de qualquer
estrutura linguı́stica, que seja definida pela gramática.
Em versões futuras da gramática, o elemento topmodel deverá passar a ser opcional pois pode
ser parcialmente calculado1 a partir das restantes regras presentes na gramática.
4.1.3
Comportamento dos modelos
A informação presente nos predicados folha e bloco, utilizados pelo AF para definir o comportamento das categorias e dos modelos, passou a estar incluı́da num único elemento. Embora continue
a haver uma distinção formal entre categorias e modelos, sendo que uma categoria é um modelo
terminal, o seu tratamento ao nı́vel do algoritmo é feito da mesma forma.
O comportamento de modelos dentro de outros modelos é descrito pelo elemento block. Os
atributos name e sup são obrigatórios e indicam que o modelo com nome name pode ocorrer dentro
do modelo sup. Os atributos start e end podem tomar os valores 0 (nunca), 1 (sempre) ou 2 (por
vezes) e indicam o modo como pode ser feita essa ocorrência. Por exemplo, o valor 2 no atributo
start indica que o modelo pode ocorrer no inı́cio, mas essa ocorrência não é obrigatória.
<!ELEMENT block
<!ATTLIST block
name
sup
start
end
(nextmod)*>
CDATA
CDATA
(0|1|2)
(0|1|2)
#REQUIRED
#REQUIRED
#REQUIRED
#REQUIRED>
O exemplo seguinte define a categoria ou modelo terminal arti s (artigo indefinido singular):
pode ocorrer dentro do modelo mpp n (modelo proposicional nuclear), embora nunca o possa começar
nem acabar. Note-se também que os modelos que o podem seguir são apenas: nc (nome comum),
nadj (nome/adjectivo), inconnu (palavra desconhecida).
<block name="arti s" sup="mpp n" start="0" end="0">
<nextmod name="nc"/>
<nextmod name="nadj"/>
<nextmod name="inconnu"/>
</block>
1 O seu cálculo consiste em percorrer todos os blocos da gramática e verificar quais os modelos que não ocorrem em nenhum
outro. De uma forma geral a gramática conterá apenas um modelo nestas condições. No caso de isso não acontecer pode ser
escolhido qualquer um destes modelos.
CAPÍTULO 4. GRAMÁTICA DO SUSANA
46
Além dos nomes de modelos, podem também ser utilizadas variáveis para designar conjuntos
de modelos. Este mecanismo resulta dos predicados em Prolog, usados na gram ática do AF, que se
continuou a utilizar apenas para manter a compatibilidade com os dados anteriores. No exemplo
abaixo, indica-se que a categoria coord (coordenação) pode ocorrer em qualquer modelo, embora não
o possa começar nem terminar, e que pode ser seguida, dentro desse modelo, por qualquer outro.
<block name="coord" sup="VARM" start="0" end="0">
<nextmod name="X"/>
</block>
Uma forma mais elegante e clara de se indicarem conjuntos de modelos evitando a utilizaç ão de
variáveis, consiste em utilizar a hierarquia de modelos. De notar que este método poderá conduzir
à criação de classes de modelos não relacionados, no caso de utilização abusiva, tornando assim as
regras mais confusas. Por exemplo, a definição da classe all, na hierarquia de modelos, como sendo
uma etiqueta genérica na qual se incluem todas as outras, permitirá indicar a regra anterior de
uma forma mais elegante:
<block name="coord" sup="all" start="0" end="0">
<nextmod name="all"/></block>
4.1.4
Hierarquia de modelos
A gramática permite definir hierarquias para os modelos, possibilitando a elaboração de regras
mais simples e abrangentes. Neste ponto a gramática sofreu uma evolução em relação à gramática
utilizada pelo AF, que apenas permite definir relações hierárquicas para os modelos terminais. A
possibilidade de definir hierarquias também para os modelos não terminais, possibilita a produção
de regras mais simples e a possı́vel redução de elementos nas regras.
As relações hierárquicas entre os modelos são definidas pelo uso do elemento superclass. O
exemplo seguinte indica que n (nome) pode ser: nc (nome comum), npr (nome próprio) nadj (ambiguidade nome/ adjectivo). Por sua vez, nc pode ser nc s (singular), nc p (plural), nc1 (nomes comuns
contáveis), nc2 (nomes comuns massivos). Note-se que o resultado pode ser representado como um
grafo dirigido, à semelhança da figura 3.5.
<superclass name="nc">
<subclass name="nc s"/>
<subclass name="nc p"/>
<subclass name="nc1"/>
<subclass name="nc2"/>
</superclass>
<superclass name="nc s">
<subclass name="nc1 s"/>
<subclass name="nc2 s"/>
</superclass>
<superclass name="nc1">
<subclass name="nc1 s"/>
<subclass name="nc1 p"/>
</superclass>
4.1. ELEMENTOS DA GRAMÁTICA
4.1.5
47
Preferências
As preferências, descritas pelo elemento preference, são um mecanismo que permite reduzir
o número de hipóteses de análise. Este tipo de regra permite seleccionar entre vários caminhos
possı́veis na análise. Os atributos prefmod e discmod, indicam o modelo que se prefere e o modelo
que se despreza (ver figura 4.1). O atributo confidance permite estabelecer qual o grau de confiança
da regra. Os restantes atributos são opcionais e limitam o contexto em que se aplica a restrição:
supmod indica o modelo dentro do qual se aplica, prevmod refere-se ao modelo anterior, word corresponde à palavra em análise e cat é a categoria que se está a analisar. Esta combinação de atributos
opcionais aumenta a flexibilidade e constitui uma melhoria em relação à gramática utilizada pelo
AF.
O atributo confidance pode ser utilizado para introduzir elementos probabilı́sticos na
gramática, a partir de observações em corpora. Este valor pertence ao intervalo
em que o
nı́vel de confiança equivale a dizer que a regra não tem qualquer valor. O nı́vel de confiança para a
preferência de um modelo sobre um modelo em determinado contexto, com base nas ocorr ências
em corpus, é definido como sendo
, com
o número de ocorrências do modelo nesse contexto. Note-se que se o valor obtido
se encontrar no intervalo , não se deve indicar uma preferência do modelo sobre o modelo
, mas sim do modelo sobre o modelo . Suponhamos que na análise de um corpus, em dado
contexto, a ocorrência de um modelo foi 80 e a ocorrência de um modelo foi 20. A preferência
do modelo sobre o modelo poderia ser definida com um grau de confiança .
- -
! "$#&%('*),+
./ $0
1
Os dois exemplos seguintes indicam duas preferências. O primeiro exemplo indica que, dentro de um modelo m nn (modelo nominal nuclear), o modelo nc1 p (nome comum singular) é preferı́vel ao modelo adj3 p (adjectivo do tipo 3 no plural)2 . O segundo exemplo indica que, dentro de
qualquer modelo, após ocorrer o modelo copv n (modelo de verbo copulativo nuclear), e quando a
classificação da palavra actual é todo p (pronome indefinido, plural), se prefere o modelo m nn ao
modelo m an2nq.
<preference prefmod="nc1 p" discmod="adj3 p" supmod="m nn" confidance="0.9"/>
<preference prefmod="m nn" discmod="m an2q" prevmod="copv n" cat="todo p"/>
A gramática utilizada pelo AF, define as preferências recorrendo a quatro tipos diferentes de
regras, de forma a contemplar os vários contextos de aplicação da preferência. Esta solução, além
de confusa, é também limitada, não suportando algumas restrições desejáveis. Por exemplo, para
indicar que se prefere uma categoria a outra em qualquer contexto, ou seja, dentro de qualquer modelo, utiliza-se o predicado pref cat ds mod e coloca-se um underscore3 no termo correspondente
ao modelo superior para que este possa ser instanciado com qualquer modelo. A gram ática do AF,
não permite, por exemplo, indicar a preferência de um modelo sobre o modelo , dentro de determinado modelo , tendo em consideração o modelo anterior , embora se possa indicar a preferência
de sobre em e a preferência de sobre após , caso sejam feitas independentemente. Na
gramática do SuSAna, as limitações mencionadas anteriormente encontram-se solucionadas.
2
2
3
3
2 (Hagège, 2000) refere que um adjectivo é do tipo 3, se puder ser núcleo de um sintagma nominal nuclear e não se puder
encontrar à esquerda de um núcleo nominal que qualifique. Exemplo: portuguesa.
3 O underscore em Prolog é utilizado como variável, que pode ser instanciada com qualquer elemento.
CAPÍTULO 4. GRAMÁTICA DO SUSANA
48
F
SN SV
F
Aux SN SV
F
SV
SN
det Nominal
Nominal
nome
Nominal
nome Nominal
SN
nomprop
SV
verbo
SV
verbo SN
Nominal
Nominal PP
Figura 4.2: Exemplo de uma mini-gramática em formato BNF.
4.2 Conversão de gramáticas
Como já foi anteriormente mencionado, a gramática desenvolvida, diverge das gramáticas livres de contexto usuais devido à possibilidade de representar preferências lexicais e hierarquias
para os modelos. A gramática permite mapear grande parte das restrições impostas pelas regras
de uma CFG nas estruturas dos blocos, obtendo assim uma gramática à qual poderá ser posteriormente adicionada uma hierarquia para os sı́mbolos e um conjunto de preferências lexicais. Note-se
contudo, que a conversão produzirá uma gramática que poderá não contemplar todas as restrições
da original, implicando assim que a transformação inversa possa não corresponder à original.
Seguidamente, são apresentados os aspectos relativos a conversões entre a gramática descrita
na secção anterior e uma gramática livre de contexto com notação BNF (Backus-Naur Form), utilizadas em grande parte das gramáticas. São descritos dois algoritmos que permitem efectuar essas
conversões.
4.2.1
Conversão de BNF para Blocos
O formato BNF (Naur et al., 1960) é frequentemente utilizado na representação de gramáticas.
O exemplo da figura 4.2, mostra uma mini-gramática retirada do exemplo do livro (Jurafsky e
Martin, 2000). O objectivo que se pretende é construir uma lista de regras com a estrutura dos
blocos, da forma apresentada na figura 4.3 para uma gramática deste tipo.
2 2 2 # # # 2 2
2 Considere-se uma qualquer regra escrita em notação BNF, então é da forma:
, com
um sı́mbolo não terminal e
, uma sequência de sı́mbolos terminais ou não.
A conversão da uma regra em notação BNF para a estrutura de blocos, consiste em percorrer cada
um dos elementos de
e construir ou actualizar o bloco correspondente à ocorrência do sı́mbolo
em . A estratégia consiste definir o bloco da forma mais restrita possı́vel e relaxar apenas quando
necessário.
2
2 2
2
O algoritmo 1 permite obter o resultado pretendido. O algoritmo pode também ser facilmente
, em que
estendido para tratar regras com expressões regulares do tipo
corres , em
ponde à ocorrência de pelo menos uma vez. O tratamento de casos do tipo
que
indica que ocorre zero ou mais vezes, exige a expansão prévia da regra, neste caso em duas
e
.
regras:
2 2
2
2 2 # # #2
2
2
2
2 2 2 ## #2
2 2 # # #2
2
2 2 2 2 ## #2
4.2. CONVERSÃO DE GRAMÁTICAS
Sı́mbolo
SN
SV
Aux
det
Nominal
nome
nomprop
verbo
SN
Nominal
PP
Superior
F
F
F
SN
SN
Nominal
SN
SV
SV
Nominal
Nominal
49
Começa
por vezes
por vezes
sempre
sempre
nunca
sempre
sempre
sempre
nunca
por vezes
nunca
Termina
nunca
sempre
nunca
nunca
sempre
por vezes
sempre
por vezes
sempre
nunca
sempre
Sı́mbolos Seguintes
SV
SN
Nominal
Nominal
SN
PP
Figura 4.3: Regras com a estrutura de blocos correspondente à mini-gramática.
Algoritmo 1 C ONVERTER B NF E M B LOCOS(gramática)
1. para cada regra da gramática fazer
2. para cada valor entre 1 e o número de elementos da sequência de
3.
C RIAR B LOCO( , )
Algoritmo 2 C RIAR B LOCO( ,
)
1. se Blocos contém um bloco do tipo em então
2. bloco Blocos.LerBloco( , )
3. se começa e bloco.NuncaComeça() então
4.
bloco.SetComeça(por vezes)
5. senão se não começa e bloco.ComeçaSempre() então
6.
bloco.SetComeça(por vezes)
7. se termina e bloco.NuncaTermina() então
8.
bloco.SetTermina(por vezes)
9. senão se não termina e bloco.TerminaSempre() então
10.
bloco.SetTermina(por vezes)
11. se não termina e não existe em bloco.Proximos() então
12.
bloco.AdicionarProximo( )
13. Blocos.Actualizar(bloco)
14. senão
15. se começa e acaba então
16.
Blocos.Adicionar bloco ( , , sim, sim, [])
17. senão se começa e não acaba então
18.
Blocos.Adicionar bloco ( , , sim, não, [ ])
19. senão se não começa e acaba então
20.
Blocos.Adicionar bloco ( , , não, sim, [])
21. senão se não começa e não acaba então
22.
Blocos.Adicionar bloco ( , , não, não, [ ])
fazer
CAPÍTULO 4. GRAMÁTICA DO SUSANA
50
Note-se que, embora seja possı́vel converter a informação presente na figura 4.2 para as estruturas dos blocos, o formato dos blocos não contempla todas as restrições da gramática original.
Podem ser utilizadas estratégias mais desenvolvidas para conseguir resultados mais aproximados.
4.2.2
Conversão de Blocos para BNF
Partindo de uma gramática descrita em termos de blocos, a dificuldade de representar a mesma
informação em notação BNF depende da complexidade da informação definida pelos blocos. A conversão da gramática da figura 4.3 resulta na gramática original (figura 4.2) e pode ser gerada utilizando o algoritmo 3.
Algoritmo 3 M APEAR B LOCOS E M B NF(
)
1. para cada bloco B em Blocos fazer
2. se B.PodeComeçar() então
3.
R CriarRegraBnf(B.superior()
B.modelo())
4.
se B.PodeTerminar() então
5.
Adicionar(gramática, R)
6.
se B.NãoTermina() ou B.TerminaPorVezes() então
7.
C OMPLETAR R EGRA B NF(Blocos, R, B)
Algoritmo 4 C OMPLETAR R EGRA B NF(
, )
,
1. para cada modelo N em B.seguintes() fazer
2. se Blocos.ExisteBloco(N, B.superior()) então
3.
B1 Blocos.ObterBloco(N, B.superior())
4.
se B1 pode não ocorrer no inı́cio então
5.
R.acrescentar(M)
6.
se B1.PodeTerminar() então
7.
Adicionar(gramática, B1)
8.
se B1.NãoTermina() ou B1.TerminaPorVezes() então
9.
C OMPLETAR R EGRA B NF(Blocos, R, B1)
2
Considere-se o caso em que
pode ocorrer dentro do modelo e ser seguido por ele próprio.
Em notação BNF conduzirá a situações do tipo
. Considere-se ainda
o caso mais genérico em que
e
podem ocorrer dentro do modelo com
a poder ser seguido
por
e por
, e
a poder ser seguido por
. Embora esta situação possa facilmente ser
indicada através das estruturas dos blocos, na notação BNF leva à criação de uma regra que envolve
expressões regulares:
. Estes problemas serão contemplados no contexto de trabalho
futuro, e implicam a criação de expressões regulares à medida em que se vão adicionando sı́mbolos à
sequência, verificando simultaneamente se a maior sequência se sı́mbolos previamente construı́da
é contemplada por uma expressão regular previamente construı́da.
2
2
# ## ## #
2
## #
# ##
4.3 Sumário
No âmbito desta tese foi concebida a estrutura de uma gramática, que serve fonte de informação
para analisador sintáctico SuSAna. A sua estrutura foi concebida de forma permitir descrever, pelo
4.3. SUMÁRIO
51
menos, toda a informação presente na gramática do AF. A informação para uma dada lı́ngua presente na gramática do AF, pode ser obtida a partir de um conjunto de propriedades, correspondentes
à formalização das caracterı́sticas linguı́sticas dessa lı́ngua, e que constituem o que se designou anteriormente por descrição da lı́ngua (secção 3.1). A estrutura da gramática do SuSAna comporta
três tipos de regras, que além de permitirem incorporar toda a informação do AF, suportam um
conjunto de restrições adicionais e permitem incluir elementos probabilı́sticos. À semelhança da
gramática do AF, é utilizada a estrutura bloco para definir o comportamento de modelos dentro
de modelos, com a diferença de permitir também definir o comportamento de categorias, ou modelos terminais. A gramática permite definir relações hierárquicas entre categorias e modelos, em
oposição com a gramática do AF, que apenas permite definir uma hierarquia para as categorias.
As preferências, utilizadas para efectuar restrições adicionais aos resultados, são indicadas por um
único tipo de regra, que permite por um lado, simplificar a manipulação da gramática e por outro,
suportar informação que não pode descrita usando a estrutura da gramática do AF. Relativamente à
gramática do AF, a gramática do SuSAna suporta um conjunto mais vasto de restrições permitindo
simultaneamente uma mais fácil manipulação da sua informação.
52
CAPÍTULO 4. GRAMÁTICA DO SUSANA
Um dos objectivos propostos para esta tese consiste na implementação de um analisador
sintáctico de superfı́cie. O tipo de resultados que se pretende obter com este analisador dever á
ser equivalente aos resultados obtidos pelo protótipo de análise de superfı́cie AF, apresentado no
capı́tulo anterior. Quando aplicado à análise de grandes quantidades de corpora, o AF apresenta
limitações, pois o seu processamento requer a realização de passos de pré-processamento, conseguidos à custa de um conjunto de scripts, e durante a sua concepção não foram considerados pormenores de optimização. De forma a resolver as limitações do AF, foi proposto o desenvolvimento de
um módulo de análise sintáctica de superfı́cie a que se deu o nome de SuSAna (Surface Syntactic
Analyser). O SuSAna integra um conjunto de algoritmos, concebidos no âmbito desta tese, com o
objectivo de efectuar uma análise eficiente e parametrizável.
Neste capı́tulo são abordados os requisitos impostos ao desenvolvimento do SuSAna; a estratégia que se seguiu para o seu desenvolvimento; e as suas caracterı́sticas principais. No que
diz respeito aos aspectos de utilização, a secção 5.2 descreve a informação que processa; tipos de
resultados que produz e formas de utilização. A secção 5.3 descreve aspectos relativos à forma
de funcionamento interno: a sua arquitectura e a estrutura de dados que manipula. A secç ão 5.4
descreve o processo de análise, apresentando os algoritmos utilizados e fazendo uma análise de complexidade da utilização desses algoritmos. A secção 5.5 aborda os aspectos relativos à extracção de
informação sobre segmentos previamente analisados e finalmente a secção 5.6 descreve o contexto
actual de utilização do módulo desenvolvido.
5.1 Objectivos e estratégia
O desenvolvimento do módulo SuSAna teve em linha de conta os seguintes requisitos:
1. Aplicação integrada. A identificação de constituintes sintácticos presentes num corpus, devidamente etiquetado ao nı́vel morfossintáctico, deve poder ser efectuada numa única operação
dependendo apenas da informação lexical disponı́vel na gramática em utilização;
2. Utilização isolada ou integrada em sistemas. A utilização da ferramenta de forma isolada permite a realização de estudos e testes, sobre informação previamente preparada para processamento sintáctico. Deve também ser contemplada a sua integração em cadeias ou sistemas de
processamento de lı́ngua natural que façam uso desse tipo de processamento;
3. Processamento de grandes quantidades de texto não restrito. O processamento de corpora
de grandes dimensões, em especial de texto não restrito, deve ser conduzido por algoritmos
54
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
robustos e eficientes. O tratamento de texto não restrito pode exigir aproximações diferentes
das utilizadas na análise sintáctica tradicional;
4. Possibilidade de utilização em diferentes plataformas. A portabilidade, neste caso, é um aspecto a ter em consideração no desenvolvimento da ferramenta de análise sintáctica. Este
requisito poderá, em parte, ser resolvido com a utilização de uma linguagem para a qual existam compiladores nas plataformas desejadas. A criação de módulos do tipo cliente/servidor,
que permitam fazer utilização do módulo de análise sintáctica em computadores designados
para essa tarefa, é também uma forma de aproximação a este problema;
5. Obtenção de diferentes tipos de resultados. Deverá ser proporcionado um conjunto de opções
que permita parametrizar a realização da análise e a forma como deverão ser extraı́dos os
resultados.
O desenvolvimento do SuSAna foi efectuado em várias fases, tendo sido definidos objectivos especı́ficos para cada uma delas.
A primeira fase consistiu em implementar uma versão do analisador sintáctico, utilizando um
algoritmo semelhante ao do AF, para processar o mesmo tipo e formato de dados e produzir o mesmo
conjunto de resultados. O objectivo a atingir foi o de poder comparar os resultados produzidos, compreender o funcionamento do algoritmo do AF e ficar a conhecer o conjunto de problemas associados
ao algoritmo. A aplicação tinha capacidade para ler o mesmo tipo e formato de informação, de
forma a poder utilizar os dados existentes. Depois de terminada, esta fase foi o ponto de partida
para as fases de desenvolvimento seguintes, pois além de permitir compreender o funcionamento
do algoritmo, deu também a conhecer um conjunto de problemas que lhe são inerentes.
A segunda fase compreendeu uma reformulação do tipo de regras da gramática, juntamente
com a sua passagem para o formato XML, e a concepção de um novo algoritmo. Embora podendo
continuar a usar as mesmas regras linguı́sticas e a analisar o mesmo tipo de documentos utilizados
pelo AF, o módulo foi alargado com capacidade de manipulação de dados em formato XML, dado que,
além de ser mais fácil de disseminar, a existência de bibliotecas de processamento já implementadas
facilita a gestão da informação neste formato. A passagem da informação para o formato XML levou
à adaptação e extensão das regras originais, conduzindo a um novo conjunto de regras mais genérico
e flexı́vel. O novo algoritmo passou a ter em consideração a realização de um conjunto de tarefas que
podem ser efectuadas com base na análise sintáctica, como é o caso da identificação das possı́veis
categorias morfossintácticas para uma palavra.
Numa terceira fase de desenvolvimento do SuSAna, dotou-se o algoritmo de conhecimento
acerca das análises parciais anteriormente calculadas, obtendo um aumento de desempenho, dado
que alguns dos cálculos passaram a ser feitos apenas uma vez. Em termos de arquitectura interna,
procedeu-se também a uma separação entre a fase da análise e a fase de extracção de resultados, de
forma a permitir um leque de opções independentes para a análise e para a extracção de resultados.
Finalmente, foram acrescentadas funcionalidades de forma a ser possı́vel a produção de variantes no tipo de resultados. A utilização do SuSAna foi alargada a uma plataforma cliente/servidor
através de RPC. Remote Procedure Call (RPC) é uma infra-estrutura cliente/servidor que permite a
inter-operabilidade, portabilidade, e flexibilidade de uma aplicação, permitindo que essa aplicação
possa estar distribuı́da sobre múltiplas plataformas heterogéneas (Rao, 1995; Birrell et al., 1984).
Para uma descrição mais completa, consultar o glossário na parte final desta tese.
5.2. ASPECTOS DE FUNCIONAMENTO
55
5.2 Aspectos de funcionamento
Esta secção descreve a utilização do módulo SuSAna, nomeadamente a informação que processa, o tipo de resultados produzidos e as formas de utilizaç ão.
5.2.1
Dados de entrada
De uma forma geral, o processamento de lı́ngua natural ao nı́vel sintáctico requer um processamento prévio ao nı́vel morfossintáctico. Esta tarefa começa geralmente por ser realizada por um
analisador morfológico ou anotador morfossintáctico, que recebendo um documento, lhe associa uma
informação morfossintáctica. A informação disponı́vel, embora com ambiguidade morfossintáctica,
pode ser já utilizada na análise sintáctica. Esta via conduzirá a um maior esforço de cálculo por
parte do analisador sintáctico e originará um conjunto mais alargado de hipóteses de análise. A outra alternativa é utilizar um desambiguador morfossintáctico para eliminar ou, pelo menos, reduzir
essa ambiguidade. A utilização do desambiguador morfossintáctico poderá também originar erros,
contribuindo assim para maiores taxas de erro no resultado final, razão pela qual deverá ser ponderada a sua utilização. A figura 5.1 mostra a cadeia de processamento linguı́stico que foi utilizada
em testes efectuados ao módulo.
Figura 5.1: Cadeia de processamento utilizada em testes com o SuSAna.
O passo final da preparação dos dados é a sua conversão para o tipo e formato adequado à
leitura por parte do analisador sintáctico. No caso da SuSAna, os dados de entrada consistem num
documento em formato XML constituı́do por zero ou mais segmentos, que são descritos de seguida.
O resultado produzido na etapa de processamento morfossintáctico contém toda a informação que o
analisador sintáctico necessita.
Geração da informação no formato do SuSAna
A conversão da informação obtida na fase da análise morfossintáctica, para o formato adequado
à leitura por parte do SuSAna, é facilitada pela existência de variadas ferramentas de manipulação
de XML. No caso concreto da cadeia de processamento da figura 5.1, a conversão do formato dos
resultados produzidos pelo módulo de pós-análise morfológica para o formato do SuSAna é feita
recorrendo à linguagem XSLT (W3C, 1999). Na figura 5.2 apresenta-se um excerto dos resultados
produzidos pelo módulo de pós-análise morfológica; na figura 5.3 é apresentado o excerto anterior,
já no formato adequado à leitura, por parte do SuSAna; e na figura 5.4 apresenta-se o código XSLT
utilizado para realizar esta conversão.
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
56
<?xml version="1.0" encoding="iso-8859-1"?>
<!DOCTYPE pasmo-out SYSTEM "PAsMo-out.dtd">
<pasmo-out>
<phrase num="1">
<hypothesis num="1">
<word name="a">
<class root="o"> <id name="artd s"/> </class>
<class root="a"> <id name="prep"/> </class>
<class root="a"> <id name="cli ac"/> </class>
</word>
<word name="água">
<class root="água"> <id name="nc1 s"/> </class>
<class root="aguar"> <id name="vc"/> </class>
</word>
<word name="gela">
<class root="gelar"> <id name="vc"/> </class>
<class root="gelar"> <id name="eliminer"/> </class>
</word>
<word name="em">
<class root="em"> <id name="prep"/> </class>
</word>
<word name="os">
<class root="o"> <id name="artd p"/> </class>
</word>
<word name="carreiros">
<class root="carreiros"> <id name="nc1 p"/> </class>
<class root="carreiros"> <id name="adj3 p"/> </class>
</word>
<word name=".">
<class root="."> <id name="eliminer"/> </class>
</word>
</hypothesis>
</phrase>
</pasmo-out>
Figura 5.2: Classificação morfossintáctica da frase “A água gela nos carreiros”, tal como se encontra
à saı́da do módulo de pós-análise morfológica PaSMo.
Estrutura dos segmentos
Os segmentos são as estruturas mais elementares que se podem analisar com o SuSAna. O
processamento sintáctico de um corpus, ou simplesmente de um documento, requer a sua divisão
em segmentos, de forma a que a análise seja feita segmento a segmento. Como se pode observar
na definição do tipo de dados (DTD) apresentada na figura 5.5 , cada segmento é composto por
uma ou várias hipóteses ou alternativas de sequências de unidades lexicais. Cada hipótese de
segmento é uma sequência de unidades lexicais anotadas morfossintacticamente. Uma unidade
lexical corresponde a uma ou mais palavras juntamente com a sua classificaç ão, como é o caso das
palavras compostas. A classificaç ão de cada unidade lexical pode ser ambı́gua, tal como se verifica
no exemplo da figura 5.3.
A definição de um segmento como um conjunto de hipóteses, permite indicar várias formas
5.2. ASPECTOS DE FUNCIONAMENTO
57
<?xml version="1.0" encoding="iso-8859-1"?>
<!DOCTYPE MorphoAnalysis SYSTEM "susana-in.dtd">
<MorphoAnalysis>
<segment>
<hypothesis>
<word name="a">
<category lemma="o" tag="artd s"/>
<category lemma="a" tag="prep"/>
<category lemma="a" tag="cli ac"/>
</word>
<word name="água">
<category lemma="água" tag="nc1 s"/>
<category lemma="aguar" tag="vc"/>
</word>
<word name="gela">
<category lemma="gelar" tag="vc"/>
<category lemma="gelar" tag="eliminer"/>
</word>
<word name="em">
<category lemma="em" tag="prep"/>
</word>
<word name="os">
<category lemma="o" tag="artd p"/>
</word>
<word name="carreiros">
<category lemma="carreiros" tag="nc1 p"/>
<category lemma="carreiros" tag="adj3 p"/>
</word>
<word name=".">
<category lemma="." tag="eliminer"/>
</word>
</hypothesis>
</segment>
</MorphoAnalysis>
Figura 5.3: Classificação morfossintáctica da frase “A água gela nos carreiros”. Informação no
formato adequado à leitura do SuSAna.
de segmentação de uma frase em unidades lexicais, por exemplo a frase “a cerca de ...” pode ser
segmentada de duas formas distintas: [a cerca][de] e [a][cerca][de]. A figura 5.3 mostra o exemplo
de um segmento constituı́do apenas por uma hipótese.
5.2.2
Resultados produzidos
O resultado da análise de um segmento é a classificação sintáctica das sequências de unidades
lexicais que compõem esse segmento, e corresponde à identificação de uma estrutura linguı́stica
abrangida por esse segmento. Por exemplo, considerando que um segmento corresponde a um
parágrafo, as estruturas linguı́sticas que se poderiam aı́ identificar poderiam ser: parágrafo; frase;
ou qualquer elemento contemplado pela gramática, por exemplo SN (sintagma nominal) , SV (sintagma verbal), ou mesmo V (verbo). Um segmento deve conter pelo menos uma das estruturas
linguı́sticas do tipo que se pretende analisar. Por omissão, o SuSAna considera que cada segmento
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
58
<?xml version=’1.0’ encoding=’iso-8859-1’ ?>
<xsl:stylesheet
xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="1.0">
<xsl:output method="xml" encoding="iso-8859-1"
doctype-system="susana-in.dtd"/>
<xsl:template match="/pasmo-out">
<MorphoAnalysis>
<xsl:apply-templates/></MorphoAnalysis></xsl:template>
<xsl:template match="phrase">
<segment><xsl:apply-templates/></segment></xsl:template>
<xsl:template match="hypothesis">
<hypothesis><xsl:apply-templates/></hypothesis></xsl:template>
<xsl:template match="word">
<word><xsl:attribute name="name"><xsl:value-of select="@name"/>
</xsl:attribute><xsl:apply-templates/></word></xsl:template>
<xsl:template match="class">
<category>
<xsl:attribute name="lemma"><xsl:value-of select="@root"/>
</xsl:attribute>
<xsl:attribute name="tag"><xsl:value-of select="id/@name"/>
</xsl:attribute>
</category>
</xsl:template>
</xsl:stylesheet>
Figura 5.4: XSL que converte a saı́da do módulo de pós-análise morfológica na entrada do SuSAna.
corresponde a uma e uma única estrutura linguı́stica do tipo que se pretende analisar. Contudo,
aceita um conjunto de opções que lhe permitem realizar a análise de diversas formas, sendo uma
delas a possibilidade de considerar que um segmento pode conter múltiplas estruturas linguı́sticas.
Neste caso o analisador tenta descobrir os seus limites dentro desse segmento.
O tipo e formato dos resultados pode também ser definido através de opções. Em termos de
formato, de uma forma geral os resultados podem consistir em simples contagens, demarcações, estruturas representadas em formato XML, ou num formato adequado à representação da informação
em grafos. A figura 5.6 apresenta o resultado da análise em formato XML, para o segmento da figura
5.3. É possı́vel também gerar um conjunto de alternativas para as unidades que podem ocorrer após
um dado segmento, partindo do princı́pio que o segmento não constitui uma estrutura linguı́stica
completa.
5.2.3
Formas de utilização
Paralelamente à implementação do SuSAna, foi desenvolvida uma aplicação que permite a
utilização do SuSAna de forma isolada. Esta aplicação consiste num pequeno programa que sendo
executado numa linha de comandos, realiza chamadas ao módulo SuSAna e permite realizar todos
os tipos de operação suportados pelo módulo.
O módulo SuSAna foi implementado como uma classe na linguagem de programação C++. Esta
caracterı́stica permite que se possa incluir e utilizar dentro de outros sistemas e aplicaç ões. A sua
utilização é feita através da sua interface de programação (API).
5.3. FUNCIONAMENTO INTERNO
59
<?xml version=’1.0’ encoding=’iso-8859-1’?>
<!ELEMENT MorphoAnalysis (segment)*>
<!ELEMENT segment (hypothesis)*>
<!ELEMENT hypothesis (word)*>
<!ELEMENT word (category)*>
<!ATTLIST word name CDATA #REQUIRED>
<!ELEMENT category EMPTY>
<!ATTLIST category lemma CDATA #REQUIRED tag CDATA #REQUIRED>
Figura 5.5: DTD dos elementos processados pelo SuSAna.
Para permitir a utilização da SuSAna numa plataforma cliente/servidor, foi implementado um
módulo cliente de RPC que permite a utilização da SuSAna em máquinas dedicadas, a partir de
qualquer máquina. A figura 5.8 mostra a utilização do módulo SuSAna numa plataforma cliente/servidor. A instalação e utilização do módulo cliente de RPC em diferentes plataformas é
facilitada pela sua reduzida complexidade e dimensão. O módulo cliente de RPC pode também ser
incluı́do em sistemas mais complexos de processamento da lı́ngua que façam uso do processamento
sintáctico.
5.3 Funcionamento interno
Considere-se a árvore sintáctica correspondente a uma análise. Ao longo desta secção será
designado por fragmento de análise, toda e qualquer estrutura da análise que possa ser obtida a
partir de um nó dessa árvore e que inclua todos os nós abaixo desse nó. Tal como se encontra
definido, um fragmento é sempre a concretização de um modelo definido pela gramática. A noção
de fragmento aqui introduzida é desprovida de uma noção linguı́stica, na medida em que depende
única e exclusivamente do conjunto de regras que se utiliza para realizar a análise. Contudo a
sequência de elementos que o constitui é sempre permitida pelas regras que definem o modelo que
lhe está associado. A figura 5.9 mostra duas análises possı́veis para o segmento “A água gela em os
carreiros”. Verifica-se que a primeira análise é composta pelos fragmentos m nn, phvn, m prepn e
a segunda é composta pelos fragmentos m prepn, phvn, m prepn, sendo os dois últimos fragmentos
partilhados pelas duas análises.
Esta secção apresenta a arquitectura adoptada para o módulo de análise de superfı́cie e a estrutura que permite, por um lado, armazenar o resultado da análise, e por outro, fornecer informação
acerca de cálculos efectuados previamente, de modo a permitir um processo de análise mais eficiente.
5.3.1
Arquitectura
A obtenção do resultado de uma análise é feita em duas etapas, podendo cada uma delas ser
parametrizada com um conjunto de opções. A primeira etapa, corresponde à análise propriamente
dita e consiste em produzir um conjunto de resultados intermédios. A segunda, corresponde a
extrair os resultados pretendidos a partir dos resultados intermédios, previamente calculados.
60
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
<?xml version="1.0" encoding="iso-8859-1"?>
<!DOCTYPE surfaceAnalysis SYSTEM "susana-out.dtd">
<surfaceAnalysis>
<segment>
<!-- A água gela em os carreiros -->
<hypothesis length="6">
<analysis weight="0" start="0" length="6">
<model name="ph" start="0" length="6">
<model name="m nn" start="0" length="2">
<model name="artd s" start="0" length="1">A</model>
<model name="nc1 s" start="1" length="1">água</model>
</model>
<model name="phv n" start="2" length="1">
<model name="vc" start="2" length="1">gela</model>
</model>
<model name="m prepn" start="3" length="3">
<model name="prep" start="3" length="1">em</model>
<model name="artd p" start="4" length="1">os</model>
<model name="nc1 p" start="5" length="1">carreiros</model>
</model>
</model>
</analysis>
<analysis weight="0" start="0" length="6">
<model name="ph" start="0" length="6">
<model name="m prepn" start="0" length="2">
<model name="prep" start="0" length="1">A</model>
<model name="nc1 s" start="1" length="1">água</model>
</model>
<model name="phv n" start="2" length="1">
<model name="vc" start="2" length="1">gela</model>
</model>
<model name="m prepn" start="3" length="3">
<model name="prep" start="3" length="1">em</model>
<model name="artd p" start="4" length="1">os</model>
<model name="nc1 p" start="5" length="1">carreiros</model>
</model>
</model>
</analysis>
</hypothesis>
</segment>
</surfaceAnalysis>
Figura 5.6: Análise sintáctica da frase “A água gela em os carreiros”.
Figura 5.7: Utilização do SuSAna como módulo inserido num sistema de processamento de lı́ngua.
5.3. FUNCIONAMENTO INTERNO
61
Figura 5.8: Utilização do SuSAna numa plataforma cliente/servidor através de RPC.
Figura 5.9: Árvores de análise da frase: “A água gela em os carreiros”.
A figura 5.10 apresenta a arquitectura geral do sistema. O tipo de arquitectura apresentado
segue uma abordagem modular, na qual o módulo de análise e o módulo de extracção de resultados são independentes. O módulo de análise coloca elementos no repositório, que utiliza também
posteriormente no decorrer da análise, de forma a evitar duplicação de cálculos. Por seu lado, o
módulo de extracção utiliza o repositório como fonte de informação, extraindo daı́ toda a informação
necessária à produção do resultado desejado. Este tipo de abordagem facilita a correcção de problemas e a introdução de melhorias, tanto na etapa da análise, como na etapa de extracção de
resultados.
5.3.2
Repositório
A figura 5.11 mostra os tipos de dados que constituem a estrutura do repositório. O repositório
é configurado e limpo no inı́cio da análise de cada frase. O vector de informação do repositório é
dimensionado de forma a que seja constituı́do por tantas posições quantas forem as unidades lexicais presentes na frase. A informação presente em cada posição do vector do repositório, designada
por informação posicional, relaciona-se com a unidade lexical que se encontra nessa posiç ão. Toda
a informação relativa à unidade lexical, tal como as possı́veis classificações morfossintácticas, é armazenada no repositório, de forma a que a tarefa de extracção de resultados possa ser efectuada
apenas com base na informação aı́ presente.
62
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
Figura 5.10: SuSAna – arquitectura interna.
De forma a impedir a duplicação de cálculos, o repositório mantém um historial das tentativas
efectuadas, no sentido de criar informação para um dado modelo. A informação indicada como
modelos testados contém uma lista de todos os modelos testados para a unidade lexical actual, onde
se indica se um determinado modelo já testado pode ou não ocorrer na posição actual. No caso de
poder ocorrer, indica-se também o caso especial, do modelo ser ou não terminal (por questões de
eficiência).
A informação relativa aos fragmentos válidos da análise é guardada na estrutura de um grafo
dirigido e acı́clico (DAG). Assim, cada posição do repositório contém arcos para os vértices do grafo
que ocorrem nessa posição. Um arco pode ter um custo associado e tem a propriedade de poder estar
ou não activo, sendo que um arco desactivado corresponde a um arco eliminado. Um arco pode ser
desactivado quando é encontrado um caminho alternativo no grafo que oferece melhores condições,
isto é, se existir um caminha cujo custo é inferior. A possibilidade de desactivar arcos proporciona
um meio de reduzir cálculos posteriores.
Cada vértice do grafo retém informação acerca da ocorrência de um modelo dentro de outro
(designado por modelo superior), um vector de arcos para os vértices que o podem seguir nesse nı́vel
da análise e um vector de arcos para as sub-estruturas, de nı́veis inferiores, das quais depende.
Para todos os vértices, é também guardada informação acerca dos possı́veis fechos posteriores e da
melhor relação custo/benefı́cio, explicada na próxima secção, para chegar a determinada posição.
5.4 O processo de análise
O resultado produzido pelo analisador de superfı́cie consiste num conjunto de hipóteses de
análise, em que cada hipótese é representada por uma árvore. O nó de topo de cada uma dessas
árvores corresponde ao sı́mbolo inicial da gramática e as folhas correspondem às classificações morfossintácticas atribuı́das previamente à frase em análise. Todos os nós representam fragmentos de
análise, sendo que o nó de topo representa o maior fragmento possı́vel e as folhas representam os
menores fragmentos possı́veis. O processo de análise consiste em calcular fragmentos e sequências
de fragmentos que são permitidos pela gramática. A representação do conjunto de árvores em
memória é feita através de um DAG, de modo a construir o número mı́nimo de vértices.
O núcleo da análise de superfı́cie é composto por duas funções, que são responsáveis por atribuir a classificação adequada aos dados presentes na entrada. O processamento que cada uma
5.4. O PROCESSO DE ANÁLISE
63
Figura 5.11: Estrutura do repositório de dados.
delas efectua é descrito nos algoritmos 5 e 6. A função C ALC -M ODELS é responsável por calcular
todos os modelos de um tipo T que se podem iniciar na posição w do segmento em análise. G ETS IBLING -M ODELS calcula e devolve todas as sequências de modelos que podem ocorrer a partir da
posição w do segmento, após a ocorrência de um fragmento L e dentro de um modelo T. As funções
C ALC -B RANCHES e C ALC -D AG -V ERTICE, descritas no algoritmos 7 e 8, poderiam ser integradas
numa única função e incluı́das dentro dos algoritmos anteriores, sendo no entanto definidas separadamente para uma melhor clareza. A função C ALC -B RANCHES é responsável por seleccionar os
caminhos seguintes possı́veis e aplicar o custo a cada um deles, em função das preferências presentes na gramática. Finalmente, a função C ALC -D AG -V ERTICE é responsável por criar os nós do
DAG e estabelecer as relações entre esses nós. A Figura 5.12 mostra as relações que se estabelecem
e o tipo de operações que cada uma delas realiza. As funções funcionam recursivamente de forma
cruzada, isto é, a primeira e a segunda chamam a terceira; a terceira por sua vez chama a primeira
e a quarta; e a quarta chama a segunda.
5.4.1
Criação de novos fragmentos
No que diz respeito ao algoritmo C ALC -M ODELS, a sua função é calcular todos os fragmentos
de análise de um tipo que podem ser iniciados numa posição da frase. A função C ALC -M ODELS
64
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
Figura 5.12: Diagrama de funcionamento da análise.
(algoritmo 5 ) começa por verificar se o problema já foi antes considerado ou se a sua solução é trivial
(no caso de ser uma das classificaç ões da palavra); se isso não acontecer, constrói um conjunto de
modelos candidatos a constituir fragmentos de análise dentro do modelo . Com base no conjunto
de modelos candidatos, procede com a tentativa de criação de ramos de análise para cada um deles.
As primeiras duas linhas do algoritmo verificam, através de uma consulta ao repositório, se
o problema foi já antes considerado, mesmo que não tenha produzido resultados. O repositório
mantém esta informação na estrutura que se designou por modelos testados (ver figura 5.11), independente da estrutura do DAG, e que se pode eliminar após efectuar toda a análise. As três linhas
seguintes verificam o caso trivial de uma das classificaç ões atribuı́das a uma palavra ser igual a
um modelo . No caso de isso acontecer, é enviada informação para o repositório e a execução termina. As linhas 6 a 8, criam o conjunto de modelos que podem começar um modelo numa posiç ão
da frase e que fazem parte de um caminho descendente até uma das possı́veis classificações da
unidade lexical actual.
A função GetStartingChildModels devolve, com base na gramática, o conjunto de modelos que
se encontram no primeiro passo do caminho descendente que vai desde um modelo a outro, usando
uma estratégia bottom-up, adequada à estrutura das regras presentes na gramática. A procura
de caminhos efectuada pela função é ilustrada pela figura 5.13 . Nos vários passos apresentados,
a figura mostra como se seleccionam os modelos que podem ocorrer directamente em e fazem
parte de um dos caminhos que vai de até ao conjunto de categorias
,
e
(que também
são modelos). No inı́cio da procura conhecem-se apenas ,
,
e
. Partindo de uma das
categorias, identificam-se os elementos onde a categoria pode ocorrer e, recursivamente, os modelos
onde os modelos acabados de encontrar podem ocorrer, até encontrar . Procede-se da mesma
forma com as restantes categorias. O resultado de getStartingChildModels é o conjunto de modelos
que fazem parte dos caminhos construı́dos e se encontram imediatamente abaixo de , no exemplo
e .
apresentado seria o conjunto formado pelos modelos
5.4. O PROCESSO DE ANÁLISE
65
Algoritmo 5 C ALC -M ODELS( , )
1. if position of repository knows model
2. return repository.IsPossible(
)
then
3. if some category of word matches then
4. repository.AddTerminalModel( , )
5. return success
in segment[ ].categories() do
grammar.GetStartingChildModels( CALC -B RANCHES(
, )
if empty( ) then
repository.SetImpossible( )
6.
7. for each category
8.
9.
)
10.
11.
12. return not found
13. else
)
14. ApplyPreferences(
)
15. ApplyLongPrinciple(
16. repository.SetPossible(
)
17. return success
Figura 5.13: Procura de possı́veis caminhos entre modelos.
Após terem sido identificados os modelos possı́veis, a função C ALC -B RANCHES verifica se, para
cada um deles, é possı́vel construir um fragmento de análise (linha 9 do algoritmo 5). Este teste
tem já em consideração as palavras seguintes da frase. Como resultado da função são armazenados
na estrutura , um conjunto de arcos que indicam o conjunto de vértices do grafo que iniciam
um fragmento de análise do tipo de um modelo . A linhas 14 e 15 permitem não considerar alguns
fragmentos produzidos, de forma a reduzir o número de análises final. A aplicação de preferências
é efectuada com base nos custos atribuı́dos pela função C ALC -B RANCHES, descrita no algoritmo 7,
enquanto que a aplicação do princı́pio dos modelos mais longos apenas depende do número de nós
usados para chegar a dada posição. Note-se que esta operação pode reduzir o número de elementos
do conjunto mas não os elimina completamente, havendo ainda a garantia de se manterem as
condições para encontrar análises válidas. As últimas linhas do algoritmo informam o repositório
acerca da possibilidade de existirem fragmentos do tipo de um modelo . Esta informação será
novamente utilizada nas primeiras duas linhas deste algoritmo, aquando da tentativa de realizaç ão
de um cálculo com os mesmos parâmetros. Este mecanismo reduz o tempo de execução, na medida
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
66
em que assegura que o mesmo cálculo não é efectuado mais do que uma vez. Note-se que a função
C ALC -M ODELS, sendo responsável por criar fragmentos de análise, é executada repetidamente pois
a realização da análise assenta na construção de fragmentos.
5.4.2
Continuação de fragmentos já iniciados
O algoritmo G ET-S IBLING -M ODELS é responsável por prever e calcular os fragmentos de
análise que podem ocorrer, após um determinado fragmento e dentro de um determinado modelo.
Por oposição à função C ALC -M ODELS, que é utilizada para descer no nı́vel da análise (em direcção
às caracterı́sticas morfossintácticas da palavra), a função G ET-S IBLING -M ODELS (algoritmo 6 ) é
Algoritmo 6 G ET-S IBLING -M ODELS( , , )
in segment[ ].categories() do
grammar.GetNextSiblingModels( CALC -B RANCHES(
, , , )
return 1.
2. for each category
3.
4.
5.
, )
utilizada para prosseguir a análise ao mesmo nı́vel em direcção ao fim da frase. A ideia subjacente a
estes dois algoritmos é que enquanto um executa uma procura orientada em profundidade, o outro
procede com uma procura em largura. Por um lado, o avanço num determinado nı́vel da análise
nunca acontece sem terem sido explorados os nı́veis inferiores dependentes desse nı́vel, e por outro,
nunca se sobe de nı́vel num dado ponto da análise sem terem sido exploradas todas as possibilidades
nesse nı́vel, para esse ponto.
As primeiras três linhas do algoritmo têm uma tarefa semelhante às linhas 3 a 6 do algoritmo
5. A diferença está no facto de se considerar o modelo anterior (
), que funciona como um factor
de restrição. A função getNextSiblingModels devolve o conjunto de modelos que pode ocorrer no
modelo , após um modelo , e que façam parte do conjunto de modelos que constituem a primeira
etapa nos caminhos possı́veis entre o modelo e as classificações morfossintácticas da palavra. A
linha 4 corresponde à linha 9 do algoritmo 5, contudo entra também em consideração com o modelo
anterior .
5.4.3
Validação de modelos candidatos e atribuição de custos
As linhas 1 a 7 da função C ALC -B RANCHES (algoritmo 7 ) são responsáveis por validar os
modelos seleccionados como candidatos por um dos algoritmos anteriores. O procedimento consiste
em, para cada um dos modelos candidatos, verificar se existem fragmentos que possam ocorrer
dentro desse modelo. Se isso acontecer, constrói um vértice no grafo e obtém uma referência para
esse vértice. A construção do vértice implica, como será visto adiante, a construção ou verificação
(caso já tenham sido construı́dos) dos vértices que podem seguir esse vértice, até formar o resto
corresponder ão a alternativas
dos fragmentos. Assim, os arcos armazenados no conjunto válidas para o fragmento em construção.
As linhas 8 a 15 são responsáveis por atribuir custos aos caminhos encontrados nas linhas
anteriores, partindo do princı́pio que se estão a considerar as preferências. Cada preferência da
5.4. O PROCESSO DE ANÁLISE
Algoritmo 7 C ALC -B RANCHES(
67
, , )
1.
do
2. for each model in
3. if repository.IsUnknown( , ) then
4.
C ALC -M ODELS( , )
5. if repository.IsValid( , ) then
G ET-D AG -V ERTICE( , , )
6.
7.
.Add(new Edge( ) )
) 1 then
8. if using preferences and size(
9. for each in
do
10.
for each in
following do
11.
if exists preference( , ) then
12.
incCost( , (preference( , ) + 1)/2)
13.
incCost( , 1 - (preference( , )+1)/2)
14. return
gramática indica a possibilidade de rejeitar determinado caminho, na presença de outro: assim,
os caminhos são testados dois a dois. É importante observar que nesta fase não são eliminados
caminhos: apenas são classificados com custos. Isto acontece, porque um caminho sem custos pode
não levar necessariamente a uma análise final válida. Estes custos serão posteriormente utilizados
na função C ALC -M ODELS (algoritmo 5) e na ordenação do resultado final.
5.4.4
Registo de caminhos e vértices no repositório
Tal como foi visto anteriormente, cada vértice que constitui o DAG suportado pela estrutura
do repositório, representa a possibilidade de ocorrência de um modelo noutro. A existência de um
vértice no grafo implica que toda a informação após esse vértice já foi calculada e é conhecida por
esse vértice. As primeiras duas linhas da função G ET-D AG -V ERTICE (algoritmo 8 ), limitam-se a
Algoritmo 8 G ET-D AG -V ERTICE( ,
1. if repository.ExistsInfo( , )
2. return repository.GetInfo( ,
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
)
, )
Not grammar.MustClose(
, )
grammar.CanClose( , )
grammar.CanStart( , )
repository.GetChilds( )
MaxLength( ) new Vertice( , , , , )
and + segment.Size() then
if for downto 1 do
if repository[ "
!# ].CanBeClosedBy( ) then
$ G ET-S IBLING -M ODELS(%
, , )
if Not Empty (
$ ) then
AddSiblings( , $ )
repository.AddVertice( )
return 68
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
verificar essa situação. A construção do vértice que representa a ocorrência de um modelo
dentro de um modelo é efectuada na linha 8. O vértice acabado de criar tem informação acerca
da possibilidade de poder começar e terminar um fragmento de análise. Como se pode verificar,
o vértice tem também conhecimento dos fragmentos com que é constituı́do. A existência destes
fragmentos é garantida na linha 5 da função C ALC -B RANCHES (algoritmo 7). O conjunto dos fragmentos está também armazenado num ou mais sub-grafos e cada uma delas pode ter tamanhos
diferentes.
As linhas 9 a 14 são responsáveis por identificar todos os vértices que podem seguir o vértice
acabado de criar. Assim, partindo do tamanho do maior sub-fragmento, a função G ET-S IBLING M ODELS (algoritmo 6) será novamente utilizada a partir da posição seguinte. No caso de terem sido
identificados caminhos possı́veis, essa informação é introduzida no vértice acabado de criar (linha
14). Uma nota importante é consequência do facto da procura começar a ser efectuada a partir
do elemento mais distante. Através deste mecanismo, o algoritmo poderia ser utilizado como um
algoritmo anytime (Russell e Zilberstein, 1991; Gorz e Kesseler, 1994) , pois a sua estrat égia consiste
em encontrar o maior conjunto de análises finais válidas, com o menor número de operações. A
produção de todos os resultados possı́veis e respectivo refinamento é efectuado progressivamente
em função do tempo disponı́vel.
5.4.5
Parametrizações da análise
A arquitectura representada na figura 5.10 mostra uma separação entre a fase de análise e a
fase de extracção de resultados, permitindo estabelecer parâmetros independentes em cada uma
dessas fases. Seguidamente, indicam-se os parâmetros que condicionam a fase de análise.
A análise de um segmento no SuSAna envolve um conjunto de parâmetros que define o tipo
de análise pretendida, nomeadamente:
, que corresponde à estrutura linguı́stica que se pre tende analisar;
, que indica a possibilidade de ignorar unidades lexicais que não permitam
a realização da análise;
, que indica a possibilidade de existirem múltiplas estruturas
linguı́sticas no segmento;
, que permite a sobreposição de resultados e é somente aplicado
no caso do parâmetro
se encontrar activo.
O algoritmo 9 mostra o processo de análise tendo em conta os parâmetros definidos. O inı́cio
de uma análise envolve a iniciação do repositório (linha 1). As linhas 2, 42 e 43 permitem fazer o
controlo de erros, sobretudo quando existem modelos desconhecidos no segmento. No caso de uma
ocorrência desse tipo, a análise do segmento actual é interrompida de forma a iniciar a análise
do próximo segmento. O processo de análise mais simples é realizado no caso das opções
e
não se encontrarem activas, consistindo apenas em realizar a análise na primeira posição
do segmento e verificar se o resultado obtido engloba todas as posições desse segmento. Nos restantes casos de parametrização, o comportamento do algoritmo consiste em realizar a análise na
primeira posição do segmento, verificar o tamanho do maior resultado obtido, e em função desse
tamanho decidir qual a posição a analisar de seguida, terminando eventualmente a análise.
5.4. O PROCESSO DE ANÁLISE
Algoritmo 9 D O-A NALYSIS(
69
,
,
,
,
)
1. Init(repository, segment)
2. try
and then
3.
if and 4.
for i = 1 to size(segment) do
5.
C ALC -M ODELS( )
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
else if and and not then
1
while size(segment) do
1
C ALC -M ODELS( )
if sucess then
repository.maxlen( , )
+ else if not and and not then
1
size(segment) do
while C ALC -M ODELS( )
if not sucess then
return fail
+ repository.maxlen( , )
else if not and and then
1
0
while size(segment) do
C ALC -M ODELS( )
if success then
Max( , + repository.maxlen( , else if then
return fail
+ 1
else if and not then
1
true
while and size(segment)
C ALC -M ODELS( )
if success then
false
else
+1
else if not and not C ALC -M ODELS(1, )
42. catch(error)
43. ReportError()
then
))
70
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
Figura 5.14: Análise de segmentos com múltiplas estruturas linguı́sticas, sem sobreposição e sem
possibilidade de desprezar unidades lexicais.
Elemento de topo (topmodel)
Em termos de análise, o elemento de topo corresponde à estrutura linguı́stica que se pretende
identificar. O seu valor por omissão é definido na gramática através do elemento topmodel, sendo,
contudo, possı́vel alterar o seu valor em tempo de execução.
Possibilidade de desprezar unidades lexicais (skips)
Por vezes, a demarcação de segmentos não é fiável. Nesse caso, poderá existir informação que
impede a obtenção de uma análise correcta, tanto no inı́cio como no fim do segmento. O SuSAna
pode ser parametrizado para ignorar elementos que não permitam começar a estrutura a analisar
e elementos finais que a não permitam concluir. Na função D O -A NALYSIS (algoritmo 9), esta opção
é indicada no parâmetro
. A utilização desta opção poderá levar à obtenção da análise para
apenas uma pequena parte do segmento.
Análise de múltiplas estruturas linguı́sticas contidas num segmento (multiple)
Por omissão, cada segmento deverá conter uma e uma só estrutura linguı́stica do tipo definido
pelo elemento de topo. Contudo, é possı́vel contemplar o caso de um segmento conter mais do que
uma dessas estruturas. Esta situação ocorre, por exemplo, quando o segmento corresponde a um
parágrafo e se pretendem analisar frases dentro desse parágrafo.
O processo de análise utilizando esta opção é realizado com a opção
e depende também
da utilização das opções
e
, tal como se pode observar no algoritmo 9. Quando utilizada
, a opção
corresponde à possibilidade de desprezar unidades
em conjunto com a opção
lexicais que antecedem ou seguem estruturas linguı́sticas pretendidas, isto é, que se encontrem no
meio dessas estruturas. A opção
permite indicar que as estruturas linguı́sticas se podem
sobrepor.
A figura 5.14 representa o processo de análise de um segmento, sem possibilidade de desprezar
unidades lexicais e sem sobreposição de resultados. Cada linha vertical efectua a demarcação de
uma ou várias unidades lexicais. Tal como se pode verificar na função D O -A NALYSIS (algoritmo 9),
depois de terem sido calculados os fragmentos que se iniciam na primeira posiç ão do segmento, o
5.4. O PROCESSO DE ANÁLISE
71
Figura 5.15: Análise de segmentos com múltiplas estruturas linguı́sticas, com sobreposição e sem
possibilidade de desprezar unidades lexicais.
Figura 5.16: Análise de segmentos com múltiplas estruturas linguı́sticas, com possibilidade de
desprezar unidades lexicais.
próximo cálculo será efectuado na posição , sendo
calculado.
o comprimento do fragmento mais comprido já
A análise de múltiplas estruturas num segmento poderá também ser efectuada com sobreposição
de possibilidades (
). A figura 5.15 ilustra este processo. Neste caso foi estabelecido que n ão
se deveriam desprezar unidades lexicais no segmento.
A possibilidade de desprezar unidades lexicais num segmento, com múltiplas estruturas do tipo
é ilustrada na figura 5.16 . De notar que este conjunto de opções em conjunto com a opção
obrigará ao cálculo de fragmentos do tipo
, para todas as posições do segmento.
5.4.6
,
,
Restrição de resultados
A análise sintáctica de um segmento pode ser constituı́da por múltiplas alternativas. No caso
particular de utilização de gramáticas de dimensão reduzida, com regras pouco refinadas, é necessário estabelecer regras suficientemente genéricas para permitir o maior número de construções
da lı́ngua, o que poderá originar um vasto conjunto de análises possı́veis. No que diz respeito ao
DAG utilizado para a análise, a adição de arcos entre vértices corresponde à produção de alternativas de análise. Durante o processo de passagem do grafo para árvores, que designamos por
linearização, cada arco alternativo poderá dar origem a um vasto conjunto de árvores, sendo cada
uma dessas árvores uma alternativa de análise. Quer o resultado final seja um grafo representativo
da estrutura da análise, quer seja um conjunto de árvores, cada uma delas constituindo uma alternativa de análise, é importante anotar ou eliminar um conjunto de possibilidades mais improváveis
ou incomuns. As técnicas de restrição de análises não limitam a cobertura e permitem estabelecer um conjunto de análises mais reduzido. O SuSAna faz uso de dois métodos para atingir esse
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
72
b
0.8
a
c
d (Fecha)
h (Fecha)
0.2
0.9
e
f1 (Fecha)
g (Fecha)
0.1
f2
Figura 5.17: DAG – Possibilidades de construção de um fragmento.
fim: princı́pio dos modelos mais longos, que resulta de estudos psico-linguı́sticos, mencionados no
capı́tulo 1, e utilização de preferências, que são especificadas na gramática. O SuSAna permite que
a utilização de qualquer um dos métodos de restrição de resultados seja facultativa.
Utilização de preferências
A utilização da informação indicada pelas preferências é feita em 3 fases distintas. A primeira fase consiste em atribuir custos aos arcos e é efectuada no algoritmo 7 (C ALC -B RANCHES);
a segunda fase consiste em utilizar esses custos para eliminar análises parciais, previamente calculadas, e é contemplada no algoritmo 5 (C ALC -M ODELS); a terceira fase é realizada quando se
produzem os resultados finais. A existência destas três fases deve-se ao facto de as preferências
não poderem eliminar hipóteses de análise, sem antes se saber se pode ser produzido um resultado
válido com as restantes hipóteses. A eliminação de hipóteses de análise, apenas na última fase,
tem um elevado custo em termos de eficiência, por essa razão, realizam-se cortes sempre que não
se corre o risco de não obter resultados.
Considere-se o DAG representado na figura 5.17 , que mostra as possibilidades de construção
de um fragmento de um determinado tipo . Cada vértice corresponde a um modelo que pode ou
não terminar e cada arco tem associado um custo, que por omissão é .
; ii) ; iii)
As várias possibilidades de construção do fragmento seriam: i) ; iv) ; v) ; vi) ; vii) . O custo associado
a cada uma das possibilidades seria de: 0.3 para vi) e vii); 0.8 para i) e ii); e 1.1 para iii) iv) e
v). Note-se que o arco que sai do modelo , com peso
pode ser eliminado, pois para qualquer
possibilidade de construção da fragmento a partir desse arco, existe uma outra possibilidade, que
não utiliza esse arco, cujo custo é menor e tem igual comprimento. Por exemplo: as possibilidades
4. e 6. têm o mesmo comprimento de 1. e oferecem menores custos. Contudo, o arco que sai de
com peso 0.9, não pode ser eliminado, pois o fragmento 3. deixaria de existir, não havendo mais
nenhuma possibilidade com comprimento 3.
#
De forma a poder eliminar correctamente os vértices de um determinado nı́vel do DAG, em cada
vértice é construı́do um vector com o comprimento da maior sequência de vértices que se consegue
construir a partir dele, designado por vector de fechos. A figura 5.18 ilustra este processo. Cada
posição do vector indica o número de possibilidades de fecho, posições à frente, sendo
.
A tentativa de eliminar um arco, será bem sucedida, se a subtracção do vector de fechos do vértice
5.4. O PROCESSO DE ANÁLISE
0.8
a
(0,0,1,3,3)
73
b
(0,0,1,1)
c
(0,1,1)
d (Fecha)
(1,1)
f1 (Fecha)
(1,1,1)
g (Fecha)
(1,1)
h (Fecha)
(1)
0.2
e
(0,1,2,2)
0.9
0.1
f2
(0,1,1)
Figura 5.18: DAG – Processo utilizado na desactivação de arcos.
de destino do arco, ao vector de fechos do vértice de origem do arco, não originar valores nulos.
.
Por exemplo, o arco que vai de a pode ser eliminado pois Note-se porém que a tentativa de eliminar o arco
conduziria ao cálculo , o qual origina um valor nulo e consequentemente não permite eliminar o arco.
-
- + + - - + + Princı́pio dos modelos mais longos
O princı́pio designado como dos modelos mais longos (Abney, 1996; Hagège, 2000), consiste em
eliminar as análises que correspondem a árvores com um maior conjunto de nós. A utilização desta
heurı́stica é feita em duas fases: a primeira fase ocorre durante a análise e a segunda ocorre na fase
de extracção de resultados. A primeira etapa de utilização desta heurı́stica é contemplada na linha
15 no algoritmo 5 (C ALC -M ODELS), logo após a aplicação de preferências. À semelhança das preferências, a eliminação de um fragmento implica necessariamente a existência de outro do mesmo
tipo, que permita realizar a análise em iguais ou melhores condições. Assim utiliza-se também o
vector de fechos utilizado também para a aplicação das preferências, como forma de verificação. A
segunda etapa é aplicada na fase de extracção de resultados. A cada resultado é atribuı́do um peso
e em função desses pesos pode-se fazer uma ordenação de resultados ou simplesmente eliminar os
resultados que não oferecem os melhores pesos.
5.4.7
Análise da complexidade
modelos não terminais, modelos terminais e .
Considere-se uma gramática com
Sendo o grafo utilizado para representar a estrutura da análise, cada vértice de está associado
a uma posição do segmento e representa a possibilidade de ocorrência de um modelo dentro
, com
de outro modelo nessa posição. Assim,
, sendo
, um modelo não terminal e um modelo terminal ou não terminal.
, # # de para uma dada posição
Considere-se um qualquer vértice
. O
número de vértices nessa posição, sendo modelo terminal é limitado por
. Nessa posição,
uma vez que o algoritmo não admite modelos recursivos, o número de vértices sendo modelo
não terminal, é limitado por . Assim, o número total de vértices é limitado
)
) ' ) . Conclui-se que o número de vértices de
por
) . Note-se que de uma forma geral,
associado à análise de um segmento de tamanho é
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
74
se o modelo ocorre no modelo e o modelo ocorre no modelo , ent ão o modelo não ocorre
directamente no modelo . Admitindo esta hipótese, o número de vértices de , para a posição
,
, implicando que o número de vértices de para um segmento de tamanho
é limitado por
.
é
) O grafo é composto por zero ou mais sub-grafos, que por sua vez podem ser compostos por
outros sub-grafos, formando assim vários nı́veis. Cada um dos grafos corresponde a um fragmento
de análise e cada nı́vel pode ser constituı́do por um ou mais sub-grafos. Cada vértice de contém
um conjunto de arcos para vértices do mesmo nı́vel e um conjunto de arcos para vértices de nı́vel
inferior. O número de arcos para vértices do mesmo nı́vel, que saem de um vértice , é no máximo
, e consequentemente limitado por
. O número de arcos que saem
de , para vértices de nı́veis inferiores é limitado por . Assim, o número total de arcos
que saem de é
.
)
) ) ) O número de operações para cada vértice é dado em função do número de arcos com origem
nesse vértice. Assim, a construção de corresponde a
operações, que corresponde
. Partindo do princı́pio a análise é sempre efectuada com a mesma gramática, é
a
um valor constante, consequentemente o número de operações para a análise de um segmento de
tamanho é
.
) ) ) ) Durante os testes realizados, verificou-se que o número de vértices para uma determinada
posição é limitado por um valor constante, bem como o número de arcos que saem desse vértice.
.
O que leva a concluir que a complexidade é, na prática,
5.5 Processo de extracção de resultados
Tal como foi visto antes, a utilização de resultados intermédios, entre a fase de análise e a fase
de extracção de resultados, permite que a análise possa ser efectuada com parâmetros independentes dos parâmetros usados para a extracção de resultados, permitindo, por exemplo, identificar
frases num texto e extrair apenas os sintagmas nominais dessas frases. Esta secç ão descreve os
conjuntos de parâmetros aceites pelo SuSAna aplicados à fase de extracção de resultados.
5.5.1
Elemento de topo
No que diz respeito à fase de extracção, o elemento de topo corresponde à estrutura linguı́stica
que se pretende extrair. Por omissão, este valor é definido à custa do elemento de topo usado para
a análise, correspondendo assim à estrutura identificada. A re-definição deste elemento permite
extrair sub-estruturas da estrutura analisada. Esta funcionalidade permite, por exemplo, extrair
sintagmas nominais de uma frase.
Considere-se a figura 5.19 , que representa a análise de uma frase, constituı́da por quatro
hipóteses. Cada hipótese é composta por um conjunto de fragmentos, representados por rectângulos.
Supondo que os fragmentos em destaque na figura são do tipo do modelo que se pretende extrair,
o resultado da extracção seria composto por três possibilidades diferentes, em que a primeira corresponderia aos quatro fragmentos iguais. Os dois fragmentos da parte final da frase n ão se po-
5.5. PROCESSO DE EXTRACÇÃO DE RESULTADOS
75
Figura 5.19: Representação da análise de uma frase constituı́da por quatro hipóteses.
dem juntar numa só, porque, possuindo diferentes comprimentos, correspondem obrigatoriamente
a fragmentos diferentes.
5.5.2
Re-definição dos parâmetros
e Os valores
e
, usados para parametrizar o processo de análise, são também utilizados para o processo de extracção. Contudo, o seu valor é re-definindo, no caso do elemento de topo
usado na extracção ser diferente do que foi utilizado na análise e da análise não ter considerado
segmentos múltiplos. Neste caso, ambos os elementos passam a ser verdadeiros, pois tem-se um
caso de extracção de sub-fragmentos do segmento.
5.5.3
Formatos de saı́da
A informação produzida na fase de análise pode ser obtida em diversos formatos, de forma a
satisfazer as necessidades do utilizador ou do sistema no qual o SuSAna pode vir a ser integrado.
XML
A figura 5.20 , apresenta a análise de uma frase em formato XML. O conjunto de elementos
definidos no DTD permite acrescentar um conjunto de informação adicional à análise, como é o caso
do seu grau de confiança. Um dos aspectos que importa focar relativamente ao XML é a facilidade
que oferece em preservar informação lida que não é relevante para a análise, como é o caso do lema
da palavra.
Contagens
Este formato permite obter contagens relativas aos resultados da análise. Neste formato, cada
linha corresponde à análise de uma hipótese de segmentação de um segmento. Apresenta-se o
número do segmento seguido do número da hipótese bem como o seu comprimento em termos de
unidades lexicais. Em termos de resultados de análise, apresenta-se o tempo de análise de todo o
segmento, bem como o número de soluções encontradas. Em virtude dos resultados poderem ter
sido analisados com a opção
e
, apresenta-se para cada conjunto de soluções, a sua
posição inicial no segmento, bem como o seu comprimento máximo. A listagem representada na
figura 5.21 , apresenta um extracto de um resultado produzido neste formato.
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
76
<segment>
<!-- A ainda mais bela rapariga -->
<hypothesis length="5">
<analysis weight="0" start="0" length="5">
<model name="ph" start="0" length="5">
<model name="m nn" start="0" length="5">
<model name="artd s" start="0" length="1">
<word name="A" root="o"/></model>
<model name="m an1" start="1" length="3">
<model name="m advn1" start="1" length="2">
<model name="adv1" start="1" length="1">
<word name="ainda" root="ainda"/></model>
<model name="advcomp" start="2" length="1">
<word name="mais" root="mais"/></model>
</model>
<model name="adj1 s" start="3" length="1">
<word name="bela" root="belo"/></model>
</model>
<model name="nc1 s" start="4" length="1">
<word name="rapariga" root="rapaz"/></model>
</model>
</model></analysis>
<analysis weight="0" start="0" length="5">
<model name="ph" start="0" length="5">
<model name="m prepn" start="0" length="5">
<model name="prep" start="0" length="1">
<word name="A" root="a"/></model>
<model name="m anp" start="1" length="3">
<model name="m advnp" start="1" length="2">
<model name="adv1" start="1" length="1">
<word name="ainda" root="ainda"/></model>
<model name="advcomp" start="2" length="1">
<word name="mais" root="mais"/></model>
</model>
<model name="adj1 s" start="3" length="1">
<word name="bela" root="belo"/></model>
</model>
<model name="nc1 s" start="4" length="1">
<word name="rapariga" root="rapaz"/></model>
</model>
</model>
</analysis></hypothesis></segment>
Figura 5.20: Análise em formato XML, da frase: A ainda mais bela rapariga.
Seg(2,0)
Seg(3,0)
Seg(4,0)
Seg(5,0)
Seg(6,0)
Len( 7)
Len( 5)
Len( 5)
Len(26)
Len(53)
Time(0.04)
Time(0.02)
Time(0.01)
Time(0.12)
Time(0.05)
[pos(0) len( 7) sols( 2)]
[pos(0) len( 5) sols( 2)]
[pos(0) len( 5) sols( 1)]
[pos(0) len(26) sols( 1)]
#Uma promessa feita ontem
#Esta bela amiga ...
#A ainda mais bela ...
#cães bonitos ...
#Um interesse ...
na cidade de ...
Figura 5.21: Extracto da análise de segmentos, no formato: contagens.
5.5. PROCESSO DE EXTRACÇÃO DE RESULTADOS
77
ph(
m nn( dem(Esta) adj1 s(bela) nadj s(amiga))
phv n( vc(portuguesa))
m prepn( prep(de) artd s(o) npr4(Pedro)))
Figura 5.22: Resultado da análise de um segmento em formato: texto.
ph(
m nn( Esta bela amiga )
phv n( portuguesa )
m prepn( de o Pedro ) )
Figura 5.23: Resultado da análise de um segmento em formato: sintagmas.
Texto
Este formato orientado para uma fácil observação dos resultados por parte do linguista, permitindo uma leitura compacta da informação. O exemplo da figura 5.22 , apresenta uma análise
produzida neste formato. O resultado é produzido com base em parêntesis, que permitem dividir os constituintes da frase, e em tabulações, que permitem uma fácil identificação dos nı́veis
hierárquicos definidos na análise.
Sintagmas
A figura 5.23 apresenta uma análise neste formato. A principal diferença relativamente ao formato texto, deve-se ao facto de não apresentar os modelos terminais associados às unidades lexicais.
Note-se que o número de possibilidades obtidas com o formato anterior pode ser superior ao apresentado neste formato, pois no formato texto duas análises iguais que diferem apenas na utilização
de dois modelos terminais diferentes, constituem dois resultados diferentes. Caso a informação
obtida por este formato seja suficiente, permite uma leitura mais clara e simples dos resultados.
Formato adequado à construção de grafos
O resultado obtido com a utilização deste formato pode ser utilizado para a obtenção de um
grafo representativo da análise. Este formato permite obter todo o tipo de informação relativo
à análise, de uma forma compacta. Existem numerosas ferramentas que permitem visualizar a
informação gerada. O formato pode ser utilizado directamente com o conjunto de aplicaç ões fornecidos com o pacote GraphViz1 (Gansner et al., 1988, 1993; Koutsofios e North, 1996). A figura 5.24
mostra o exemplo de um grafo produzido a partir da informação produzida com o SuSAna. Note-se
que o grafo contém informação acerca dos arcos eliminados, bem como o custo atribuı́do a cada arco.
A informação gerada pode ser vista como uma representação da estrutura da análise em memória.
1 Colecção de ferramentas e pacotes, open source, destinados à manipulação de configuração do aspecto de grafos.
http://www.graphviz.org/
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
78
ph
m_prepn_part
7−8−S−N−N−(0,0)
m_prepn_part
m_prepn_part
prep
7−8−S−N−C−(0,1)
artd_s
8−8−N−E−C−(0,0)
ph
ph
m_nn_part
0−0−S−N−N−(0,0)
copi_n
m_nn_part
prep
4−4−S−N−N−(0,0)
7−7−S−N−N−(0,0)
m_nn_part
madv
artd_s
4−4−S−E−C−(0,0)
prep
7−7−S−N−N−(0,0)
ph
m_nn_part
artd_s
0−0−S−E−C−(0,0)
ph
ph
ph
m_nn
0−9−S−E−C−(0,11)
phv_n
2−9−S−E−C−(0,7)
que_n
3−9−S−N−C−(0,6)
m_nn
artd_s
m_nn
npr4
phv_n
vc
que_n
qu
0−1−S−N−C−(0,1)
1−1−S−E−C−(0,0)
2−2−S−E−C−(0,0)
3−3−S−E−C−(0,0)
inf_n
m_cli
prep
4−4−N−E−C−(9999,0)
7−7−S−N−N−(0,0)
m_nn
artd_s
m_nn
npr4
m_reln
prep
4−5−S−N−C−(0,1)
5−5−S−E−C−(0,0)
7−7−S−N−N−(0,0)
m_cli
que_n
cli_ac
4−4−S−E−C−(0,0)
prep
7−7−S−N−N−(0,0)
ph
m_nn
ph
phv_n
ph
m_prepn
4−9−S−E−C−(0,5)
6−9−S−E−C−(0,1)
7−9−S−E−C−(0,0)
m_prepn
m_prepn
phv_n
vc
prep
7−9−S−N−C−(0,2)
artd_s
8−9−N−N−C−(0,1)
m_prepn
nc1_s
9−9−N−E−C−(0,0)
6−6−S−E−C−(0,0)
O
Jorge
disse
que
o
João
saiu
m_prepn
nc2_s
9−9−N−E−C−(0,0)
em
o
carro
Figura 5.24: Grafo de análise da frase: O Jorge disse que o João saiu em o carro.
5.5.4
Previsão de modelos em estruturas incompletas
Uma das tarefas que se podem realizar com a SuSAna, consiste em prever o conjunto de modelos admissı́veis para a palavra seguinte, numa frase que se encontre incompleta. Esta funcionalidade está actualmente a ser utilizada num sistema de auxı́lio à escrita de poemas, para limitar o
conjunto de palavras admissı́veis numa rima (Araújo, 2003).
5.5.5
Desambiguação
O SuSAna pode ser utilizado para a desambiguação parcial de texto, tendo presente que as
categorias gramaticais não utilizadas em análises obtidas são inválidas no contexto sintáctico em
que se encontram. Esta funcionalidade será integrada em versões futuras do SuSAna.
5.6 Casos de utilização do sistema
A necessidade de utilização da análise sintáctica no contexto de actuais e futuros projectos
ou tarefas em curso no L F constitui uma das principais motivações para o desenvolvimento do
SuSAna. O módulo do SuSAna tem sido utilizado em diversas tarefas e está actualmente a ser
utilizado em sistemas de processamento de linguagem natural. Nesta secção são descritas algumas
tarefas que usam o SuSAna.
5.6. CASOS DE UTILIZAÇÃO DO SISTEMA
5.6.1
79
ATA: Aquisição Automática de Termos
O ATA (Paulo et al., 2002) é um sistema, uma arquitectura e uma metodologia para a extracção
automática de termos. A cadeia de processamento do sistema é composta por várias tarefas: 1)
Lematização – efectuada com o analisador morfológico Smorph, o resultado produzido nesta fase é
texto lematizado; 2) processamento pós morfológico – tarefa efectuada com o PaSMo que consiste em
agrupar as unidades de texto lematizado na fase anterior; 3) análise sintáctica de superfı́cie – tarefa
realizada com o SuSAna cujo resultado consiste em texto lematizado e delimitado sintacticamente;
4) extracção de termos. O resultado final consiste numa lista de termos simples e numa lista de
termos compostos, obtidos com base em frequências.
A identificação de termos é efectuada no ponto 3) da cadeia de processamento. Para esse efeito,
foram adicionadas regras à gramática do SuSAna, que lhe permitem reconhecer a estrutura de um
termo.
5.6.2
Poeta: sistema de auxı́lio a escrita de poemas
Este sistema tem como função sugerir um conjunto de possı́veis palavras para uma rima incompleta. O correcto funcionamento do Poeta passa por identificar todas as palavras ou formas
que se podem sugerir ao utilizador, tendo em consideração que esse conjunto deve ser o mais reduzido possı́vel. Nesse contexto, a cada palavra são aplicadas restrições ao nı́vel da terminação,
classificação morfossintáctica e se faz sentido sob o ponto de vista sintáctico. O SuSAna tem um
modo de funcionamento que lhe permite deduzir, para uma frase incompleta, quais as categorias
morfossintácticas que fariam sentido para continuar essa frase. Essa funcionalidade permite restringir ainda mais o conjunto de categorias que a palavra a sugerir pode assumir.
5.6.3
Extracção de sintagmas nominais
O reconhecimento de sintagmas nominais em corpora é uma tarefa importante e de grande
aplicação em diversas áreas. Uma das áreas onde a sua aplicação tem sido investigada é na
recuperação de informação. Grande parte da comunidade cientı́fica considera que os sintagmas
nominais constituem a informação mais significativa para a identificação do conteúdo de um texto,
a sua utilização em sistemas de representação de documentos permite, por um lado destacar a
informação representativa do documento e, por outro, reduzir a quantidade de informação necessária à representação desse mesmo documento. A representação de documentos pode ser, por
exemplo, usada em sistemas de recuperação de texto.
5.6.4
Testes sobre corpus com e sem ambiguidade
Os testes apresentados de seguida foram realizados para verificar o tipo de resultados produzidos pelo SuSAna em função da ambiguidade de um corpus com texto não restrito2 , e consistem em
identificar a estrutura dos sintagmas nucleares presentes nesse corpus.
2 A expressão texto não restrito vem do Inglês unrestricted text e corresponde à expressão texto real. Artigos de um jornal
ou a transcrição de um corpus de fala, são exemplos de texto real.
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
80
Tempo (segs.)
Total
por frase
Com amb.
Sem amb.
333,99
0,13
212,73
0,08
Tabela 5.1: Comparação do tempo de processamento do SuSAna com base na ambiguidade.
Hip.
Ambig.
Desamb.
0
14,9%
23,7%
1
47,1%
71,7%
2
23,1%
2,3%
3-4
8,2%
2,1%
4
6,7%
0,2%
Tabela 5.2: Comparação do número de soluções por cada resultado em função da ambiguidade.
Os testes foram conduzidos com base numa gramática constituı́da por: 269 blocos; 70 relações
hierárquicas; e 199 preferências, totalizando 538 regras. As regras definem o comportamento de
151 modelos diferentes, 116 dos quais terminais e os restantes não terminais.
Os textos considerados neste teste são constituı́dos por excertos de livros com aproximadamente
29100 palavras. A segmentação dos textos em frases revelou 2608 segmentos com uma média de
10,96 palavras por segmento. A classificaç ão morfossintáctica produziu um total de 38574 etiquetas
o que corresponde a uma ambiguidade média de 1,326.
Resultados da análise
Os testes foram realizados com e sem ambiguidade morfossintáctica. A análise de informação
com ambiguidade morfossintáctica traduz-se num tempo de processamento mais elevado e num
conjunto maior de possibilidades de análise. Por outro lado, a desambiguação morfossintáctica
automática pode aumentar o número de erros. A tabela 5.1 apresenta o tempo de processamento3
despendido em cada um dos testes.
A análise de uma frase pode ser constituı́da por mais do que uma possibilidade: assim, é desejável obter o menor conjunto de análises não vazias, limitando simultaneamente o número total
de hipóteses com recurso a preferências e ao princı́pio dos modelos mais longos. Nesse sentido, o
número de hipóteses de cada análise foi considerado como uma das medidas de avaliaç ão.
A tabela 5.2 mostra o número médio de hipóteses geradas para o conjunto de frases, tendo
como base informação ambı́gua e desambiguada. Relativamente à informação com ambiguidade, os
resultados mostram que a maioria das análises consiste numa ou duas possibilidades. A informação
desambiguada, por seu lado, origina um maior número de análises vazias, grande parte delas devido
aos erros introduzidos pelo desambiguador, reduzindo assim o número de possibilidades de análise.
3 Testes
realizados num processador Intel Pentium III 800 Mhz usando o sistema operativo Linux.
5.7. SUMÁRIO
81
5.7 Sumário
Este capı́tulo apresenta SuSAna, um módulo de análise sintáctica de superfı́cie concebido e
implementado no âmbito desta tese. Este analisador foi desenvolvido tendo como ponto de partida
o funcionamento do protótipo de análise de superfı́cie AF (Hagège, 2000). Os objectivos propostos para o desenvolvimento do SuSAna, assentam no desenvolvimento de uma ferramenta integrada, independente e orientada para o processamento de grandes quantidades de corpora. A sua
integração noutros sistemas e plataformas, foi um dos aspectos tidos em consideração no seu desenvolvimento, razão pela qual se implementou como um módulo. Foca-se o uso do XML para a
representação de dados e define-se o tipo de dados que o SuSAna processa. Neste contexto define-se
a noção de segmento e descreve-se a sua estrutura.
No que diz respeito ao funcionamento do módulo, a secção 5.3 aborda a sua arquitectura e a
representação interna da informação. Relativamente à sua arquitectura, o sistema separa a função
de análise da função de extracção de resultados. A ligação entre essas duas funções é estabelecida
por uma estrutura de dados, designada por repositório, que contém toda a informação necessária
para a produção de resultados. O repositório permite também utilizar informação previamente
calculada, de forma a reduzir o tempo de execução da aplicação.
Na secção 5.4 descreve-se o processo de análise e os algoritmos utilizados. O núcleo da análise
de superfı́cie é composto por duas funções. A função C ALC -M ODELS é responsável por calcular
todos os modelos de um tipo T, que se podem iniciar na posição w do segmento em análise. G ETS IBLING -M ODELS calcula e devolve todas as sequências de modelos que podem ocorrer a partir de
uma posição w do segmento após a ocorrência de um fragmento L e dentro de um modelo T. A função
C ALC -B RANCHES é responsável por seleccionar os caminhos seguintes possı́veis e aplicar o custo a
cada um deles em função preferências presentes na gramática. Finalmente, a função C ALC -D AG V ERTICE é responsável por criar os nós do grafo de análise e estabelecer as relações entre esses nós.
Estas funções funcionam recursivamente de forma cruzada. O processo análise tem uma comple
, sendo o número de unidades lexicais do segmento e o número de sı́mbolos
xidade
presentes na gramática. Um dos principais pontos a ter em conta numa aplicação de análise de
superfı́cie é a limitação do número de análises, mantendo simultaneamente a cobertura relativamente aos fenómenos linguı́sticos. O SuSAna utiliza dois mecanismos de restrição de análises:
preferências e princı́pio dos modelos mais longos.
) 82
CAPÍTULO 5. SUSANA: ANALISADOR DE SUPERFÍCIE
Após a descrição do módulo de análise de superfı́cie SuSAna, importa analisar os seus resultados e o seu desempenho em corpus. Este capı́tulo inicia-se com uma análise do conjunto de resultados, através da comparação entre os resultados do AF e os resultados do SuSAna. De seguida
avalia-se o desempenho do sistema desenvolvido, num corpus jornalı́stico com cerca de 4,5 milhões
de unidades lexicais. Apresentam-se também um conjunto de estatı́sticas e algumas considerações
acerca do tipo de resultados obtidos.
6.1 Condições de avaliação
Os testes conduzidos no âmbito desta avaliação foram realizados num computador com sistema
operativo Linux, cujas caracterı́sticas são apresentadas na tabela 6.1. Durante a realização dos testes, a máquina executava um conjunto de processos, que fazem parte do seu normal funcionamento,
contudo, os tempos de processamento apresentados em cada tarefa, correspondem apenas ao tempo
de dedicação do processador a essa tarefa, obtidos com o comando time.
Atributo
Sistema operativo
Versão do kernel
Processador
Cache
Frequência
Bogomips
Memória
Swap
Valor
Linux RedHat
2.4.20-8
Intel Pentium III
256 KB
800 Mhz
1600
512 Mb
256 Mb
Tabela 6.1: Caracterı́sticas do computador onde foram realizados os testes de desempenho.
6.2 Gramática
A informação presente nas diferentes versões da gramática, usadas ao longo deste capı́tulo,
provém da gramática descrita por Hagège (2000) e utilizada nos seus testes com o protótipo AF.
Esta gramática foi desenvolvida com o propósito de delimitar os sintagmas nominais presentes
CAPÍTULO 6. AVALIAÇÃO
84
numa frase. Assim, a parte relativa ao seu tratamento encontra-se mais desenvolvida: o tratamento de sintagmas verbais, por exemplo, está a ser feito de forma pouco profunda, conduzindo
necessariamente a uma falta de precisão nos resultados.
Foram introduzidas algumas modificações à gramática, umas vezes originadas por inconsistências encontradas, outras para proporcionar novas etiquetas ou modelos mais especı́ficos.
Apresentam-se as modificações mais relevantes:
Tratamento da coordenação: em Hagège (2000), os fenómenos de coordenação são tratados
de forma superficial, em que parte do processamento é efectuado ao nı́vel do algoritmo. O
algoritmo do AF usa uma estratégia de Look-Ahead, na qual são examinadas as classificações
das palavras à direita de uma vı́rgula ou conjunção, antes de considerar o caso de coordenação.
O algoritmo do SuSAna, contudo, permite efectuar o mesmo tratamento, apenas com base nas
regras da gramática e seguindo sempre a mesma estratégia. Assim, foram introduzidas na
gramática, as regras que o SuSAna necessita, para produzir os mesmos resultados obtidos
pelo AF.
Foi introduzido o modelo break. este modelo, permite indicar ao SuSAna o fim de uma frase.
A gramática utilizada pelo AF, apenas utiliza o modelo m ponct no qual se podem incluir:
pontos finais, parêntesis, reticências, etc. O facto de poder incluir sı́mbolos que não terminam
uma frase, como é o caso dos parêntesis, obriga a indicar na gramática que o modelo m ponct
nem sempre termina uma frase. O modelo break é uma categoria ou modelo terminal, que
pode ser usado nos dados de entrada do SuSAna para indicar o fim de uma frase, mesmo que
o segmento não termine nesse ponto. Na gramática foi introduzida informação de que este
modelo apenas poderá seguir os modelos que podem terminar uma frase, e termina sempre a
frase. Note-se que, na ausência deste modelo, quando se envia para o SuSAna, por exemplo,
um ponto final imediatamente antes do fim do segmento, este vem etiquetado com a etiqueta
eliminer.
No momento da realização dos testes que se descrevem neste capı́tulo, a gramática continha
informação acerca do comportamento de 152 modelos diferentes, 117 dos quais terminais e os restantes não terminais. Em termos de regras, a gramática era composta por um total de 542 regras,
das quais 270 eram blocos, 73 eram relações hierárquicas e 199 eram preferências.
6.3 Comparação entre o AF e o SuSAna
Utilizando a mesma informação, isto é, gramáticas que permitam associar a mesma estrutura
a cada frase da lı́ngua, as duas aplicações devem produzir os mesmos resultados, e no caso de
diferenças deve-se procurar a sua justificação. Note-se que uma das motivações para o desenvolvimento do SuSAna é substituir a utilização do AF pelo SuSAna. Assim, foram realizados testes
de comparação entre o SuSAna e o AF, aproximando as condições de realização dos testes de cada
um dos sistemas. Os parâmetros de avaliação considerados foram a eficiência e o conjunto de resultados obtidos em cada um deles. Os dados utilizados na realização dos testes são processados de
forma a que a informação presente na entrada de cada um dos analisadores seja a mesma, embora
6.3. COMPARAÇÃO ENTRE O AF E O SUSANA
85
Figura 6.1: Diagrama de tratamento de informação, de forma a ser processada tanto pelo AF como
pelo SuSAna.
no formato adequado a cada um dos sistemas. Desta forma, garante-se que os resultados obtidos dependem apenas do processamento realizado por cada um dos sistemas. No que diz respeito
à eficiência, foi feito um esforço no sentido de tornar possı́vel a realização dos testes na mesma
máquina, na mesma plataforma, e em iguais condições, de forma a obter tempos de medição mais
precisos.
6.3.1
Preparação dos dados
De forma a proceder na tarefa de análise sintáctica, cada um dos analisadores necessita de
informação previamente classificada morfossintacticamente. Contudo, o tipo de dados utilizado
por cada um dos analisadores diverge. Assim, a estratégia que se adoptou consistiu em utilizar as
mesmas ferramentas para efectuar o processamento de nı́vel morfossintáctico, e adaptar o resultado
obtido ao formato requerido por cada uma das aplicações. Esta estratégia garante que o conjunto
de dados obtido por cada uma das ferramentas seja equivalente.
O primeiro passo no processo de produção dos dados consiste em classificar a informação ao
nı́vel morfológico, tarefa que foi realizada pelo analisador morfológico SMORPH de Aı̈t-Mokhtar
(1998). O segundo passo consiste em produzir um conjunto de segmentos, constituı́dos por unidades
lexicais devidamente classificadas com um conjunto de etiquetas, a partir das classificaç ões obtidas
no passo anterior. Este passo foi conduzido com recurso ao pós-analisador morfológico PaSMo (Paulo
e Mamede, 2001; Paulo et al., 2002).
A informação presente à saı́da do PaSMo é suficiente para que se possam realizar os testes, contudo não se encontra ainda no formato adequado. A conversão da informação para o formato adequado à leitura pelo SuSAna não levanta problemas, pois tanto a saı́da do PaSMo como a entrada do
SuSAna se encontram no formato XML. A conversão é realizada com um pequeno programa em linguagem XSLT. A conversão da informação para a entrada do AF, por seu lado, levanta um conjunto
de problemas, pois o AF exige um formato especial em que cada etiqueta presente no corpus seja
acompanhada pelas folhas presentes na gramática do AF, que se adequam a essa etiqueta. Como
não existem ferramentas disponı́veis para a solução deste problema, foi construı́da uma aplicação
para esse efeito, que se designou por Pasmo2Af. A figura 6.1 ilustra toda a cadeia de processamento
associada ao processo de preparação dos dados.
CAPÍTULO 6. AVALIAÇÃO
86
6.3.2
Preparação e parametrização dos analisadores
De forma a proporcionar condições de avaliação semelhantes aos dois analisadores, foi necessário, por um lado, colocar os dois sistemas em funcionamento na mesma plataforma e, por
outro, parametrizar o SuSAna de forma a produzir o tipo de resultados do AF.
Preparação do AF
O primeiro passo no sentido de aproximar as condições de teste dos dois analisadores, consistiu em juntar todos os ficheiros de código do AF num único ficheiro de forma a reduzir o overhead
na consulta dos vários ficheiros, mantendo a mesma funcionalidade. Esta forma de utilizaç ão não
permite, ainda assim, uma avaliação precisa, dado que o SuSAna é uma aplicação compilada e o
AF é interpretado. O passo seguinte consistiu em compilar a versão compacta do AF e produzir
um ficheiro binário e executável. A geração do ficheiro executável foi realizada recorrendo às ferramentas que acompanham o sistema de desenvolvimento SICStus v3.10,1 e efectuada com todas as
optimizações permitidas.
Parametrização do SuSAna
Como foi mencionado na sub-secção 5.4.5 do capı́tulo anterior, o SuSAna permite efectuar a
análise e extrair resultados com base num conjunto de parâmetros. Para os testes apresentados
activada e as opções
e
desactivadas. A
o SuSAna é executado com a opção
opção
resulta do AF apenas permitir apenas analisar segmentos com uma única estrutura
linguı́stica de topo. Por outro lado, como o AF devolve resultados incompletos no caso de n ão conseguir tratar todo o segmento, a melhor forma encontrada para produzir resultados semelhantes
foi utilizando a opção
. Assim, todos os resultados produzidos pelo SuSAna são analisados
de forma a identificar os casos problemáticos: se o resultado da análise não contempla a primeira
palavra da frase, então considera-se que o SuSAna produz zero resultados; se o resultado não cobre
todas as palavras da frase, é feita uma análise manual do problema.
6.3.3
Corpus utilizado na avaliação
O processo de análise de resultados foi condicionado pela existência de erros ou inconsistências
no AF. Por exemplo, a frase seguinte origina um erro, impedindo a continuação da análise:
[ F16
[ A1
’um’, [’um’,’arti s’],
’trabalho’, [’trabalho’,’nc1 s’ , ’trabalhar’,’vc12’],
’algo’, [’algo’,’pri’],
’violento’, [’violentar’,’vc12’]
] A1
] F16 %fim da frase número 16
1 O sistema de desenvolvimento de prolog SICStus é um sistema que obedece às normas ISO. Trabalhando sobre um
núcleo eficiente, permite o tratamento de grandes quantidades de informação.
6.3. COMPARAÇÃO ENTRE O AF E O SUSANA
87
Assim, optou-se por fazer a comparação entre o AF e o SuSAna, apenas com base no corpus
utilizado por Hagège (2000), durante a avaliação do AF. A escolha deste corpus permite garantir
uma execução correcta por parte do AF, uma vez que esse corpus já fora anteriormente processado
pelo AF. De acordo com Hagège (2000), este corpus é composto por aproximadamente 4000 palavras,
e foi construı́do com base em três fontes distintas:
constituição. Introdução e os seis primeiros artigos da Constituição da República Portuguesa;
jornal1 e jornal2. Extractos do jornal Público, escolhidos arbitrariamente;
teses. Extractos de duas teses de Mestrado.
A tabela 6.2 apresenta as caracterı́sticas gerais do corpus, entre as quais, o número de segmentos
que o compõem, bem como o número de hipóteses de divisão desses segmentos. Note-se, por exemplo, que em jornal1, existe um segmento com duas alternativas, isto é, duas hipóteses de divisão em
unidades lexicais. Para cada parte distinta do corpus, são indicados também o número de palavras
e etiquetas a elas associadas; média de palavras por hipótese de frase; e ambiguidade média, que
corresponde à média do número de etiquetas atribuı́das a cada palavra.
Textos
constituição
jornal1
jornal2
teses
Totais
Segmentos
28
45
20
54
147
Hipóteses
28
46
22
55
151
Palavras
615
1323
623
1706
4267
Etiquetas
807
1749
854
2248
5658
Pals/Hips
21.96
28.76
28.32
31.02
28.26
Amb.
1.31
1.32
1.37
1.32
1.33
Tabela 6.2: Caracterı́sticas dos textos utilizados para comparar os analisadores AF e SuSAna.
6.3.4
Processo para extracção de resultados
A primeira etapa no processo de comparação entre o AF e o SuSAna consiste em comparar
os resultados produzidos por cada um dos sistemas, de forma a identificar as possı́veis diferenças.
Uma vez que os sistemas produzem diferentes tipos de resultados e em diferentes formatos, esta
etapa compreendeu a passagem da informação para um formato único. Tendo em consideração que
a estrutura da informação produzida pelo SuSAna permite representar toda a informação obtida
do AF, e se encontra em formato XML, optou-se por construir uma ferramenta de convers ão, dos
resultados do AF para os resultados do SuSAna, que se designou por af2xml. A comparação dos
resultados foi realizada a partir de dois ficheiros correspondentes à análise do SuSAna e do AF, nos
quais cada linha corresponde a uma das possibilidades de análise de cada frase. Estes ficheiros
foram produzidos com base em XSLT, a partir da estrutura de dados produzida pelo SuSAna. A
figura 6.2 mostra a sequência de processamento utilizada no processo.
CAPÍTULO 6. AVALIAÇÃO
88
Figura 6.2: Diagrama de processamento de resultados produzidos pelo AF e pelo SuSAna.
6.3.5
Resultados
Apresenta-se seguidamente uma análise aos resultados obtidos pelos dois analisadores, tanto
no que diz respeito à informação produzida, como em termos de tempo de processamento.
Diferença de resultados
Em Hagège (2000), os fenómenos de coordenação são tratados de forma superficial. O algoritmo
do AF usa uma estratégia de Look-Ahead, na qual são examinadas as classificações das palavras à
direita de uma vı́rgula ou conjunção, antes de considerar o caso de coordenação (ver secção 3.2.6). O
algoritmo do SuSAna, contudo, permite efectuar o mesmo tratamento, apenas com base em regras
da gramática, tendo em consideração que é aplicado o princı́pio dos modelos mais longos. Nos
resultados produzidos pelo AF, verificaram-se resultados incoerentes com as regras da gram ática
e com as indicações dadas por Hagège (2000) relativamente ao tratamento da coordenação. As
incoerências verificadas, dizem respeito ao tratamento da coordenação, e devem-se provavelmente
à forma particular de tratamento destes casos no AF. Uma vez que este tipo de problema se encontra
localizado, foi implementado um script que corrige este tipo de ocorrências com o AF, fazendo com
que este problema não influencie os resultados.
Após efectuar os tratamentos necessários, verificou-se ainda assim que, grande parte das
análises produzidas pelos dois analisadores diferem, tanto no que diz respeito à estrutura da
análise, como em termos do número de análises produzidas. De forma a perceber as razões que
levam a estas diferenças, foi analisada pormenorizadamente a parte do corpus designado por constituição. Das 28 frases analisadas, apenas 13 deram resultados exactamente iguais, embora outras
4 possuı́ssem hipóteses de resultados comuns a ambos os analisadores. A tabela 6.3 mostra de uma
forma resumida o tipo e a razão das diferenças. De seguida, descrevem-se os factores que levam às
diferenças nos resultados das restantes 15 frases:
Análises incompletas não justificadas. Por vezes, o AF devolve resultados com an álises incompletas, que abrangem diferentes números de palavras na frase, chegando mesmo a devolver
resultados com análises completas e incompletas em simultâneo. Grande parte das análises
incompletas devolvidas envolvem apenas uma pequena parte da frase. Por exemplo, em frases
com 78 palavras, devolve resultados que abrangem apenas as duas primeiras palavras.
Análises repetidas. O AF repete, por vezes, a mesma alternativa de análise, contribuindo assim
para um aumento do número de alternativas e consequentemente para a diferença de resultados.
6.3. COMPARAÇÃO ENTRE O AF E O SUSANA
89
Figura 6.3: Tipos de diferenças nos resultados produzidos pelo AF e pelo SuSAna, relativos aos
textos constituição.
Utilização parcial das preferências. Foram observados casos de resultados produzidos pelo AF,
que poderiam ser eliminados, com base nas preferências existentes na gramática.
Utilização parcial do princı́pio dos modelos mais longos. Por vezes, o AF devolve resultados,
que se verificaram poder ser eliminados, com base no princı́pio dos modelos mais longos. A
análise realizada pelo SuSAna, compreende a construção de um grafo onde se testam todas as possibilidades de análise. A extracção de resultados, a partir desse grafo, permite a
comparação de todas as possibilidades de análise de forma a poder contemplar todas as possibilidades de aplicação das preferências e de eventuais princı́pios. Por seu lado, o AF realiza
uma procura parcial que o impede de contemplar todos os casos.
Desempenho dos sistemas
No que diz respeito ao desempenho, as duas aplicações foram analisadas quanto ao tempo
de processamento e memória ocupada. A tabela 6.3 apresenta os valores obtidos em cada parte do
corpus, acrescentando também o número de hipóteses de análise e o tamanho dos resultados, depois
de convertidos no formato XML. No que diz respeito aos tempos, no caso do SuSAna, pode verificarse uma correlação entre os tempos de processamento e o tamanho dos resultados. Na realidade,
CAPÍTULO 6. AVALIAÇÃO
90
Texto
constituição
jornal1
jornal2
teses
User time (s)
AF
SuSAna
11,33
9,72
15,56
11,00
26,14
3,71
26,74
20,73
Memória (kb)
AF
SuSAna
29.572
3.940
15.888
4.644
55.700
3.720
20.440
5.552
Hipóteses
AF SuSAna
164
133
197
195
204
89
315
340
XML (kb)
AF
SuSAna
390
2.500
700
3.000
450
600
1100
5.900
Tabela 6.3: Comparação de desempenho entre o AF e o SuSAna. A coluna correspondente à
memória, apresenta o maior bloco de memória ocupado durante o processamento, em kbytes.
no caso do SuSAna, o tempo de processamento apresentado, corresponde, na sua maioria, a tempo
usado para a leitura e escrita da informação. O SuSAna utilizou apenas 13,7s para realizar a
análise de todo o corpus.
Os valores de ocupação de memória, apresentados na tabela 6.3, encontram-se elevados no
caso do SuSAna, devido à utilização de uma versão antiga da biblioteca Xerces (Xerces, 2003), de
manipulação de XML. A utilização do XML é feita através de uma árvore DOM, que representa a
estrutura e informação de um documento em memória. As recomendações do W3C para a estrutura
das árvores DOM, não contemplam, a possibilidade de ler partes de documentos, obrigando a que
o documento XML seja tratado como um bloco e seja colocado todo em mem ória. A ocupação de
memória pelo SuSAna, antes da análise de uma frase é de cerca de 3.100 kbytes e em média,
aumenta cerca de 927 bytes por palavra durante a análise.
6.4 Desempenho do SuSAna em corpus alargado
Nesta secção descrevem-se os resultados obtidos na análise de um corpus jornalı́stico, composto
por cerca de 4.6 milhões de palavras, que corresponde a cerca de dois meses de edição do jornal
Público.
6.4.1
Parâmetros de avaliação
A qualidade dos resultados obtidos depende única e exclusivamente das regras presentes na
gramática. Assim, a qualidade dos resultados não será avaliada, pois as regras utilizadas nos
testes realizados no âmbito desta tese, consistem em ligeiras modificações do conjunto de regras
originais utilizado por Hagège (2000), para a tarefa de extracção de sintagmas nominais. Uma vez
que o SuSAna produz o mesmo conjunto de resultados produzido pelo AF, a avaliaç ão da qualidade
dos resultados remete-se para Hagège (2000).
O tempo de processamento é um factor relevante, no que diz respeito à integração do módulo
SuSAna em cadeias de processamento ou sistemas de processamento de lı́ngua natural. Os resultados da análise sintáctica, podem ser aplicados a variados domı́nios, como é o caso da sı́ntese e
reconhecimento de fala, nos quais o factor tempo não pode ser desprezado. Assim, interessa avaliar
o desempenho do SuSAna ao nı́vel do tempo de processamento, e identificar os factores que mais
influenciam esse desempenho.
6.4. DESEMPENHO DO SUSANA EM CORPUS ALARGADO
Elemento
Edições
Segmentos
Unidades Lexicais
Etiquetas
91
Contagem
51
170.226
4.599.080
6.034.521
Tabela 6.4: Caracterı́sticas do corpus correspondente a dois meses de edição do jornal Público.
A utilização do módulo poderá ser comprometida pela memória necessária à sua execução. Por
exemplo, certos dispositivos, como é o caso dos PDA, onde a utilização de um analisador sintáctico
pode ser interessante, têm recursos limitados em particular no que diz respeito a memória. Durante
a execução do SuSAna foi por vezes verificado um grande consumo de memória, mesmo antes de iniciar a análise. Este consumo exagerado de memória deve-se à construção de uma árvore DOM a partir da informação se encontra no formato XML, com todos os dados para análise. As recomendações
do W3C para o DOM 1.0 e 2.0 não prevêem a leitura incremental e parcial da informação, contudo,
a análise concorrente e incremental bem como o tratamento e manipulação de fragmentos de documentos XML, estão de momento a ser considerados para integrar as especificações da DOM versão
3.0.2 Assim, embora se apresentem os dados relativos ao consumo de memória, estes não devem ser
entendidos como limitadores, mas simplesmente como elementos que descrevem o estado actual de
funcionamento do SuSAna.
As necessidades do analisador, bem como o tipo de resultados pretendidos, variam em
função da sua parametrização. Assim, é importante analisar os recursos requeridos consoante a
parametrização.
6.4.2
Caracterı́sticas do corpus
O corpus utilizado nos testes seguintes compreende 51 edições do jornal Público, correspondendo a cerca de 4,6 milhões de unidades lexicais. As edições consideradas foram seleccionadas de
um conjunto de edições do ano 2001, sendo a sua maioria relativa aos meses de Fevereiro e Dezembro desse ano. O corpus original encontra-se em formato HTML, do qual foram removidas as
etiquetas. A tabela 6.4 apresenta um resumo das caracterı́sticas do corpus.
Relativamente ao tamanho dos segmentos, ou seja o número de unidades lexicais que constituem o segmento, a sua distribuição em função do número de unidades lexicais é apresentada na
figura 6.4. O maior segmento é composto por 752 unidades lexicais, embora o tamanho médio seja
cerca de 27 unidades lexicais, e a figura mostre que a maioria dos segmentos possui entre 19 e 39
unidades lexicais. Em termos de ambiguidade média, isto é, número de classificaç ões atribuı́das a
cada uma das unidades lexicais, o seu valor é aproximadamente 1,31 etiquetas por palavra.
2 Mais
informações em http://www.w3.org/TR/2002/WD-DOM-Level-3-ASLS-20020409/load-save.html
CAPÍTULO 6. AVALIAÇÃO
92
Figura 6.4: Distribuição de segmentos por número de unidades lexicais.
6.4.3
Preparação dos dados
A preparação dos dados foi realizada segundo a cadeia de processamentos ilustrada na figura
6.1 e utilizada no contexto da comparação entre o AF e o SuSAna. A esta cadeia foi adicionado mais
um módulo, para efectuar uma última fase de adaptação dos resultados produzidos no módulo de
pós-análise morfológica PaSMo. O PaSMo utiliza um conjunto de sequências de sı́mbolos, designado
por separadores, que lhe permitem segmentar a sua saı́da em frases. Contudo, este processo é
apenas baseado na palavra, não entrando em conta com a sua etiqueta, e tornando possı́vel o fim de
uma frase onde esta não deveria ocorrer. O módulo adicionado junta todos os segmentos produzidos
pelo PaSMo num único segmento e adiciona a etiqueta a cada uma das palavras consideradas
anteriormente como separadores (ponto final, ponto de exclamação, etc.) e que podem terminar
uma frase. Assim, ao processar cada uma dessas palavras, o SuSAna poderá ou não considerar
que a frase termina nesse ponto. Esta operação contribui para que menos unidades lexicais sejam
desprezadas durante a análise.
De forma a testar o desempenho do sistema em corpus sem segmentação, foi também produzida
uma versão do corpus na qual se retiraram as etiquetas de inı́cio e fim de segmento, existentes no
documento. Assim, cada edição do jornal passou a constituir um único segmento, fazendo com que
o corpus seja constituı́do por apenas 51 segmentos.
6.4.4
Os resultados
A análise do desempenho do sistema foi realizada com várias parametrizações, por forma a
estudar o desempenho do sistema em variadas situaç ões. O primeiro teste foi realizado com as
opções definidas por omissão, que consistem em considerar que cada segmento corresponde a uma
frase e que todas as palavras desse segmento fazem parte da frase. Seguidamente realiza-se um
teste com a opção skips, que permite obter análises completas, embora possam não cobrir todas
as unidades lexicais presentes no segmento. Pretende-se com este teste, conhecer o n úmero de
segmentos que contêm frases – embora possam existir unidades lexicais nesse segmento que não
fazem parte da frase – e a percentagem de unidades lexicais desprezadas nas análises incompletas
6.4. DESEMPENHO DO SUSANA EM CORPUS ALARGADO
Parâmetro de avaliação
Tempo total despendido
Tempo despendido apenas na análise
Tempo máximo de análise de um segmento
Tempo de análise médio por segmento
Tempo de análise médio por unidade lexical
Tamanho do maior segmento (unidades lexicais)
Número de segmentos no corpus
Número de segmentos classificados
Número de frases identificadas
Máxima memória ocupada
93
Teste 1
4h 16m
3h 32m
1,01s
90ms
3,3ms
753
170 226
105 157
105 151
163 Mb
Teste 2
3h 35m
4h 18m
1,02s
91ms
3,4ms
753
170 226
168 021
168 021
164 Mb
Teste 3
5h 26m
4h 44m
2,63s
115ms
4,3ms
753
170 226
168 021
245 288
164 Mb
Teste 4
5h 31m
4h 48m
512s
389s
4,3ms
133 487
51
51
243 724
287 Mb
Tabela 6.5: Resultados obtidos na análise do corpus. teste 1 - sem opções; teste 2 - opção skips, teste
3 - skips e multiple; teste 4 - corpus segmentado por edição de jornal.
obtidas. O terceiro teste, foi realizado com as opções
e
. Finalmente, foi realizada a
e
,
análise das edições que constituem o corpus, sem segmentação e com as opções
implicando a análise de segmentos com dezenas de milhares de palavras. A tabela 6.5 apresenta os
resultados obtidos.
Teste 1: Análise de segmentos com parametrização por omissão
A análise segmentos com as opções por omissão implica que cada segmento corresponde à estrutura linguı́stica que se pretende analisar. Como se pode deduzir a partir dos elementos da tabela
6.5 , foram analisados em média 11,1 segmentos por segundo, que corresponde a uma média de 300
unidades lexicais por segundo.
Com esta parametrização, foi possı́vel identificar a estrutura sintáctica de cerca de 61,6% dos
segmentos. Os resultados obtidos podem ser consequência de 3 factores: (i) elementos incorrectos
sob o ponto de vista sintáctico; (ii) reduzida informação presente na gramática; (iii) qualidade da
segmentação prévia, que constitui um factor determinante na obtenção de resultados, na medida
em que cada segmento terá de corresponder exactamente à estrutura linguı́stica que se pretende
analisar – neste caso a frase.
Teste 2: Análise de segmentos com o parâmetro skips
A análise de segmentos com a opção
permite identificar uma estrutura linguı́stica num
segmento, mesmo que não contemple todas as unidades lexicais desse segmento, podendo vir a
ser desprezadas unidades lexicais no inı́cio ou no fim do segmento. A análise realizada com esta
parametrização permite identificar a estrutura de segmentos que não foram analisados devido à
existência de unidades lexicais incompatı́veis no inı́cio ou no fim do segmento, ou devido a falta de
cobertura da gramática.
Os resultados obtidos indicam que foi possı́vel identificar a estrutura de 98,7% dos segmentos
presentes no corpus, dos quais 37% apresentam análises incompletas. Foi também calculado que as
CAPÍTULO 6. AVALIAÇÃO
94
análises incompletas obtidas cobrem cerca de 42,2% das unidades lexicais presentes nos segmentos
correspondentes.
Teste 3: Análise de segmentos com os parâmetros skips e multiple
A coluna Teste 3, da tabela 6.5, mostra os elementos estatı́sticos resultantes da análise efectuada com esta parametrização. De uma forma geral observou-se um aumento dos tempos de
execução. Esta situação deve-se aos testes realizados após a identificação de uma estrutura incompleta, que prosseguem até esgotar todas as posições do segmento.
Tal como a parametrização anterior, a parametrização
e
permitiu identificar a
estrutura de 98,7% dos segmentos presentes no corpus. Contudo, as análises incompletas passaram
a cobrir 95,3% das unidades lexicais presentes nesses segmentos.
Teste 4: Análise de documentos não segmentados
Com este tipo de análise pretende-se perceber de que forma o SuSAna permite analisar segmentos com uma grande quantidade de palavras, realizando em simultâneo a sua segmentação
em frases. O objectivo pretendido é verificar o desempenho do sistema no tratamento de segmentos
com grande quantidade de unidades lexicais. Note-se que o algoritmo constrói um grafo que engloba
todas as unidades lexicais da frase.
A análise realizada com esta parametrização permitiu identificar 243 724 segmentos, que corresponde a uma redução de 1 564, relativamente aos segmentos identificados no Teste 3. Esta
redução é um indicador de que, estando a gramática correcta, a segmentação efectuada nos testes anteriores, ao nı́vel morfossintáctico, não foi efectuada da forma mais adequada. O conjunto
dos segmentos identificados permitiram cobrir cerca de 97,7% das unidades lexicais presentes no
corpus, o que corresponde a cerca de 2,5% mais cobertura do que o conseguido no Teste 3.
Análise do número de alternativas por resultado
Na análise sintáctica de superfı́cie é importante ter em consideração, por um lado, a cobertura
da gramática, e por outro, formas de limitar a explosão combinatória de resultados. Nos tópicos anteriores a gramática foi analisada em termos de cobertura, na medida em que se extraı́ram valores
acerca do número de segmentos analisáveis por essa gramática. Neste tópico, faz-se uma análise ao
número de alternativas originadas em cada resultado, de forma a verificar a eficácia dos mecanismos de limitação de resultados utilizados, nomeadamente: preferências e princı́pio psicolinguı́stico
da presença dos modelos mais longos.
A figura 6.5 apresenta, para cada uma das parametrizações, o número segmentos que foram
correctamente analisados, bem como a sua distribuição de acordo com o número de alternativas
em cada resultado. A figura mostra que grande grande parte dos resultados de uma análise são
constituı́dos por uma a duas alternativas, nos três casos de parametrização. Por exemplo, 37%
das análises efectuadas com a opção
são constituı́das por apenas uma opção. O número de
resultados com 1 a 4 alternativas encontra-se entre 77% e 80% nos primeiros dois casos, e 83% para
os dois últimos.
6.4. DESEMPENHO DO SUSANA EM CORPUS ALARGADO
95
Figura 6.5: Distribuição do número de alternativas que compõem o resultado da análise de cada
segmento.
A figura 6.6 mostra a relação que existe entre o número de soluções por segmento e o seu tamanho. Verifica-se que o número de alternativas de análise pode aumentar consideravelmente com
o tamanho do segmento, como era de esperar. Isto acontece porque a análise de um simples segmento pode levar a milhares de soluções. Para os resultados apresentados, o número de alternativas
máximo para o resultado da análise de um segmento, foi limitado a 1024, de forma a não aumentar
desmesuradamente os resultados.
Análise do número de soluções em função do seu número de unidades lexicais
A figura 6.7 mostra a contagem das análises obtidas em função do número de unidades lexicais
presentes nessas análises. A linha a tracejado, corresponde ao conjunto de segmentações obtido do
módulo de pós-análise morfológica.
Em termos de resultados obtidos com a parametrização por omissão (sem opções), pode
verificar-se que não foi possı́vel encontrar soluções para grande parte dos segmentos cujo tamanho varia de 21 a 55 unidades lexicais. Verifica-se ainda que a maioria dos segmentos têm um
tamanho de cerca de 39 unidades lexicais, e para esse tipo de segmentos, se consegue apenas cerca
de metade das análises.
A opção
permite que o resultado da análise de um segmento possa incluir apenas uma
parte das suas unidades lexicais. Como se verifica na figura 6.7, há um desvio para a esquerda, dos
resultados obtidos em função do conjunto dos segmentos. Isto acontece, porque são obtidas análises
cujo tamanho é inferior ao tamanho do segmento original.
Os resultados relativos às opções
e
, são quase coincidentes e correspondem
96
CAPÍTULO 6. AVALIAÇÃO
Figura 6.6: Número médio de soluções por segmento do corpus, em função do seu tamanho.
Figura 6.7: Distribuição das análises em função do número de unidades lexicais que as compõem.
6.4. DESEMPENHO DO SUSANA EM CORPUS ALARGADO
97
Figura 6.8: Média do número de soluções em função do número de unidades lexicais do segmento.
a um aumento do número de análises, com tamanho mais reduzido. Note-se que o número de
análises obtidas com tamanho inferior a cerca de 27 unidades lexicais é mesmo superior ao número
de segmentos existentes com esse tamanho.
O gráfico apresentado na figura 6.8, mostra o número médio de soluções em função do número
de unidades lexicais que constituem essas soluções. Os valores do gráfico para um determinado
tamanho, em termos de unidades lexicais, são calculados com base no número total de resultados obtidos com esse tamanho e com base no número total de soluções obtidas nesses resultados.
Verifica-se uma tendência para um aumento do número de resultados, em função do número de
unidades lexicais presentes nesses resultados.
Análise de tempos de execução em função do tamanho do segmento
Importa agora analisar o tempos de execução, em função do tamanho do segmento, isto é, do
número de unidades lexicais. A figura 6.9 mostra o tempo de análise médio por segmento, dado
em função do número de unidades lexicais presentes nesse segmento. Verifica-se que o tempo de
execução aumenta com o número de unidades lexicais presentes no segmento, como seria de esperar. Contudo, os resultados da figura consideram também o tempo de processamento utilizado
em segmentos dos quais não foi possı́vel extrair qualquer análise. A figura 6.10 mostra o tempo
de análise por palavra, tendo em conta o tamanho do segmento a que pertence. Os resultados
expressos na figura tomam em consideração os segmentos dos quais não foi possı́vel extrair qualquer análise. Assim, estes resultados correspondem ao tempo médio real de processamento de uma
palavra, sabendo o tamanho do segmento em que se encontra.
98
CAPÍTULO 6. AVALIAÇÃO
Figura 6.9: Tempo de análise dos segmentos em função do seu tamanho.
Figura 6.10: Tempo de análise por palavra, em função do tamanho do seu segmento.
6.5. SUMÁRIO
99
6.5 Sumário
Nos testes de comparação realizados entre o AF e o SuSAna, foram obtidas conclusões acerca
do funcionamento de cada um dos sistemas que é importante realçar. Em primeiro lugar, é importante considerar a flexibilidade de cada um dos sistemas, bem como os problemas relativos à sua
utilização. Nestes aspectos, o AF oferece reduzidas condições de utilização, em oposição ao SuSAna,
que ao longo de todos os testes realizados mostrou um elevado grau de robustez e flexibilidade. Por
outro lado, os resultados da comparação revelam que o AF produz, por vezes, resultados diferentes
do SuSAna, que após analisados se mostraram incorrectos. Também relativamente aos tempos de
execução, se verificou uma clara superioridade do SuSAna relativamente ao AF. Não foi, contudo,
possı́vel comparar os tempos de execução de cada um dos analisadores em função do tamanho das
frases, devido a erros de originados pelo AF.
No que diz respeito aos testes no corpus do Público, o SuSAna mostrou grande robustez e
permitiu fazer observações interessantes. Seria importante comparar os resultados obtidos com
outros sistemas, o que constitui uma tarefa difı́cil, por um lado, devido à dificuldade de obtenção
de ferramentas para a lı́ngua portuguesa, e por outro, devido à utilização de uma gramática ainda
pouco desenvolvida, no que diz respeito ao seu conteúdo. A gramática utilizada foi produzida com
vista à extracção de sintagmas nominais, deixando por descrever um grande conjunto de fenómenos
linguı́sticos, como é, por exemplo, o caso dos sintagmas verbais.
100
CAPÍTULO 6. AVALIAÇÃO
O trabalho realizado no âmbito desta dissertação compreendeu a concepção e desenvolvimento
de um módulo de análise sintáctica de superfı́cie para a lı́ngua portuguesa. O desenvolvimento
deste módulo – SuSAna – partiu de um estudo às várias técnicas de análise sintáctica e sistemas de análise de superfı́cie que as integram. Em particular, foi analisado o sistema de análise
sintáctica de superfı́cie de Hagège (2000), que compreende um protótipo de análise de superfı́cie
(AF) e uma gramática que constitui a sua fonte de dados. O desenvolvimento do SuSAna compreendeu três etapas: desenvolvimento de um algoritmo de análise sintáctica de superfı́cie eficiente,
em termos de complexidade; implementação do algoritmo num módulo; e a criação de ferramentas para a utilização e teste desse módulo tanto numa plataforma autónoma como em plataformas
cliente/servidor. O desenvolvimento do SuSAna foi também acompanhado pela criação de uma
gramática, baseada na gramática do AF, para a qual foram concebidos elementos, que permitem
representar informação adequada ao processamento sintáctico que se realiza com o SuSAna, e permitem incorporar a informação linguı́stica presente na gramática do AF.
O processo de análise é efectuado em duas etapas: a primeira consiste em construir estruturas
compatı́veis com a informação presente na gramática e a segunda consiste em filtrar as análises que
se podem obter a partir dessas estruturas. A gramática utiliza dois elementos que permitem definir
os tipos de restrições necessários à realização dessas duas etapas: o primeiro é definido à custa de
blocos; o segundo consiste num conjunto de preferências que permitem seleccionar o conjunto de
análises com melhor classificação a partir das análises possı́veis, obtidas em função do primeiro
tipo de restrições. O mecanismo de restrições permite, abranger um grande conjunto de fenómenos
linguı́sticos e obter um conjunto de hipóteses que serão, na segunda etapa, refinadas e reduzidas,
contribuindo assim para evitar conjuntos intratáveis de hipóteses de análise. As preferências foram
estendidas de forma a incluir elementos probabilı́sticos, permitindo classificar quantitativamente
os resultados, com base em observações em corpora. A gramática permite definir hierarquias de
sı́mbolos, que podem ser utilizados para reduzir o número de regras da gramática e aumentar a sua
legibilidade, contribuindo também para uma mais fácil manutenção.
O módulo de análise desenvolvido, além de implementar um algoritmo eficiente, é também
flexı́vel, tanto no que diz respeito às possibilidades de integração noutros sistemas, como em termos de realização da análise. O algoritmo foi concebido de forma a fazer uso da hierarquia de
sı́mbolos suportada pela gramática, que além de incluir categorias, permite também definir incluir
relações hierárquicas entre modelos. A aplicação das preferências é efectuada durante a análise,
aos constituintes da frase acabados de construir, contribuindo para uma redução da complexidade
da análise e consequente melhoria de desempenho. O mecanismo de procura do algoritmo permite
a sua utilização como um algoritmo anytime, integrável em sistemas que exigem baixos tempos de
CAPÍTULO 7. CONCLUSÕES E TRABALHO FUTURO
102
resposta. O conjunto de parâmetros aceites pelo SuSAna, tanto ao nı́vel da análise como ao nı́vel
da extracção de resultados, permite utilizar a informação obtida através da análise sintáctica, para
diversos fins. A parametrização ao nı́vel da análise permite, por um lado, considerar ou ignorar
restrições, como é o caso das preferências e do princı́pio psicolinguı́stico dos modelos mais longos,
e por outro, considerar variadas configurações nos segmentos a analisar. A produção de resultados
pode ser efectuada em diferentes formatos, adequados tanto à análise por parte do linguista, como
em sistemas computacionais.
A avaliação realizada mostra que, relativamente ao protótipo AF, o SuSAna é mais estável,
eficiente e obtém resultados mais precisos. A análise de 28 frases de um corpus, com os dois analisadores, mostrou que apenas 13 originaram o mesmo resultado e que nas diferenças obtidas nos
resultados das restantes 15 verificou-se que os resultados produzidos pelo AF eram inconsistentes.
Mostrou-se também que o sistema actual permite processar corpora não restrito, com um ritmo
médio de cerca de 300 palavras por segundo.
7.1 Trabalho futuro
Nesta secção enumeram-se alguns pontos de continuidade deste trabalho. Algumas destas
tarefas não foram efectuadas por limitações de tempo, outras por não se enquadrarem no âmbito do
trabalho proposto para esta tese. Do ponto de vista computacional é importante:
Introduzir regras de forma interactiva e semi-automática, com recurso a uma ferramenta de
interface e a partir de observações em corpora. A existência de uma ferramenta que possibilite
a escolha e rejeição de análises iterativamente permitiria criar, eliminar, ou re-ajustar os
elementos probabilı́sticos associados às preferências, de forma automática.
Criar uma ferramenta que permita verificar as possı́veis inconsistências nas regras da
gramática e reduzir a informação aı́ presente de forma automática, tendo em consideração
a hierarquia de sı́mbolos. No que diz respeito às inconsistências, de momento é possı́vel indicar que um dado modelo pode seguir um modelo dentro de , sem que o comportamento
de dentro de se encontre definido, o que faz com que a informação inicial não possa ser utilizada. A hierarquia de sı́mbolos pode ser usada para agrupar regras e torná-las mais claras.
Com efeito, dados dois blocos relativos a dois modelos e , com e os únicos elementos
subsumidos por um modelo , se os dois blocos contêm a mesma informação, poderá ser mais
claro criar um bloco associado a , e eliminar os anteriores.
Comparar o desempenho do sistema. Esta tarefa só pode ser realizada mediante a conversão
e utilização das gramáticas utilizadas noutros sistemas. Nesse sentido importa desenvolver
ferramentas de conversão automática de gramáticas.
A componente linguı́stica utilizada no âmbito do trabalho encontra-se ainda incompleta e melhorias
ao nı́vel desses recursos permitiriam obter resultados mais precisos. Indicam-se seguidamente os
pontos que se consideram mais importantes e este nı́vel.
Léxico: O dicionário que foi utilizado no decurso desta tese é reduzido e encontra-se orientado
para a extracção de sintagmas nominais. Uma maior cobertura lexical permitiria melhorar
7.1. TRABALHO FUTURO
103
os resultados obtidos para a análise. A introdução de informação acerca da sub-categorização
para classes gramaticais, como adjectivos, verbos e nomes, será uma tarefa inevitável para o
correcto processamento de textos reais.
Coordenação: A estratégia para o tratamento da coordenação neste trabalho consistiu em não
impor restrições à sua ocorrência, seguindo a estratégia também utilizada por Hagège (2000).
Hagège reporta que uma das fontes de erro na extracção SNs está justamente associada ao
não tratamento da coordenação, pois determinados SNs foram extraı́dos de forma incompleta
ou com demasiados complementos.
Gramáticas paralelas para outras lı́nguas: Por exemplo, o castelhano possui construções semelhantes às construções utilizadas no português, nesse sentido, a criação de uma gramática
da essa lı́ngua seria facilitada e permitiria efectuar estudos contrastivos acerca da estrutura
das lı́nguas, com base no processamento do SuSAna. Foi já demonstrado interesse por parte
de investigadores de uma universidade no México, em efectuar parte desta tarefa.
104
CAPÍTULO 7. CONCLUSÕES E TRABALHO FUTURO
Modelos
modelo
Descrição
m mn
m nnt
m an2
m an2q
m an2nq
madj
m an1
m prepn
m prepvn
m anp
madv
m advn1
m advn2
m advnp
mpp n
copv n
m unknown
ph
mnn rel
m virg
m conj
m ponct
copi n
que n
inf n
m cli
m reln
m ger
m se
modelo nominal nuclear
modelo nominal nuclear especial para tı́tulos
modelo adjectival nuclear do tipo 2
quantificado
não quantificado
modelo adjectival
modelo adjectival nuclear do tipo 1
modelo preposicional nuclear
modelo preposicional verbal nuclear
modelo adjectival preposicional
modelo adverbial
modelo adverbial nuclear do tipo 1
modelo adverbial nuclear do tipo 2
modelo adverbial nuclear preposicional
modelo de particı́pio passado nuclear
modelo de verbo copulativo nuclear
modelo onde ocorrem palavras desconhecidas
modelo de frase. Corresponde normalmente ao modelo de topo
modelo nominal nuclear para os relativos formados com cujo
elementos que contém: virg
elementos que contém: [coord, conj]
elementos que contém: [paro, parf, ponctu, ptvir] (pontuação)
elementos que contém: [prep] copinf. (verbos copulativos no infinitivo)
elementos que contém: [prep] qu
relativo aos verbos
elementos que contém: [cli ac, cli ad, cli c]
elementos que contém: [prep] rel
elementos que contém: ppres
elementos que contém: se
APÊNDICE A. DESCRIÇÃO DAS CATEGORIAS E MODELOS
106
Categorias
Nomes
Etiqueta
Descrição
nc
nc1
nc2
npr1
npr2
npr3
npr4
Nome comum
Nomes comuns contáveis
Nomes comuns massivos
Marte; Lisboa; Janeiro. (nunca precedidos por um artigo)
O Porto; O Tejo. (sempre precedidos de um artigo)
França. (por vezes precedidos de artigo e por vezes não)
Um tal Ferreira. (nomes próprios de pessoas)
Adjectivos
Etiqueta
Exemplos
nadj
adj1
adj2
adj3
vizinha (nome/adjectivo)
bela; belo
mero
portuguesa (adjectivos do tipo 3)
Advérbios
Etiqueta
Exemplos
advcomp
adv1
adv2
adv3
tao
pouco
adv mente
mais; menos
ainda; já; mesmo
muito; bastante
demasiado; apenas
tão
pouco
advérbios terminados em mente
107
Pronomes
Etiqueta
Exemplos
outro
cada
qualquer
vario p
ambos p
uns p
certo1
nenhum s
nenhum p
q3 s
q3 p
tanto s
tanto p
todo s
todo p
algum s
algum p
mesmo
tal s
tal p
próprio
outro; outra; outros; outras
cada
qualquer; quaisquer
vários, várias
ambos; ambas
uns; umas
certo; certa; certos; certas
nenhum; nenhuma
nenhuns; nenhumas
muito; pouco; bastante
muitos; poucos; bastantes
tanto; tanta
tantos; tantas
todo; toda
todos; todas
alguns, algumas
alguns; algumas
mesmo; mesma; mesmos; mesmas
tal
tais
próprio; própria; próprios; próprias
Outras classes de categorias
Etiqueta
Valor
card p
ord
poss
dem
cujo
artd
arti s
ppas
copinf
coord
virg
unknown
break
inconnu
eliminer
cinco. (numerais cardinais)
terceira. (numerais ordinais)
tua. (pocessivos)
este; aquele; esse. (demostrativos flexionados)
cujo. (pronome relativo)
o. (artigo definido)
um; uma. (artigo indefinido singular)
particı́pios passados
verbos copulativos no infinitivo
coordenação
vı́rgula
palavra desconhecida
separador de segmento
palavra desconhecida
categoria especial que pode ser ignorada
108
APÊNDICE A. DESCRIÇÃO DAS CATEGORIAS E MODELOS
Este capı́tulo apresenta alguma da terminologia utilizada na dissertaç ão. Alguns dos termos
apresentados resultam da tradução de termos utilizados na literatura internacional, caso em que
se apresenta tanto a lı́ngua de origem como o termo original, assim como referências às fontes e a
outras partes da dissertação onde é focado com maior profundidade.
algoritmo anytime Em termos genéricos, são Chunks Sintagmas com coerência, termos
algoritmos que satisfazem as três propriede arte (Exemplo: Desvio de padrão,
dades seguintes: 1- são tolerantes a probleDistribuição Normal, etc. Inglês: phrases
mas de
, isto é, podem ser susthat cohere, terms of art (like standard depensos por algum tempo sem que daı́ reviation, chi squared, normal distribution,
sulte um grande
etc.)
; 2- mesmo que
sejam interrompidos a qualquer instante,
conseguem devolver sempre uma resposta; Cobertura (recall) definida habitualmente
como sendo o número de respostas correc3 - as respostas que devolvem melhoram
tas, calculadas por um sistema, sobre o
em função do tempo. Gorz (1994) propõe
número total de respostas correctamente
a seguinte definição: um algoritmo é dito
esperadas. (ver precisão)
ser produtor se o programa que o
implemente conduzir a uma granularidade
na produção de resultados, compatı́vel com Cobertura lexical entendida com base no
número de formas diferentes validadas
as restrições de tempo do consumidor.
pelo léxico e às quais pode, eventualmente,
ser aplicada uma etiqueta.
API
Qualquer conjunto de rotinas, geralmente
disponı́veis para utilização por parte de Constituinte de uma frase é uma sequência de
unidades lexicais que fazem parte dessa
programadrers. O sistema operativ, por
frase e que se comportam como uma simexemplo, tem uma API para uma variedade
ples unidade. Um constituinte é um elede tarefas de manuseamento de discos e fimento que funciona como unidade numa
cheiros. As API são escritas para proporciconstrução semiótica de nı́vel superior.
onar código portável. O Programador apenas tem de se preocupar com a chamada e
os parâmetros da função e não com os deDTD
- O propósito
talhes de implementação, os quais podem
de um DTD é definir a correcta construção
variar de sistema para sistema.
dos blocos de um documento XML, SGML
ou HTML. O DTD define a estrutura de
um documento com uma lista de etiquetas
Chinks Pequenas palavras, delimitadoras que
e atributos permitidos para a construção
quebram as unidades com significado
do seu conteúdo, e que etiquetas podem
semântico (como um, de, é, etc.). Inglês: litser incluı́das dentro de outras etiquetas.
tle words, delimiters that break apart the
Pode ser declarado no próprio documento
meaningful units of thought (like a, of, is,
ou como uma referência externa.
etc.)
3
(
GLOSSÁRIO
110
Gramática descreve como uma frase pode ser
decomposta em sintagmas. Na construção
de uma gramática para uma dada linguagem, deve-se ter em conta a generalidade,
o conjunto de frases que a gramática analisa correctamente; selectividade que se define como o conjunto de não-frases identificadas como problemáticas; e compreensibilidade que se entende como a simplicidade
da gramática em si (Allen, 1995).
Reduz a complexidade do desenvolvimento de aplicações que se distribuem em
múltiplos sistemas operativos e protocolos
de redes, permitindo abstrair o programador dos detalhes subjacentes aos vários sistemas operativos e interfaces de rede. O
programador utiliza as funções definidas
por RPC como interface. (Rao, 1995). O
conceito de RPC tem sido discutido na literatura desde 1976, com implementações de
larga escala entre finais da década de 70 e
princı́pios da década de 80 (Birrell et al.,
1984).
Granularidade entendida como o grau de complexidade da informação associada às formas que o dicionário reconhece/valida, independentemente do formalismo utilizado
Sintagma é uma sequência de palavras que forpara as representar.
mam uma unidade significativa. Cada sintagma tem uma palavra principal, que é
Modelos são estruturas linguı́sticas que os
designada
por núcleo e outras palavras deanalisadores de superfı́cie AF e SuSAna
pendentes
desse núcleo. Ver Unidade Sinidentificam. Os modelos definem-se semtagmatica. Texto Editora: Conjunto de elepre à custa de um conjunto de propriementos
linguı́sticos que se ordenam como
dades. Um modelo para um conjunto de
complementos
de uma unidade maior. conpropriedades é uma sequência de sı́mbolos
junto
de
duas
ou mais palavras que posque satisfaz o conjunto das propriedades
suem
um
significado,
mas que por si só não
consideradas. Assumindo que as caracpodem
formar
uma
frase
completa.
terı́sticas morfossintácticas das palavras
correspondem ao conjunto de sı́mbolos, um
modelo para um conjunto de proprieda- Sintagma não recursivo Um sintagma diz-se
não recursivo se não puder ocorrer dentro
des linguı́sticas, no contexto da análise
dele
próprio. Propriedade: sendo A e B dois
sintáctica, é uma sequência de categosintagmas
não recursivos, se A ocorre denrias morfossintácticas que satisfazem estro
de
B,
ent
ão B não poderá ocorrer dentro
sas propriedades. Esta questão é focada na
de
A.
sub-secção 3.1.1.
Palavras funcionais palavras cuja função é,
em grande parte ou inteiramente, gramatical, como é o caso das preposições, artigos, pronomes e conjunções (APL e ILTEC,
1992).
subcategorização certos tipos de relações entre palavras e sintagmas. Dizemos que, por
subcaexemplo, um verbo como
tegorisa um SN.
Texto não restrito do inglês unrestricted text,
esta expressão é utilizada para designar
texto não processado ao nı́vel linguı́stico,
que pode oferecer dificuldades de tratamento do nı́vel computacional, uma vez que
pode conter, por exemplo: erros gramaticais, palavras desconhecidas e construções
- infra-estrutura
RPC
pouco comuns. (ver Texto Real)
cliente/servidor que aumenta a interoperabilidade, portabilidade, e flexibili- Texto real texto tal como existe. Erros gramadade de uma aplicação, permitindo que
ticais, palavras desconhecidas, construções
essa aplicação possa estar distribuı́da sopouco comuns, são alguns dos problemas a
bre múltiplas plataformas heterogéneas.
enfrentar na análise deste tipo de texto.
Precisão (precision) definida habitualmente
como sendo o número de respostas correctas, calculadas por um sistema, sobre o
número total de respostas, dadas por esse
sistema. (ver cobertura)
3
GLOSSÁRIO
111
Traço gramatical informação essencialmente
juntar estruturas compatı́veis numa estrurelevante para a relação de acordo, ou
tura mais geral e rejeitar as incompatı́veis.
de concordância, que se verifica entre,
por exemplo, o especificador e o núcleo.
São considerados traços sintácticos, ou XSLT Acrónimo de funcionais, os elementos que fornecem
- Linguainformação de pessoa, número, género e
gem declarativa que permite traduzir
caso (Chomsky, 1981).
documentos em formato XML noutros
documentos em formato XML ou em texto
Unidade Sintagmática é definida como sendo
arbitrário. O XSLT foi desenhado para
um agrupamento intermediário entre o
ser usado como parte do XSL, que é uma
nı́vel do vocábulo e o da oração. Desta
linguagem de estilos (
) para
maneira, um ou mais vocábulos unem-se,
o XML. O XSLT é concebido para ser
em sintagmas, para formar uma unidade
também usado independentemente do
maior, que é a oração.
XSL. Consultar http://xmlsoft.org/XSLT/ e
http://www.w3.org/TR/xslt/
Unificação técnica computacional que permite
- 2
112
GLOSSÁRIO
Abney, S. (1992). Prosodic Structure, Performance Structure and Phrase Structure. In Proceedings,
Speech and Natural Language Workshop, pp. 425–428. Morgan Kaufmann Publishers, San Mateo, CA.
Abney, S. P. (1991). Parsing by Chunks. In Berwick, R. C., Abney, S. P., e Tenny, C., editores,
Principle-Based Parsing: Computation and Psycholinguistics, pp. 257–278. Kluwer Academic Publishers, Dordrecht.
Abney, S. P. (1996). Part-of-Speech Tagging and Partial Parsing. In Church, K., Young, S., e Bloothooft, G., editores, Corpus-Based Methods in Language and Speech, chapter Dordrecht. Kluwer
Academic Publishers.
Afonso, Susana, Bick, E., Haber, R., e Santos, D. (2002). Floresta sintá(c)tica:a treebank for Portuguese. In Rodrı́guez, M. G. e Araujo, C. P. S., editores, Proceedings of LREC 2002, the Third
International Conference on Language Resources and Evaluation, pp. 1698–1703, Las Palmas de
Gran Canaria, Spain. ELRA.
Aho, A. V. e Ullman, J. D. (1972). The Theory of Parsing, Translation, and Compiling, volume II.
Prentice-Hall, Englewood Cliffs, NJ.
Allen, J. (1995). Natural Language Understanding. Benjamin/Cummings, Redwood City, CA, 2nd
edition.
APL e ILTEC, editores (1992). Dicionário de Termos Linguı́sticos, volume I e II. Edições Cosmos.
Associação Portuguesa de Linguı́stica e Instituto de Engenharia Teórica e Computacional.
Appelt, D. E. e Israel, D. (1999). Introduction to Information Extraction Technology. In IJCAI-99
Tutorial.
Araújo, P. (2003). Classificação de Poemas e Sugestão das Palavras Finais dos Versos. Tese de
Mestrado, Universidade Técnica de Lisboa - Instituto Superior Técnico, Lisboa. trabalho em
curso.
Aı̈t-Mokhtar, S. (1998). L’analyse présyntaxique en une seule étape. Tese de Doutoramento, Université Blaise Pascal, GRIL.
Backus, J. W. (1959). The syntax and semantics of the proposed international algebraic language of
the Zurch ACM-GAMM Conference. In Information Processing: Proceedings of the International
Conference on Information Processing, pp. 125–132, Paris.
114
BIBLIOGRAFIA
Batista, F. e Mamede, N. (2002). SuSAna: Módulo Multifuncional da Análise Sintáctica de Superfı́cie. In Gonzalo, J., Peñas, A., e Ferrández, A., editores, Proceedings of the Multilingual
Information Access and Natural Language Processing Workshop, pp. 29–37, Sevilla, Spain. IBERAMIA 2002.
Bick, E. (1996). Automatic Parsing of Portuguese. In Actas do II Encontro de Processamento da
Lı́ngua Portuguesa Escrita e Falada (EPLP 96).
Bick, E. (2000). The Parsing System Palavras, Automatic Grammatical Analysis of Portuguese in a
Constraint Grammar Framework. Aarhus University Press.
Birrell, D., A., Nelson, e J., B. (1984). Implementing Remote Procedure Calls. In ACM Transactions
on Computer Systems, number 2, pp. 39–59. ACM.
Bray, T., Paoli, J., Sperberg-McQueen, C. M., e Maler, E. (2000). Extensible Markup Language
(XML) 1.0 (Second Edition) W3C Recommendation. web document. http://www.w3.org/XML/.
Bès, G. G., Hagège, C., e Coheur, L. (1999). De la description des propriétés linguistiques à l’analyse
d’une langue. In VEXTAL, Venice, Italy. Poster.
Butt, M., King, T., Nino, M., e Segond, F. (1999). A Grammar Writer’s Cookbook. CSLI Publications.
Carroll, J., Briscoe, E., e Grover, C. (1991). A development environment for large natural language
grammars. Relatório Técnico 233, Computer Laboratory, Cambridge University, UK.
Chanod, J.-P. (2000). Robust Shallow Parsing and Beyond. Xerox Research Centre Europe.
Chomsky, N. (1956). Three Models for the Description of Language. IRE Transactions on Information
Theory, 2(3):113–124.
Coheur, L. e Mamede, N. (2002). From Syntax to Semantics: Taking Advantages of 5P. In Ranchhod, E. e Mamede, N., editores, Advances in Natural Language Processing, Third International Conference, Portugal for Natural Language Processing (PorTAL), pp. 79–82, Faro, Portugal.
Springer-Verlag, LNAI 2389.
Cole, R., Mariani, J., Uszkoreit, H., Zaenen, A., e Zue, V. (1995). Survey of the State of the Art in
Human Language Technology. http://citeseer.nj.nec.com/article/cole95survey.html.
Dowty, D. R., Karttunen, L., e Zwicky, A. M., editores (1988). Natural Language Parsing, chapter 9,
pp. 307–319. Cambridge University Press.
Earley, J. (1970). An efficient context-free parsing algorithm. Communications of the ACM, 13(2):94–
102.
Ejerhed, E. (1996). Finite state segmentation of discourse into clauses. In Proceedings of ECAI 96
Workshop Extended finite state models of language, pp. 24–33.
Fach, M. (1999). A Comparison Between Syntactic and Prosodic Phrasing. In Proceedings of Eurospeech 1999, volume 1, pp. 527–530, Budapest.
Frazier, L. e Fodor, J. D. (1978). The Sausage Machine: A new two-stage parsing model. Cognition,
6:291–325.
BIBLIOGRAFIA
115
Gansner, E. R., Koutsofios, E., North, S. C., e Vo, K. P. (1993). A Technique for Drawing Directed
Graphs. In IEEE Trans. on Soft. Eng., volume 3, pp. 214–230.
Gansner, E. R., North, S. C., e Vo, K. P. (1988). DAG – A Program to Draw Directed Graphs. In
Software – Practice and Experience, volume 17, pp. 1047–1062.
Giguet, E. (1998). Méthode pour l’analyse automatique de structures formelles sur documents
multilingues. Tese de Doutoramento, Université de Caen Basse-Normandie.
Gorz, G. e Kesseler, M. (1994). Anytime Algorithms for Speech Parsing? In Proceedings of COLING94, Kyoto.
Graham, S. L., Harrisson, M. A., e Ruzzo, W. L. (1980). An Improved Context-Free Recognizer. ACM
Transactions on Programming Languages and Systems, 2(3):415–462.
Grover, C., Carroll, J., e Briscoe, E. (1993). The Alvey Natural Language Tools grammar (4th release). Relatório Técnico 284, Computer Laboratory, Cambridge University, UK.
Hagège, C. (2000). Analyse Syntaxique automatique du portugais. Tese de Doutoramento, Laboratoire de Recherche sur le Language, Université Blaise Pascal, Clermont-Ferrand, GRIL.
Hagège, C. e Bès, G. G. (1999). Delimitação das construções relativas e completivas na análise de
superfı́cie de textos. In Actas do IV Encontro para o Processamento Computacional da Lı́ngua
Portuguesa Escrita e Falada PROPOR99, Universidade de Évora, Évora.
Hindle, D. (1983). User manual for Fidditch, a deterministic parser. Relatório técnico, Naval Research Laboratory.
Hindle, D. (1994). A Parser for Text Corpora. In Computational Approaches to the Lexicon, pp.
103–151. Oxford University Press, Oxford.
Jensen, K., Heidorn, G. E., e Richardson, S. D., editores (1993). PEG: The plnlp english grammar.
Natural Language Processing: The PLNLP Approach, chapter 3, pp. 29–45. Kluwer Academic
Publishers.
Jurafsky, D. e Martin, J. H. (2000). Speech and Language Processing. Prentice Hall.
Karlsson, F., Voutilainen, A., Heikkilä, J., e Anttila, A., editores (1995). Constraint Grammar: A
Language-Independent System for Parsing Unrestricted Text. Mouton de Gruyter, Berlin - New
York.
Kasami, J. (1965). An Efficient Recognition and Syntax Analysis Algorithm for Context-Free Languages. Relatório técnico, Air Force Cambridge Research Laboratory.
Kimball, J. (1973). Seven principles of surface structure parsing in natural language. Cognition,
2(1):15–47.
Koehn, P., Abney, S., Hirschberg, J., e Collins, M. (2000). Improving intonational phrasing with syntactic information. In 25th International Conference on Acoustics, Speech, and Signal processing
(ICASSP).
116
BIBLIOGRAFIA
Koskenniemi, K. (1983). Two-level Morphology. A General Computational Model for Word-form
Production and Generation. Number 11. Department of General Linguistics, University of Helsinki.
Koutsofios, E. e North, S. C. (1996). Drawing Graphs with dot.
Lavie, A. (1996). GLR* - A Robust Parser For Spontaneously Spoken Language.
LIMSI (2002). GRACE: Gramaires et Ressources pour les Analyseus de Corpus et leur Evaluation.
http://m17.limsi.fr/TLP/grace/.
Moll, R. N., Arbib, M. A., e Kfoury, A. (1988). An Introduction to Formal Language Theory. Springer
Verlag, New York, USA.
Naur, P., Backus, J. W., Bauer, F. L., Green, J., Katz, C., McCarthy, J., Perlis, A. J., Rutishauser, H.,
Samelson, K., Vauquois, B., Wegstein, J. H., van Wijngaarden, A., e Woodger, M. (1960). Report
on the algorithmic language ALGOL 60. Communications of the ACM, 3(5):299–314.
Norvig, P. (1992). Paradigms of Artificial Intelligence Programming. Morgan Kaufmann Publishers,
San Francisco, California.
Paulo, J. L., Correia, M., Mamede, N. J., e Hagège, C. (2002). Using Morphological, Syntactical, and
Statistical Information for Automatic Term Acquisition. In Ranchhod, E. e Mamede, N., editores,
Advances in Natural Language Processing, Third International Conference, Portugal for Natural
Language Processing (PorTAL), pp. 219–227, Faro, Portugal. Springer-Verlag, LNAI 2389.
Paulo, J. L. e Mamede, N. J. (2001). ATA - Automatic Term Acquisition. In Proceedings of the
Workshop on Extraction of Knowledge from Databases, pp. 51–54, Porto, Portugal.
Pavia, N. G. (1999). Using the Incremental Finite-State Architecture to create a Spanish Shallow
Parser. In XV Congres of SEPLN.
Pentus, M. (1993). Lambek Grammars Are Context Free. In Proc. of 8th Ann. IEEE Symp. on Logic in
Computer Science, LICS’93, pp. 429–433. IEEE Computer Society Press, Los Alamitos, Montreal,
Canada.
Petitepierre, D., Krauwer, S., des Tombe, L., Arnold, D., e Varile, G. (1987). A Model for Preference.
In Proceedings of the 3rd Conference of the European Chapter of the ACL.
Rao, B. R. (1995). Making the Most of Middleware. In Data Communications International, volume 12, pp. 89–96. Setembro.
Ritchie, G., Black, A., Pulman, S., e Russell, G. (1987). The Edinburgh/Cambridge Morphological
Analyser and Dictionary System. Relatório Técnico 10, Department of Artificial Intelligence,
University of Edinburgh.
Russell, S. J. e Zilberstein, S. (1991). Composing Real-Time Systems. In Proceedings of the Twelfth
International Joint Conference on Artificial Intelligence, pp. 212–217, Sydney, Australia.
Salton, G. (1989). Automatic Text Processing. Addison-Wesley Publishing Company.
BIBLIOGRAFIA
117
Schulze, B., Heid, U., Schmid, H., Schiller, A., Rooth, M., Grefenstette, G., Gaschler, J., Zaenen, A., e
Teufel, S. (1994). Comparative State-of-the-Art Survey and Assessment Study of General Interest
Corpus-oriented Tools. DECIDE - MLAP-Project 93-19, Deliverable D-1b.
Shieber, S. M. (1986). An Introduction to Unification-Based Approaches to Grammar. CSLI, Stanford.
Shieber, S. M., Schabes, Y., e Pereira, F. C. N. (1995). Principles and Implementation of Deductive
Parsing. Journal of Logic Programming, 24(1,2):3–36.
Stolcke (1995). An Efficient Probabilistic Context-Free Parsing Algorithm that Computes Prefix
Probabilities. In Computational Linguistics, MIT Press for the Association for Computational
Linguistics, volume 21.
Strzalkowski, T., editor (1994). Reversible Grammar In Natural Language Processing. Kluwer
Academic Publishers, Boston, London.
Tomita, M. (1987). An Efficient Augmented-Context-Free Parsing Algorithm. Computational Linguistics, 13:31–46.
Vergne, J. e Giguet, E. (1988). Regards Théoriques sur le Tagging. In actes de la cinquième
conférence Le Traitement Automatique des Langues Naturelles (TALN98), Paris, França.
Voutilainen, A., Heikkilä, J., e Anttila, A. (1992). Constraint Grammar of English. A PerformanceOriented Introduction. Number 21. Department of General Linguistics, University of Helsinki.
W3C (1999). XSL Transformations (XSLT) Version 1.0. Web site. http://www.w3.org/TR/xslt.
Xerces (2003). The Apache XML Project. http://xml.apache.org/. The Apache Software Foundation.
Younger, D. (1966). Context-Free Language Processing in Time
10(2):189–208.
. In Information and Control, pp.
Zechner, K. e Waibel, A. (1998). Using Chunk Based Partial Parsing of Spontaneous Speech in
Unrestricted Domains for Reducing Word Error Rate in Speech Recognition. In Proceedings of the
COLING / ACL98.
118
BIBLIOGRAFIA
algoritmo, 35, 62, 66
anytime, 68
CKY, 19, 26
CYK, 16
Earley, 19
GHR, 16
alternativas
frase, 34
ambiguidade, 17, 20, 36, 41
análise
complexidade da, 73
de superfı́cie, 4
hipóteses, 74
processo de, 62
resultados, 80
robusta, 5
sintáctica, 3
análises, 59
analisador
de Earley, 18
LR, 18
API, 58
aposição mı́nima, 7
arquitectura, 59
associação à direita, 7
avaliação
AF, 40
condições de, 40, 83
BNF, 14, 48
caminhos
registo de, 67
categorias
generalização de, 30
maximais, 30
não maximais, 30
CCG, 15
cobertura, 40
lexical, 4
coordenação, 37, 84, 88, 103
corpus, 80
custos
atribuição de, 66
identificação, 5
funcionamento
interno, 59
function composition, 20
DAG, 20, 31, 62–64, 67
DCG, 14
declaratividade, 25
desambiguação, 78
DOM, 91
DTD, 43, 56
grafo, 62
grafos
vértices do, 62
visualização, 77
gramática, 80, 83
gramáticas
livres de contexto, 14
paralelas, 103
grau de confiança, 47
elemento
bloco, 45
de topo, 45, 74
preference, 47
superclass, 46
estratégia, 8, 53
estruturas
incompletas, 78
múltiplas, 70
extracção
sintagmas nominais, 79
ferramentas
af2xml, 87
Jonction, 34
MPS, 33, 34, 40
Pasmo2Af, 85
SMORPH, 33
Fidditch, 23
formatos
contagens, 75
grafos, 77
Sintagmas, 77
Texto, 77
XML, 43, 75
fragmentos, 3, 59, 62
continuação de, 66
criação de, 63
definição, 59
HG, 15
Hierarquia de Chomsky, 13
Lambek
cálculo de, 19
gramáticas de, 19
late closure, 7
LIG, 15
low attachement, 20
módulo
de análise, 61
de extracção, 61
minimal attachment, 7
modelo
anterior, 32
break, 84
de topo, 30, 45, 70
definição, 43
não terminal, 44
superior, 32
terminal, 44
modelos, 45, 46
candidatos, 66
comportamento, 30
identificação, 29
ÍNDICE REMISSIVO
120
mais longos, 65, 72, 73, 80
previsão de, 78
motivação, 2
objectivos, 8, 53
operações
flechagem, 34
folhagem, 34
parâmetros
da análise, 68
de extracção, 75
precisão, 40
preferências, 20, 47, 72
contexto, 47
recuperação de texto, 79
repositório, 61, 62, 67
resultados, 80
AF, 34
extracção de, 74
formatos, 75
restrição de, 71
retrocesso, 17, 23
right association, 7
robustez, 9
RPC, 9, 54, 59
sı́mbolo
inicial, 14
não terminal, 14
terminal, 14
segmentos, 70
demarcação de, 70
estrutura, 56
shallow
parsers, 4, 21
syntax, 4
shift-reduce, 17, 18
sintagma nuclear, 38
sintaxe
de superfı́cie, 4
domı́nio, 3
sistemas
ATA, 79
Poeta, 79
SN
complementos, 40
SNs
existência de, 41
extracção de, 38
extractor, 39
teor, 41
TAG, 15
teorias
psicolinguı́sticas, 3, 6, 20
termos
extracção de, 79
texto real, 79
unidades lexicais
definição, 56
desprezar, 70
unificação
formalismos, 16
vértices
registo de, 67
visibilidade, 25
XML, 9, 55, 58, 75, 91
XSLT, 55, 85