[Cascavel-pm] Comparacao aproximada entre duas strings

[Luiz Gonzaga]

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
>