Calculando a Distância de Edição em PHP com a Função levenshtein

1. Introdução

Quando um programa responsável por checar a ortografia de um documento encontra uma palavra que não faz parte de seu dicionário, esta é apontada como um possível erro ortográfico. Adicionalmente, o programa apresentará uma lista de sugestões, ou seja, uma relação de palavras que sejam próximas (ou similares) à palavra errada. A lista de sugestões é normalmente precedida por aquela famosa frase: “você não quis dizer... ?”.

Mas qual o critério utilizado para selecionar as palavras próximas? Qual a noção empregada para computar o quanto duas palavras são similares? A resposta está no conceito de distância de edição. Este artigo explica o conceito e apresenta exemplos de utilização na linguagem PHP.

2. Distância de Edição

A distância de edição é uma medida que compara duas strings, digamos str1 e str2, e retorna o número mínimo de caracteres que precisam ser modificados, inseridos ou excluídos para transformar str1 em str2. A ideia é que se duas strings possuem um valor baixo para a distância de edição então podemos considerá-las similares, já que transformar uma na outra requer um número baixo de operações.

Para que o conceito fique mais claro, considere que temos str1 = “DUDU” e str2= “EDU”. Como podemos proceder para transformar “DUDU” em “EDU”? Na prática, existem várias as maneiras possíveis, conforme veremos a seguir.

Para começar, na Figura 1 apresentamos uma maneira não muito inteligente de fazer a transformação. Neste exemplo, para transformar “DUDU” em “EDU” o seguinte procedimento foi executado: primeiro excluímos todas as letras de “D”, “U”, “D” e “U” e depois adicionamos todas as letras de “E”, “D”, “U”. O custo total é de 7 operações (4 exclusões + 3 inserções).

Figura 1: Transformação – Uma exemplo com custo alto

A transformação representada na Figura 1 não é nada inteligente porque é muito custosa. É possível transformar “DUDU” em “EDU” de uma forma muito mais inteligente e econômica em relação ao número de operações, conforme mostra a Figura 2. Neste exemplo a transformação foi feita da seguinte forma:

• Exclusão da primeira letra “D” de “DUDU”, gerando a palavra “UDU”;
• Troca do primeiro “U” por “E” em “UDU”, gerando a palavra “EDU”.

Desta forma, foram necessárias apenas 2 operações. Este é o número mínimo de operações necessárias para o exemplo (Ou seja: não há como transformar “DUDU” em “EDU” realizando menos de 2 operações).

Figura 2: Transformação – Uma exemplo com custo mínino

A medida da distância de edição retorna um número inteiro que representa exatamente o custo mínimo para transformar str1 em str2 (ou str2 em str1). Conforme dissemos anteriormente, quando esse custo é baixo, normalmente str1 e str2 são muito parecidas. Se, por um exemplo, um usuário digita a palavra “EXCESSÃO” (palavra com erro ortográfico) a distância de edição poderá nos ajudar a sugerir “EXCEÇÃO” (palavra com grafia correta) como uma correção, uma vez que o valor da distância de edição entre essas duas palavras é igual a 2 - um valor baixo.

A distância de edição, também é conhecida como distância de Levenshtein (nome do criador do algoritmo). Ela é tão popularmente utilizada que certas linguagens de programação, como o PHP, já possuem funções prontas para o seu cálculo. Para outras linguagens é fácil encontrar implementações prontas na Internet. Na seção seguinte apresentamos alguns exemplos de utilização da função em PHP.

2. Distância de Edição

Na linguagem PHP, a função que retorna a distância de edição entre duas strings chama-se “levenshtein” (um nome um tanto difícil de memorizar!). Sua forma de utilização é bastante simples, conforme mostra o exemplo da Listagem 1.

Listagem 1: Função “levenshtein” – exemplo inicial

<?php
//teste 1: "ABC" x "ABC"
$p1 = "ABC"; $p2 = "ABC";
$d = levenshtein($p1, $p2);
echo "dist $p1 -> $p2 = $d<br/>";

//teste 2: "MARCOS" x "ARCOS"
$p1 = "MARCOS"; $p2 = "ARCOS";
$d = levenshtein($p1, $p2);
echo "dist $p1 -> $p2 = $d<br/>";

//teste 3: "DUDU" x "EDU"
$p1 = "DUDU"; $p2 = "EDU"; 
$d = levenshtein($p1, $p2);
echo "dist $p1 -> $p2 = $d<br/>";

//teste 4: "MAMAO" x "MELAO"
$p1 = "MAMAO"; $p2 = "MELAO";
$d = levenshtein($p1, $p2);
echo "dist $p1 -> $p2 = $d<br/>";

//teste 5: "A" x "AVIAO"
$p1 = "A"; $p2 = "AVIAO";
$d = levenshtein($p1, $p2);
echo "dist $p1 -> $p2 = $d<br/>";

//teste 6: "SOLAR" x "ENSOLACAO"
$p1 = "SOLAR"; $p2 = "ENSOLACAO";
$d = levenshtein($p1, $p2);
echo "dist $p1 -> $p2 = $d<br/>";

//teste 7: "HELICOPTERO" x "PARALELEPIPEDO"
$p1 = "HELICOPTERO"; $p2 = "PARALELEPIPEDO";
$d = levenshtein($p1, $p2);
echo "dist $p1 -> $p2 = $d<br/>";

?> 

O resultado da execução do programa é:

Listagem 2: Resultado do primeiro exemplo

dist ABC -> ABC = 0
dist MARCOS -> ARCOS = 1
dist DUDU -> EDU = 2
dist MAMAO -> MELAO = 2
dist A -> AVIAO = 4
dist SOLAR -> ENSOLACAO = 5
dist HELICOPTERO -> PARALELEPIPEDO = 10

Vamos explicar alguns casos:

- str1 = “ABC” e str2= “ABC”

Nesse caso, a Dist. Edição = 0, já que as strings são iguais.

- str1 = ‘MARCOS’ e str2= ‘ARCOS’

Dist. Edição = 1. Basta uma operação para transformar str1 em str2, que consiste em apagar a letra “M” de str1

- str1 = ‘MAMAO’ e str2= ‘MELAO’

Dist. Edição = 2. Duas operações precisam ser realizadas para transformar str1 em str2. A primeira é inserir a letra “A” por “E” em str1 e a segunda é trocar “M” por “L” também em str1.

- str1 = ‘HELICOPTERO’ e str2= ‘PARALELEPIPEDO’

Dist. Edição = 10. Essa é mais complicada! Mas a Figura 3 ilustra um exemplo onde são realizadas 10 operações. São 4 exclusões + 5 modificações + 1 inclusão.

Figura 3: Conjunto de operações para transformar PARALELEPIPEDO em HELICOPTERO

Vamos agora apresentar um exemplo mais próximo de uma aplicação real para a função de distância de edição. Considere que possuímos um dicionário contendo nomes de bairros. Suponha que, a partir de um formulário, um usuário tenha digitado o nome “JDIM PAULIZTA” como nome do bairro onde mora. Este nome não encontra-se em nosso dicionáiro. Sendo assim, podemos comparar esse valor digitado com todo o conteúdo do nosso dicionário, encontrar o item com a menor distância de edição e sugerir esse item para o usuário. O código-exemplo é apresentado na Listagem 2.

Listagem 3: Função “levenshtein” – exemplo inicial

<?php
//dicionario
$dic[0] = "JARDIM PAULISTA";
$dic[1] = "JARDIM EUROPA";
$dic[2] = "ITAQUERA";
$dic[3] = "VILA MARIANA";
$dic[4] = "VILA MADALENA";
$dic[5] = "MORUMBI";
$dic[6] = "CENTRO";
$dic[7] = "PRACA DA ARVORE";

//TESTE: qual o nome mais similar à "JDIM PAULIZTA" no dicionário?
$bairro1 = "JDIM PAULIZTA";

$min_dist = 1000;
$sugestao = "";

foreach ( $dic as $item_dic)
    {
		$cur_dist = levenshtein($bairro1, $item_dic);
		echo "distancia edicao: $bairro1 -> $item_dic = $cur_dist<br/>";
		
		if ($cur_dist < $min_dist) {
			$min_dist = $cur_dist;
			$sugestao = $item_dic; 
		}
	}

echo " <br/><br/>bairro: $bairro1<br/>";	
echo "você não quis dizer $sugestao ?";	
	
?> 

Veja o resultado da execução:

Listagem 4: Resultado do segundo exemplo

JDIM PAULIZTA -> JARDIM PAULISTA = 3
distancia edicao: JDIM PAULIZTA -> JARDIM EUROPA = 8
distancia edicao: JDIM PAULIZTA -> ITAQUERA = 10
distancia edicao: JDIM PAULIZTA -> VILA MARIANA = 9
distancia edicao: JDIM PAULIZTA -> VILA MADALENA = 10
distancia edicao: JDIM PAULIZTA -> MORUMBI = 11
distancia edicao: JDIM PAULIZTA -> CENTRO = 13
distancia edicao: JDIM PAULIZTA -> PRACA DA ARVORE = 13

bairro: JDIM PAULIZTA
você não quis dizer JARDIM PAULISTA ?

Com este exemplo, encerramos o artigo sobre distância de edição em PHP. Até a próxima!