Hélio
Marcos Paz de Almeida e
Kecia Aline Marques Ferreira
Universidade Federal de Minas Gerais – Departamento de Ciência da Computação
Belo Horizonte – Minas Gerais – Brasil
Junho de 2004
A grande quantidade de textos produzidos por meio ou para uso de dispositivos informatizados torna necessária a existência de artifícios que possibilitem a identificação e correção automática de eventuais erros presentes em tais textos. Pesquisas nesta área datam de algumas décadas atrás e tendem a continuar dada a complexidade do assunto em relação à estrutura das diferentes línguas existentes. Os algoritmos e técnicas propostos para correção automática de palavras têm escopo definido de acordo com os tipos de correção que eles pretendem realizar.
Este trabalho apresenta alguns conceitos importantes relacionados a esta área de pesquisa, descreve algumas técnicas propostas para solucionar o problema de detecção e correção de erros em textos e oferece uma visão geral do Verifica, uma ferramenta desenvolvida no DCC/UFMG com este propósito.
A verificação e a correção automática de textos em dispositivos computacionais é mais do que uma simples tarefa de auxiliar a edição de textos. Algoritmos e técnicas com este objetivo têm utilidade, por exemplo, em aplicações de reconhecimento de voz, máquinas de tradução e OCR.
Identificar um erro em um texto é diferente de corrigi-lo. Identificar significa perceber e apontar o erro cometido. Isso é realizado basicamente por uma consulta a um dicionário existente. A questão principal neste ponto é encontrar formas eficientes de se realizar tal consulta. Corrigir automaticamente uma palavra em um texto é um problema muito mais complexo do que identificar um erro, pois é necessário encontrar uma outra palavra que substitua a palavra errada.
A seguir, são descritas algumas técnicas de correção automática de palavras em textos e é apresenta uma visão geral da ferramenta Verifica.
Kukich [1] agrupa as técnicas de correção automática de palavras em textos em três categorias: a primeira delas consiste na identificação de erros de palavras; a segunda consiste na correção automática de palavras isoladas; a terceira, na correção automática baseada em contexto.
2.1
Detecção de erros em palavras (nonword error detection)
O objetivo deste tipo de técnica é identificar quando uma palavra não compõe uma lista de palavras ou dicionário pré-existente.
Trabalhos nesta área foram desenvolvidos nas décadas de 70 e 80 e envolvem principalmente técnicas para casamento de padrões e comparação de cadeias de caracteres para determinar quando uma palavra não está presente em uma lista de palavras ou dicionário pré-existente. [1]
O fator crítico para detectar erro em uma palavra isolada é a utilização de técnicas eficientes de pesquisa no dicionário. Além disso, a manutenção das palavras que compõem o dicionário é uma questão relevante; ele deve conter um número razoável de palavras comumente encontradas em textos para que o a verificação não aponte com muita freqüência detecções falsas. Por outro lado, um número demasiado grande de palavras pode fazer com que alguns erros não sejam detectados. Segundo Pacheco[2], é conveniente que o dicionário contenha palavras comumente usadas nos textos convencionais.
Kukich[1] descreve, entre outras, as seguintes técnicas de detecção de erros em palavras:
2.1.1
Análise de n-grama
Um n-grama é uma seqüência de n letras ou palavras, onde n geralmente é 1, 2 ou 3, respectivamente monograma, bigrama e trigrama. Esta técnica consiste em examinar cada n-grama de uma palavra de entrada e pesquisar em uma tabela de n-gramas válidos. Na Língua Portuguesa, por exemplo, np, nb e qrl são exemplos de n-gramas inválidos. Isso requer o preenchimento prévio da tabela de n-gramas, por exemplo, a partir do pré-processamento de um dicionário.
A forma mais simples de implementação de um bigrama é por meio de uma matriz 26X26. Cada posição da matriz representa a combinação de duas letras do alfabeto; possui valor 1 quando a combinação entre as letras é válida para pelo menos uma das palavras que compõem o dicionário, e possui valo 0, caso contrário.
2.1.2
Pesquisa em dicionário
A técnica mais comum para implementar pesquisa em dicionário é o uso de tabela hash. Neste método, os registros armazenados em uma tabela são diretamente endereçados a partir de uma transformação aritmética sobre a chave de pesquisa”. [3]. Uma implementação para o tipo de dados abstrato Dicionário é mostrada por Ziviani [3].
2.2
Correção de palavras isoladas (isolated-word error correction)
As técnicas elaboradas com esta característica detectam e proporcionam a correção de erros em palavras isoladas no texto. Estudos nesta área foram iniciados na década de 60.
Em algumas ferramentas, a correção é realizada com a intervenção do usuário. Em outras circunstâncias, porém, pode ser necessário que a correção seja automática; neste caso, a própria ferramenta decide como o erro será corrigido.
As técnicas para esse tipo de correção seguem geralmente três passos: detecção do erro, geração de correções candidatas e ordenação das correções candidatas. Algumas vezes, este último passo é dispensado. A questão principal neste tipo de correção é a geração de correções candidatas.
Alguns estudos encontraram padrões nos tipos de erros cometidos na edição de palavras [1]. São conclusões de tais estudos:
- muitos erros são instâncias simples de inserção, exclusão, substituição ou transposição de caracteres, ou seja, há uma tendência de se cometer apenas um desses tipos de erro na edição de em uma palavra;
- uma palavra grafada erradamente tende a um caractere de sua grafia correta;
- poucos erros ocorrem na primeira letra da palavra.
Este trabalho descreve dois grupos de técnicas para este tipo de correção: distância mínima de edição e similaridade de chaves.
2.2.1
Distância mínima de edição
Distância mínima de edição: “é a quantidade mínima de operações de edição (inserção, exclusão e substituição) necessária para transformar uma cadeia de caracteres em uma outra”. Em geral, algoritmos baseados neste conceito requerem m comparações entre a palavra e o dicionário, onde m é o número de entradas do dicionário. [1]
2.2.2
Similaridade de chaves
Similaridade de chaves consiste em mapear toda palavra em uma chave tal que palavras com grafias semelhantes tenham a mesma chave. A vantagem desta técnica é que não é necessário comparar a palavra com todas as palavras do dicionário para encontrar as correções candidatas. Kukich[1] cita um exemplo antigo desta técnica: o sistema SOUNDEX[1918] ; ele mapeia uma cadeia de caracteres em uma chave composta pela primeira letra mais uma seqüência de dígitos, determinada de acordo com a regra abaixo. Zeros e repetições de caracteres eliminados da chave resultante.
A, E, I, O, U, H, W, Y : 0
B,
F, P, V : 1
C,
G, J, K, Q, S, X, Z : 2
D,
T : 3
L : 4
M, N : 5
R : 6
Assim, temos como exemplos da aplicação destas regras: WEKK – W022 – W2 | WEEK – W002 – W2 | WEAK – W002 – W2.
2.3
Correção dependente de contexto (context-dependent word correction)
As classes de técnicas descritas anteriormente não resolvem o problema de uma palavra grafada corretamente ser utilizada no lugar de outra, ou seja, não consideram a estrutura sintática em que a palavra foi utilizada.
Segundo Pacheco[2], a estrutura sintática da frase é um componente importante na maioria dos processos associados com a utilização de linguagem natural. Um problema não trivial envolvido neste tipo de análise é a necessidade de se categorizar palavras.
Kukich [1] aponta duas formas para o tratamento deste tipo de erros, o uso das técnicas de Processamento de Linguagem Natural (Natural Language Processing) e a Modelagem Estatística de Linguagem (Statistical Language Modelling).
2.3.1
Processamento de linguagem natural (PLN)
Utilizando as técnicas de processamento de linguagem natural, considera-se que um erro em uma palavra seja uma violação das regras do PLN, e então aplicam-se as ferramentas do PLN para realizarem a tarefa de buscar e corrigir o erro.
Na pesquisa em PLN, consideram-se 5 níveis de regras: o lexico, o sintático, o semântico, o da estrutura do discurso e o pragmático.
Erros em palavras são considerados erros do nivel léxico, pois violam as regras da criação de palavras válidas. Erros de concordância entre sujeito e verbo são considerados como erros sintáticos, assim como outros erros que resultem na substituição de uma palavra em uma frase por outra palavra de uma categoria que não satisfaça o contexo.
Erros que não violam regras sintáticas mas ainda assim causam anomalias semânticas são considerados erros semânticos, como por exemplo “Te vejo em cinco minuetos”. Erros que violam as relações de coerência inerente em um texto são considerados erros de estrutura de do discurso, como por exemplo “Tenho três filhos, Carlos e Miguel”. Já um erro que reflete uma anomalia relacionada às metas ou aos planos dos participantes do discurso são classificados como erros pragmáticos, como por exemplo “Eu curso ciência da comunicação” (quando se queria dizer computação).
2.3.2
Modelagem Estatística de Linguagem (MEL)
Os modelos estatísticos de linguagem são essencialmente tabelas de estimativas de probabilidade condicional para algumas ou todas as palavras em uma linguagem que especificam a probabilidade de uma palavra ocorrer dentro do contexto de outras palavras.
Por exemplo, um MEL de trigrama de palavra especifica a distribuição de probabilidade para a próxima palavra, condicionada pelas duas palavras anteriores. Já um MEL de bigrama parte do discurso especifica a distribuição de probabilidade da parte do discurso da próxima palavra condicionado pela parte do discurso da palavra anterior. Um MEL de colocação especifica a distribuição de probabilidade para certas palavras ocorrerem a uma certa distância de outra palavra lingüisticamente relacionada (por exemplo, a cinco posições, seja para a direita ou para a esquerda).
As técnicas de correção automática de palavras em textos têm como exemplos de aplicações:
- Aconselhamento de palavras em editores de textos
- Sistemas de reconhecimento de voz
- Máquinas de tradução
-
OCR (Optical
Character Recognition)
Verifica[2] é uma ferramenta de auxílio à redação desenvolvida no DCC/UFMG. É um sistema para verificação e aconselhamento de palavras da Língua Portuguesa para usuários do Latex.
O sistema utiliza um autômato finito determinístico para armazenar um dicionário de aproximadamente 242 mil palavras. Segundo Pacheco [2], “um autômato é uma estrutura de dados eficiente para o armazenamento de léxicos por prover uma maneira compacta para armazenamento do vocabulário e garantir eficiência de acesso ao mesmo. A compactação é garantida pelo compartilhamento de trechos comuns existentes entre palavras do vocabulário. A complexidade da pesquisa pela ocorrência de uma palavra armazenada nesta estrutura é linear com relação ao tamanho da palavra pesquisada.”
Quando uma palavra não é encontrada no dicionário, o sistema oferece sugestões de correções. Para isso, utiliza as regras abaixo definidas em função dos tipos de erro mais comuns ocorridos durante digitação de textos. Cada candidata obtida com a aplicação destas regras é pesquisada no dicionário.
- substituição: faz a substituição de cada caractere da palavra por todos os outros caracteres do alfabeto;
- exclusão: tenta inserir cada caractere do alfabeto em todas as posições da palavra;
- inserção: gera-se uma palavra candidata removendo-se cada um dos caracteres da palavra original;
- transposição: faz a troca de caracteres dois a dois na palavra original;
- fonética: tenta a substituição de fonemas por outros de mesmo som (ch por x, ss por ç, sc por ç, ss por ç, qu por c, e vice-versa.
A identificação e correção automáticas de palavras em texto são uma questão importante por que documentos escritos são formas essenciais de comunicação para o ser humano. É importante garantir que a representação simbólica de palavras chegue aos dispositivos computacionais na sua forma correta.
São questões importantes nos algoritmos para correção automática de palavras em textos: forma compacta para armazenar o dicionário; tempo de resposta da pesquisa no dicionário; definição das palavras que devem compor o dicionário
Pesquisas nesta área iniciaram há algumas décadas e estão em continuidade, principalmente no campo da correção automática dependente de contexto. Este é um problema de ordem prática cuja solução não é trivial.
- Pesquisa para apurar melhor os padrões de erros de ortografia cometidos.
- Pesquisa de métodos para análise sintática de textos
- Continuidade dos estudos a respeito de categorização sintática desenvolvidos por Pacheco[2].
[1] Kukich, K. 1992. Techniques for Automatically Correcting Words in
Text. ACM Computing Surveys, Vol.24, Nº 4, Dec. 1992.
[2] Pacheco, H. C. F. Uma Ferramenta de Auxílio à Redação, Dissertação de Mestrado DCC/UFMG, 1996
[3] Ziviani, N. Projeto de Algoritmos com Implementações em Pascal e C, Pioneira Thomson Learning, 2004, segunda edição. (Livro Texto)