Como encontrar a palavra mais parecida

Considere que você tem uma lista de palavras e pede para uma pessoa encontrar uma determinada palavra. Mesmo que a palavra esteja com um espaço no meio, faltando acento e com letras maiúsculas e minúsculas alternadas, o ser humano consegue perceber o padrão desejado e informar a linha onde está o termo. Se fosse um computador, seria preciso indicar um monte de exceções e possibilidades a serem consideradas ao comparar o termo a ser encontrado com cada elemento da lista. Quando processamos texto, estamos lidando com símbolos que carregam muito mais informação para ser computada do que números.

O problema em determinar quão semelhantes são duas palavras é enfrentado no caso de verificadores ortográficos, por exemplo. Ou também durante a integração de cadastros diferentes, onde o nome de uma pessoa pode aparecer escrito de formas um pouco diferentes. Até mesmo a comparação de documentos para verificar a existência de plágio. Existem diversos algoritmos para o computador encontrar a palavra mais parecida dentre uma lista de outras – alguns deles são exemplificados nos posts Comparison of String Distance Algorithms e Comparando textos aproximadamente quase parecidos.

O cientista russo Vladimir Levenshtein publicou um trabalho em 1965 com uma proposta de resolver esse problema. A distância Levenshtein (ou distância de edição) entre duas sequências de caracteres (também chamadas de “strings”) é dada pelo número mínimo de operações necessárias para transformar uma string no outra, sendo que essas operações podem ser a inserção, eliminação ou substituição de um carácter. Ao executar essa transformação em cada item da lista no termo informado, a palavra mais parecida é a que tem a menor distância Levenshtein. A distância de Damerau-Levenshtein (que também homenageia Frederick J. Damerau) difere da distância clássica de Levenshtein por incluir transposições entre suas operações permitidas, além das três operações clássicas de edição de um único caracter.

Outro algoritmo, o Soundex, codifica as palavras de acordo a sua pronúncia em inglês. O código Soundex para um nome consiste na primeira letra do nome seguida por três dígitos numéricos, que codificam as consoantes restantes. As vogais e consoantes com som parecido com o de uma vogal (Y, H, W) não são considerados. Consoantes com articulação próxima compartilham o mesmo dígito (por exemplo, as consoantes labiais B, F, P e V são codificadas como o número 1). Mais detalhes no artigo do Soundex na Wikipedia.

Exemplo

O R possui uma biblioteca com o algoritmo da distância Levenshtein já implementado – pacote stringdist. Para instalá-lo, use o seguinte comando no terminal R:

> install.packages("stringdist", dependencies=TRUE, lib="~/Rpacks")

A lista de palavras utilizada nesse exemplo contém os nome de referência de reservatórios (sem palavras repetidas), que compõem nomes de arquivos e de URLs. Ela deve ser gravada no arquivo de texto puro “lista_palavras.txt”, no mesmo diretório.

SUDESTE
PARANA
ITAIPU
BMONTE
MADEIRA
TPIRES
SUL
NORDESTE
NORTE

O script a seguir recebe o termo a ser procurado como um argumento, mas pode ser informado manualmente dentro do script como uma variável. Depois, grava na memória a lista de palavras, disponível no arquivo “lista_palavras.txt”. Por fim, chama a rotina para calcular a distância de Levenshtein para cada palavra na lista: se a distância for menor, então ele guarda o termo da lista como sendo a resposta. Como critério de desempate, um segundo algoritmo de cálculo de distância é implementado (soundex, no caso).

#!/usr/bin/Rscript
# Script para encontrar o termo de uma lista mais parecido com a palavra informada

# Definindo bibliotecas conforme endereço (suprimindo mensagens iniciais)
end_libs="~/Rpacks"
suppressPackageStartupMessages(require(stringdist,lib=end_libs))

# Receber termo a ser trabalhado
args = commandArgs(trailingOnly = TRUE)
termo = args[1]

# Abrir arquivo com lista de palavras de referência
lista = as.data.frame(read.table('lista_palavras.txt'))

for (i in 1:length(lista[[1]])){
	# Selecionar string da lista
	palavra = as.character(lista[[1]][i])
	# Calcular a distância de Damerau-Levenshtein
	dist = stringdist(termo,palavra,method='osa')
	# Calcular a distância baseada em "soundex encoding"
	dist2 = stringdist(termo,palavra,method='soundex')
	# Caso já tenha calculado alguma distância
	if (exists("ref")) {
		# Guardar a palavra com a menor distância
		if (dist < ref) {
			ref = dist
			ref2 = dist2
			resposta = palavra
		} else if (dist == ref) {
			# Usar cálculo de segunda distância como desempate
			if (dist2 < ref2) {
				ref2 = dist2
				resposta = palavra
			}
		}
	} else {
		ref = dist
		ref2 = dist2
		resposta = palavra
	}
}

# Imprime a palavra mais parecida com o termo de entrada
cat(resposta)
cat('\n') # Quebra de linha

Caso o termo possua duas ou mais palavras, informe-os dentro de aspas duplas ao executar o script ou na declaração da variável.

Note que ele supõe que o pacote tenha sido instalado em “~/Rpacks” e o binário do R esteja disponível em “/usr/bin/Rscript”. Para executá-lo, basta dar permissão de escrita ao arquivo (vide comando da primeira linha) e executá-lo conforme o comando da segunda linha (supondo que o arquivo seja salvo com o nome “levenshtein.R”):

chmod +x levenshtein.R
./levenshtein.R "Belo Monte"

Onde “Belo Monte” é a palavra (nesse exemplo) que você deseja buscar seu semelhante mais próximo na lista. Também pode ser executado como “Rscript levenshtein.R termo”, sem a necessidade de acrescentar a permissão de escrita.