[Cascavel-pm] Comparacao aproximada entre duas strings
Luiz Gonzaga
lgonzaga em lncc.br
Sábado Outubro 15 10:01:09 PDT 2005
Oi Marcos,
Este eh um problema que existe em bioinformatica, que eh fazer o
ALINHAMENTO de duas sequencias, sejam de nucleotideos (DNA), sejam de
aminoacidos (proteinas). Dependendo do tamanho das sequencias a serem
comparadas, os algoritmos podem ser bastante "pesados".
Agora estou sem acesso, mais existe um bom livro que demostra alguns
destes algoritmos implementados com perl. Vou procurar a referencia e
mando.
Mais simplicando, o algoritmo examina a alinhamento de caractere a
caractere e pontua se existe igualdade, substituicao ou insercao de
espacos. Se for um algoritmo de alinhamento local, ele procura pelas duas
maiores subsequencias de cadas sequencia, cuja pontuacao do alinhamento
seja a maior possivel. Se for um algoritmo de alinhamento global, ele
gerarah o alinhamento das duas sequencias completas.
No exemplo que voce mandou, teriamos um possivel alinhamento, como
exemplo:
||
WIM: an Information Mine --Model for the World Wide Web
WIM: an Information Mining Model for the -----------Web
^^ ^^^^^^^^^^^
E a pontuacao poderia se calculada da seguinte forma:
Igualdade: Soma + 1 (W=W, I=I, M=M etc)
Substituicao: Subtrae - 2 (e <=> i, " "<=>n)
Insercao de espaco (-): Subtrae - 2.
Extensao da insericao de espacos: Subtrae - 1
E a pontuacao, salvo erro de calculo, seria 21.
Se as sequencias forem pequenas, existem algoritmos baseados em
programacao dinamica, que apesar de terem uma complexidade quadratica, sao
satisfatoriamente rapidos.
Espero ter ajudado e quando eu achar as referencias envio.
Abracos, Luiz Gonzaga.
On Sat, 15 Oct 2005 00:05:14 -0300
Marco Modesto <marcoabmod em gmail.com> wrote:
> Alguem saberia me indicar um modulo ou função pra comparar se duas
> strings são próximas?
> -> Fazer a função não seria difícil, mas talvez alguém conheça algo
> pronto.
>
> Por exemplo:
> "WIM: an Information Mine Model for the World Wide Web"
> "WIM: an Information Mining Model for the Web"
> Possuem distância de 0.8. (este valor é apenas ilustrativo).
>
> Mas
> "A Practical Minimal Perfect Hashing Method"
> "WIM: an Information Mining Model for the Web"
> Possuem distância 0, ou seja não há semelhança alguma entre as strings.
>
> Usei o SoftTFIDF em Perl, mas em alguns casos que analisei ele
> retornou uma proximidade muito alta a duas strings completamente
> diferentes:
>
> SoftTFIDF em Java:
> http://secondstring.sourceforge.net/javadoc/com/wcohen/secondstring/SoftTFIDF.html
>
>
> obrigado,
>
> Marco.
> _______________________________________________
> Cascavel-pm mailing list
> Cascavel-pm em pm.org
> http://mail.pm.org/mailman/listinfo/cascavel-pm
>
Mais detalhes sobre a lista de discussão Cascavel-pm