Qual a proximidade entre gatos e ratos?

Apresenta o algoritmo de Levenshtein, que mede a distância de edição entre duas palavras ou expressões.
O algoritmo de Levenshtein é importante porque mede quão diferentes duas palavras ou textos são, contando quantas edições mínimas são necessárias para transformar um no outro.

Ele é útil para correção ortográfica, buscas aproximadas, detecção de similaridade, reconhecimento de voz, comparação de DNA, análise de dados textuais e qualquer aplicação que precise saber se duas sequências “parecem” iguais, mesmo quando têm erros ou variações.

Na nossa página na Internet há disponível um aplicativo para cálculo automatizado da distância de edição de palavras pelo algoritmo de Levenshtein:

https://www.robertocsantosrj.eti.br/a...

Veremos, neste vídeo, o passo a passo manual para a obtenção dos resultados da comparação entre as palavras gato e carta, sitting e Kitten e Petrópolis e Teresópolis.

No algoritmo de Levenshtein, cada posição da matriz representa o custo mínimo para transformar uma parte da primeira palavra em uma parte da segunda. Primeiro compara-se os caracteres atuais: se forem iguais, a substituição não custa nada; se forem diferentes, custa um. Em seguida, calcula-se o valor da célula considerando três possibilidades: remover um caractere da primeira palavra, inserir um caractere para aproximar as sequências ou substituir o caractere atual pelo correspondente da outra palavra. Inserções e remoções sempre têm custo um, enquanto a substituição varia conforme a igualdade dos caracteres. O menor desses três valores determina o custo acumulado até aquela posição.

No algoritmo de Levenshtein, constrói-se uma matriz onde a primeira palavra é colocada na horizontal, ao longo da linha superior, e a segunda palavra é colocada na vertical, ao longo da primeira coluna. O preenchimento é feito célula por célula, da esquerda para a direita e de cima para baixo. Em cada célula, calcula-se o custo mínimo para transformar o prefixo horizontal (da primeira palavra) no prefixo vertical (da segunda palavra).

A cada passo, olha-se para os dois caracteres envolvidos: o caractere da primeira palavra correspondente à coluna atual e o caractere da segunda palavra correspondente à linha atual. Se forem iguais, a substituição não acrescenta custo; se forem diferentes, ela custa um. Em seguida, observam-se três células que já estão preenchidas: a célula logo acima, que representa o custo de remover um caractere da primeira palavra; a célula à esquerda, que representa o custo de inserir um caractere para se aproximar da segunda palavra; e a célula na diagonal superior esquerda, que representa o custo de substituir (ou manter) o caractere atual. Inserções e remoções sempre acrescentam um, enquanto a substituição acrescenta zero ou um, dependendo da igualdade dos caracteres.

O menor desses três valores acumulados é colocado na célula atual. Esse processo se repete para cada combinação de coluna (caractere da primeira palavra) e linha (caractere da segunda palavra), até que toda a matriz esteja preenchida, produzindo ao final a distância de edição mínima entre as duas palavras.
--------------------------
Bem-vindo(a) ao RCSantos Scripts!
Aqui você encontra conteúdos de Ciência da Computação e áreas correlatas, incluindo: Programação, Análise de Dados, Matemática, Estatística, Inteligência Artificial, Big Data, Mineração de Dados, Computação Gráfica, Edição de Áudio e Vídeo, Automatização e muito mais.
Aprenda de forma prática e objetiva, com tutoriais, exemplos e dicas para aplicar no seu dia a dia ou em projetos profissionais.
Inscreva-se e fique por dentro das novidades e conteúdos exclusivos sobre tecnologia e ciência de dados:
   / @rcsantos_scripts