Comparação parcial de strings
Enviado por Blabos (blabosΘgmail·com):
“Algumas vezes temos que comparar textos que possuem erros de digitação, modificações, plágios, entre outros, nos quais uma comparação direta é inútil. Para esses casos precisamos de ferramentas que identifiquem trechos parecidos em strings.
Em outro texto publicado no Equinócio, mostramos algumas técnicas e módulos para trabalhar com comparação parcial de strings, que podem ser utilizadas entre outras coisas para sanitizar grandes massas de dados.” [referência: sao-paulo.pm.org]
• Publicado por Augusto Campos em
2011-03-09
@brlinuxblog
Feed RSS
Ótimo artigo com uma bela introdução.
Só um complemento bobo: o Peter Norvig uma vez explicou (de forma simplificada, claro) como funciona a correção (que não é bem “ortográfica”) da busca do Google, usando como exemplo um programinha que calcula, a partir de uma palavra original, palavras de distância 1 ou 2, e depois mede a frequência delas num dicionário.
http://norvig.com/spell-correct.html
Tem várias implementações lá feitas por outras pessoas em outras linguagens. Eu fiz uma em Java, baseado na implementação em Python dele (bem mais elegante a versão original em Python, claro).
Já eu gostaria de um programa que funcionasse ao contrário: pegasse um determinado texto e alterasse as palavras, mantendo o significado…
Brincadeira, é claro.
Podia ir mais fundo. Em geral, as mesmas técnicas que são usadas para encontrar palavras parecidas são usadas para encontrar “genes parecidos” e, mais que isso, fazer alinhamento genético, como o algoritmo de Smith-Waterman (alinhamentos locais) ou o de Needleman-Wunsch (alinhamentos globais) — vide o software livre que revolucionou a genética, o blast. Cabe lembrar que existe ainda a comparação múltipla de seqüências, em que você não tem só duas strings pra comparar, mas várias delas – e com algoritmos de comparação binária o custo computacional se torna exponencialmente proibitivo, razão pela qual são usados outros algoritmos.