Faxina depois da festa

December 16, 2008 · Posted in Perl 

“Não só de regex vive o monge, mas de todo módulo que há no CPAN.”

Recentemente fui incumbido da ingrata tarefa de realizar determinada atividade de trás para frente. O bom senso nos diz que a melhor hora para higienizar (ou sanitizar) dados em um sistema é em algum momento antes de eles entrarem na base de dados. Isso poupa enormes dores de cabeças, inclusive por SQL Injection.

Infelizmente (ou felizmente) o mundo real não é um mundo ideal e algumas vezes os dados precisam ser higienizados dentro do banco. No meu caso, haviam várias empresas cada uma com uma base de “clientes” que foi digitada à mão. Em um dado momento essas empresas se fundiram e unificaram as bases numa só (pelo menos foi o que me contaram), e tempos depois resolveram disponibilizar essas informações (basicamente endereços) via web.

O pequeno detalhe é que cada base tinha suas próprias inconsitências, que depois de juntas culminou em uma massaroca de dados contendo todas as inconsistências juntas. O que fazer agora? Como fazer agora?

A solução encontrada para higienizar esses endereços foi utilizar uma aplicação que pegasse cada endereço, um por um e comparasse com a base do Diretório Nacional de Endereços.

Por uma questão de performance a lnguagem Perl foi adotada. Das outras opções, a mais rápida levaria cerca de algun anos rodando ininterruptamente para resolver o problema, com uma qualidade questionável.

O principal problema em si, não era o que fazer, mas o como fazer. Simplesmente utilizar uma regex não resolveria porque tínhamos erros de digitação como:

‘rua do caximbo’ ao invés de ”Rua do Cachimbo’
‘Rua Marai das Graças’ ao invés de ‘Rua Maria das Graças’

Tentar adivinhar cada combinação possível de erro iria levar mais tempo do que executar a aplicação. Tivemos que apelar para os algoritmos de comparação de string. Para a alegria da galera existe uma penca de módulos no CPAN para isso, bastava escolher qual o mais adequado.

Text::Soundex

Esse bateu na trave. Ele utiliza um algoritmo fonético para detectar palavras parecidas de acordo com a sua pronúncia em Inglês… Resolveria vários erros de ortografia, se os endereços fossem expressões em inglês.

Text::Levenshtein

Outro módulo interessante. Usa o algoritmo “Levenshtein edit distance”, uma medida de “distância” entre strings baseada no número de inserções, deleções e substituições feitas em uma para que ela se torne a outra e vice versa.

Em nossos testes de amostragem ele se mostrou mais rápido que o String::Trigram, porém com uma qualidade inferior nos resultados. A própria documentação diz que ele não é adequado para esta tarefa.

String::Trigram

O módulo String::Trigram de Tarek Ahmed foi o que melhor respondeu aos nossos testes de amostragem. Ele utiliza o algoritmo dos n-gramas, que consiste em transformar a string um conjunto de blocos especiais de n caracteres, os n-gramas, e comparara os conjuntos de cada string. Dessa comparação sai uma taxa de similaridade entre as strings. Por exemplo:

carreta: {car arr rre ret eta}
careta: {car are ret eta}

(n-gramas coincidentes)/(total de n-gramas) = Taxa de similaridade
3/6 = 50%

O módulo também possui várias opções de ajuste fino.

Outros Módulos

Outros módulos como o String::Similarity e o String::Approx foram analisados mas ambos utilizam os algoritmos de distância analisados anteriormente, e pelo mesmo motivo foram descartados.

A n-Gramática

Pode parecer estranho que o algoritmo de n-gramas se saia melhor que um de distância, mas foi o que melhor funcionou com os nossos dados. Além do mais o módulo permite que criemos uma espécie de cache com uma base de comparação, no caso os endereços do DNE.

Dada uma lista de palavras (endereços limpos vindos da base DNE), ele calcula os n-gramas e os armazena como chaves de um hash uma única vez. Cada vez que uma palavra é checada contra a base, essa palavra é quebrada também em n-gramas que são procurados no hash da base. No final o módulo retorna a lista das palavras da base que mais se aproximam da palavra checada, limitadas pelo grau mínimo de similaridade que for configurado.

Aplicando

A aplicação final separava os endereços por CEP e gerava uma micro-base com poucas ruas, facilitando o trabalho de comparação. Depois atualizava ou não o endereço na base de dados “suja” dizendo qual a taxa de similaridade entre o endereço digitado e a base DNE. Tudo isso é claro, feito em vários processos paralelos, jogando o gargalo na capacidade do banco de dados de fornecer e atualizar os dados.

Tempo estimado para processar toda a base? Cerca de 3 meses. Taxa de endereços higienizados com sucesso? 97%

Abaixo um pequeno esboço de como utilizar o String::trigram

#!/usr/bin/perl
 
use strict;
use warnings;
 
use String::Trigram;
 
## Somente para o Wordpress não cagar o layout...
## Ninguém popula array assim, ok!
my @base;
push @base, qw/rato boi tigre coelho dragao serpente/;
push @base, qw/cavalo carneiro macaco galo cao porco/;
 
## Assim é mais adequado.
my @words = qw/ratos drogao cavalo caval carneir camelo galinha/;
 
my $min_sim = 0.20; ## 20%
 
my $trig = String::Trigram->new(
    "cmpBase"           =>  @base,
    "minSim"            =>  $min_sim,
    "warp"              =>  1,
    "ignoreCase"        =>  1,
    "keepOnlyAlNums"    =>  1,
    "ngram"             =>  3,
    "debug"             =>  0,
);
 
for my $animal (@words) {
    my (@best_matches, $sim);
 
    $sim = $trig->getBestMatch($animal, @best_matches);
 
    $sim = int( 0.5 + 100 * $sim );
 
    if ($sim >= $min_sim) {
        print "Similaridade entre $animal e $best_matches[0]:t$sim%", $/;
    }
}

Link úteis, ou não…

Comprehensive Perl Archive Network
Pesquisas no CPAN
String::Trigram no CPAN

Tags: no tags

Comments

  • Daniel Mantovani

    Fantástico tem que ir para o perl.org.br

    Foi uma maneira muito inteligente de se fazer uma coisa.

    Blabos, agora que você está de férias bem que poderia dar algumas palestras em universidades e expandir a cultura Perl no país. Este seu artigo seria um puta de um exemplo de como Perl é poderoso, e como programadores de Perl são fodas.

  • Daniel Mantovani

    Fantástico tem que ir para o perl.org.br

    Foi uma maneira muito inteligente de se fazer uma coisa.

    Blabos, agora que você está de férias bem que poderia dar algumas palestras em universidades e expandir a cultura Perl no país. Este seu artigo seria um puta de um exemplo de como Perl é poderoso, e como programadores de Perl são fodas.

  • Dona Maria

    Nem pensar!

  • Dona Maria

    Nem pensar!

  • http://twitter.com/renato_cron Renato Santos Souza

    Precisamos fazer isso aqui na empresa, mas na verdade, o problema é nas ruas que estão sem CEP.

    Temos a base do correio (atualizada a cada 2 meses).
    no seu caso,
    o gargalo era esperar o correio (que é um site bem lento, rs) ?

  • http://blabos.org Blabos de Blebe

    Nada. O gragalo tava no banco desnormalizado e seu tamanho. A simples adição de alguns índices fez a performance melhorar bastante.Também tínhamos a base de dados dos correios em Oracle.

blog comments powered by Disqus