Name: Como medir a diferença entre palavras com a distância de Levenshtein
Uploaded: 2025-12-05T10:00:13Z
Description: O algoritmo de Levenshtein mede a distância de edição entre duas palavras ou expressões. O algoritmo de Levenshtein é importante porque mede quão diferentes...

O algoritmo de Levenshtein 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/computacao/aplicativos/como-medir-a-diferenca-entre- palavras-com-a-distancia-de-levenshtein

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.
---
Resumo:
O vídeo explica o algoritmo de Levenshtein, que mede a distância de edição entre duas palavras ou textos, contando o número mínimo de edições necessárias para transformar uma palavra na outra (0:33). O algoritmo é útil para correção ortográfica, buscas aproximadas, detecção de similaridade, reconhecimento de voz, comparação de sequências de DNA e análise de dados textuais (0:49).

Funcionamento do Algoritmo (1:48-2:45, 6:03-7:34):

Uma matriz é construída com a primeira palavra na horizontal e a segunda na vertical.
Cada célula da matriz representa o custo mínimo para transformar um prefixo da primeira palavra em um prefixo da segunda.
Comparam-se os caracteres atuais: se forem iguais, o custo de substituição é zero; se forem diferentes, o custo é um.
O valor de cada célula é calculado considerando três possibilidades: remover um caractere (custo da célula acima + 1), inserir um caractere (custo da célula à esquerda + 1), ou substituir/manter o caractere (custo da célula diagonal superior esquerda + custo de substituição).
O menor desses três valores é colocado na célula atual.
O processo se repete até que toda a matriz seja preenchida, e o valor final na célula inferior direita representa a distância de edição mínima entre as duas palavras.
O vídeo demonstra o cálculo manual para os pares de palavras:

Gato e Carta (1:38)
Sitting e Kitten (1:41)
Petrópolis e Teresópolis (1:44)
Uma ferramenta online para cálculo automatizado está disponível na página do autor (1:21).
--------------------------
Inscreva-se e fique por dentro das novidades e conteúdos exclusivos sobre tecnologia e ciência de dados:
https://www.youtube.com/@robertosantosscripts?sub_confirmation=1