da teoria à prática - levenshtein


posted by qmx on 13 August 2010
http://www.flickr.com/photos/crosswordman/3930231228/sizes/s/in/photostream/

Normalmente, nossa área possui duas vertentes totalmente polarizadas: os práticos e os acadêmicos.

Antes de mais nada, espera-se de um bom profissional um equilíbrio interessante entre conhecimento acadêmico (não necessáriamente adquirido na academia) e o conhecimento prático.

Ambas as coisas são boas, o problema é a falta de equilíbrio entre as duas!

Vez por outra, alguns problemas da vida real se mostram verdadeiros “cases” para a aplicação de coisas altamente teóricas da academia, e como não podia deixar de ser, fui vítima me deparei com uma dessas recentemente.

Como comparar um dado oficial com um dado digitado por uma pessoa? A resposta inicial seria bem simples, não?

nome1 = “Av. Morvan dias de Figueiredo, nº 3600”
nome2 = “Av. Morvan dias de Figueiredo, nº 3600”

nome1 == nome2
=> true

O fato é que as coisas não são tão simples assim na vida real:

nome1 = “Av. Morvan dias de Figueiredo, nº 3600”
nome2 = “Av. Morvan dias de figueiredo, nº 3600”
nome1 == nome2
=> false

Oops, mas não é o mesmo nome?

O fato é que não é tão trivial assim fazer comparações de strings; o caminho natural seria imediatamente colocar tudo em maiúsculas ou minúsculas e comparar; daí teriamos os acentos esquecidos; depois teríamos alguém mais criativo:

nome1 = “Av. Morvan dias de Figueiredo, 3600”
nome2 = “Av. Morvan dias de Figueiredo, N 3600”
nome1 == nome2
=> false

Ué… mas não é o mesmo nome, qual o problema de retornar false? Isso se torna um problema enorme, já que tecnicamente as duas strings representam sim a mesma coisa! Nesse caso seria muito mais interessante medir a similaridade entre essas strings. Como fazer isso?

Existe um algoritmo muito interessante que calcula a quantidade de alterações que eu tenho que fazer pra que um grupo de dados fique igual ao outro, mais conhecido como Distância Levenshtein. Neste caso, ao comparar as duas strings usando levenshtein, obteria o valor 2. (tenho que colocar a letra “N” e mais um espaço, para que o nome1 fique igual ao nome 2, logo duas alterações).

Para conseguir um índice de similaridade, nada melhor do que inventar uma escala e tomá-la como base: elegi minhas regras elementares e cheguei em uma escala em porcentagem, seguindo esta fórmula:

indice de similaridade = 1 - (distância / tamanho da primeira string)

Isso vai chegar a um número interessante, no nosso caso como a string possui 36 posições, vamos ter um valor de 0.9444444444, ou seja, quase 95% de semelhança!

Claro que a regra não é tão abrangente, mas para simples comparações já ajuda, e muito!

Como a maioria dos algoritmos, esse também já possuía implementação open-source. Existe uma gem de ruby chamada text que se encarrega de implementar coisas comuns a análise textual. Então, encapsulei o código de comparação da similaridade entre strings e coloquei na minha gem de utilidades a canivete.

Veja o resultado final:

require 'rubygems'
require 'canivete/similarity'

string1 = “Av. Morvan dias de Figueiredo,  3600”
string2 = “Av. Morvan dias de Figueiredo,  N 3600”
string1.similarity_rate(string2)
=> 0.944444444444

Claro que isso pode não servir pra diversos casos, mas é bom conhecer esses algoritmos!

Você conhece mais algum caso? Comente!