Um Estudo sobre Funções de Distância entre Palavras na Língua
Portuguesa
Reinaldo Viana Alvares, Rubem Mondaini
Universidade Federal do Rio de Janeiro – UFRJ – CT/COPPE,
Ilha do Fundão, 21.941-972, Caixa Postal 68511, Rio de Janeiro, Brasil
E-mail: [email protected], [email protected]
Resumo: Funções de distância entre pares de palavras correspondem a um número real r que,
caso pequeno, indica similaridade entre as mesmas. São importantes na avaliação de
Algoritmos de Stemming, uma vez que o método de Paice [1] requer amostra de palavras
dividida em ‘grupos conceituais’, tais que as palavras de cada grupo apontam para o mesmo
conceito. São comparadas cinco distâncias, quatro encontradas na literatura, e a última,
formulada e concebida neste trabalho.
Palavras-chave: Linguística, PLN, Funções de Distância.
1 Introdução
É comum observar que variações de uma palavra apontam para o mesmo conceito. Por exemplo,
os termos matemática e matemático apontam para a idéia matemática. A distância entre esse
par é pequena. Por outro lado, entre matemática e biologia é grande, pois a combinação de
letras dessas palavras é muito diferente.
Funções de distância entre um par de strings X e Y correspondem a um número real r
que, caso seja pequeno, indica que X e Y são similares. Caso contrário, diferentes. Esta pesquisa
introduz as distâncias encontradas em [2], apresenta uma função (DAbr) e um estudo de caso.
2 Funções de Distância
Em [2], são definidas quatro funções (D1, D2, D3 e D4). Dadas duas strings X = x0x1 ... xn e Y =
y0y1 ... yn’ é definida uma função lógica pi, usada para penalidade: pi = 0 se xi = yi com 0 ≤ i ≤
min(n,n’), 1 caso contrário. A pi vale 1 se na i-ésima posição entre as strings X e Y as letras são
diferentes. Caso X e Y tenham tamanhos diferentes, a menor string é completada com nulos.
Seja n +1 o comprimento das strings, e m a posição da primeira ocorrência de erro entre X e Y
(x0 = y0, x1 = y1, ..., xm-1 = ym-1, mas xm≠ym). Tem-se (D1, D2, D3 e D4) na Figura 01:
Figura 01 – Definições de D1, D2, D3, D4.
A seguir, o resultado de (D1, D2, D3 e D4) aplicado ao par <mergulhei, mergulhador>:
D1 = 0,01465; D2 = 0,26786; D3 = 1,07143; D4 = 0,68182.
3 A Função DAbr
A função DAbr, é dividida em três partes. A hipótese consiste em beneficiar uma região R, de
tamanho LEN(R), comum entre as palavras para o caso geral (III). Tal região corresponde à
maior subcadeia comum em posição contígua entre as strings. DAbr é assim definida:
0, se X=Y (palavras iguais) (I); 1, se X≠Y (palavras totalmente diferentes) (II);
Caso contrário,
(III)
1742
Para o exemplo DAbr(mergulhei, mergulhador), a região R é mergulh; LEN(R)=7 (caso
geral (III)). Assim, DAbr(mergulhei, mergulhador)=0,00781.
4 Estudo de Caso
Nesta seção é realizada uma análise de precisão das distâncias. Foram selecionadas 500 palavras
a partir de [3] A Tabela 01, apresenta três exemplos:
Tabela 01 – Resultados do experimento envolvendo pares retirados aleatoriamente da amostra.
X
Y
D1
D2
D3
D4
DAbr
abacaxi
renderá
caracterizado
apostavam
sinalize
caracterizadores
0,99609
1,74219
0,00021
1,99219
15,93750
∞
∞
0,13462
0,40385
1,77083
1,99219
0,32813
1.0
1.0
0,00012
A partir da Tabela 01, verifica-se que os valores das cinco medidas estão de acordo
com a definição de funções de distância. Já na Tabela 2 são encontrados exemplos dos valores
mínimo e máximo das funções:
Tabela 2 – Exemplos de pares de palavras para distâncias máximas e mínimas.
A partir da Tabela 02, nota-se que cada par de palavras, cujo resultado da função é
mínimo, aponta para o mesmo conceito. Já no caso de pares de palavras cujo resultado da
função é máximo, os termos representam conceitos diferentes.
5 Considerações Finais e Trabalhos Futuros
Foram apresentadas cinco funções de distância entre pares de palavras (D1, D2, D3, D4 e DAbr).
As quatro primeiras, extraídas da literatura. Já a DAbr, concebida e projetada nesta pesquisa. Os
resultados mostram que todas estão de acordo com a definição de função de distância.
Como continuidade, convém usar as distâncias em um processo de agrupamento
(clusterização) de palavras, avaliando-as em função da qualidade dos clusters obtidos.
6 Referências
[1] Paice, C.D.: “An evaluation method for stemming algorithms”. In Proceedings of the 17th
annual international ACM SIGIR conference on Research and development in information
retrieval. ACM Press. Pages 42-50, Dublin, Ireland, 1994.
[2] Majumder, P., Mitra,M., Parui, S.K., Kole, G.: “YASS: Yet another suffix stripper”. In
ACM Transactions on Information Systems(TOIS). 2007.
[3] Alvares, R. V.; Garcia, A. C. B.; Ferraz, I. N. STEMBR: a stemming algorithm for the
brazilian portuguese language. In: 12th Portuguese Conference on Artificial Intelligence.
2005.
1743