Carregando
0x50Lição 6 de 18

Meça a similaridade das palavras com a distância de edição

Conte as edições entre duas palavras e use-as para corrigir erros de digitação.

22 min Questionário com 6 perguntas 2 exercícios de código
Ao final desta lição, você saberá
  • Explique as três operações de edição e calcule a distância de edição manualmente
  • Preencha uma tabela de distância de edição com programação dinâmica
  • Crie um pequeno corretor ortográfico

Você digita “teh” e seu telefone sugere “the”. Como isso sabe? Um ingrediente chave: “teh” está a apenas algumas pequenas edições de “the” e muito mais longe de “dez mil”. A distância de edição (ou distância de Levenshtein) entre duas palavras é o menor número de inserções, exclusões e substituições de um único caractere que transformam uma na outra.

Experimente

Até 15 XP

Adivinhe a distância

Para cada par, adivinhe o menor número de edições antes de contar com cuidado - depois compare seu palpite com uma sequência de edições mais barata. Um bom hábito: primeiro alinhe as letras que as duas palavras compartilham.

Par de palavras 1 de 6Pontuação 0/0

cat para cut

Qual é o menor número de edições de uma letra (inserir, remover ou trocar)?

Computando: uma tabela de problemas menores

Tentar todas as sequências possíveis de edição seria inviável. A programação dinâmica constrói uma tabela em que a célula (i, j) contém a distância entre as primeiras i letras de uma palavra e as primeiras j letras da outra. Cada célula recebe o menor custo entre três movimentos:

  • excluir uma letra: célula acima + 1
  • inserir uma letra: célula à esquerda + 1
  • substituir uma letra, ou mantê-la se for igual: célula na diagonal superior esquerda + 1 ou + 0

Esta é a tabela para as palavras inglesas “cat” → “cut”. A resposta está no canto inferior direito:

εcut
ε0123
c1012
a2112
t3221

(ε é a string vazia: ir de nada até “cu” exige duas inserções.)

edit_distance.py
1def edit_distance(source, target):
2    previous = list(range(len(target) + 1))
3    for row, source_letter in enumerate(source, start=1):
4        current = [row]
5        for column, target_letter in enumerate(target, start=1):
6            substitution = previous[column - 1] + (source_letter != target_letter)
7            current.append(min(previous[column] + 1, current[column - 1] + 1, substitution))
8        previous = current
9    return previous[-1]
10
11print(edit_distance("kitten", "sitting"))
Saída
3

Um corretor ortográfico

Um corretor simples compara a palavra digitada com todas as palavras de um dicionário e sugere a mais próxima. Corretores reais (como aquele que Peter Norvig escreveu em cerca de 20 linhas) também preferem palavras mais comuns: “teh” é 2 edições de “the” e “tech”, mas “the” é muito mais provável.

Principais conclusões

  • Distância de edição conta o menor número de inserções, exclusões e substituições entre duas strings.

  • Programação dinâmica preenche uma tabela de respostas menores para que cada célula exija trabalho constante.

  • Correção ortográfica = candidatos com poucas edições + preferência por palavras comuns.

Quiz da aula

6 perguntas · aprovação com 5 acertos · até 50 XP

Ao passar, você conclui a aula e mantém sua sequência. As perguntas erradas voltarão em sessões de revisão.

Pratique: aplique NLP com Python

Experimente cada ideia de processamento de texto em Python, execute com entradas de exemplo e use os resultados para ver onde o método funciona ou falha.

Exercício 1

Calcule a distância de edição

+25 XP

Leia duas palavras em linhas separadas e imprima a distância de edição de Levenshtein. Cada inserção, exclusão ou substituição custa 1.

  • kitten → sitting
  • Uma substituição
  • Palavras idênticas
main.py
Carregando editor…

O Python é executado em um ambiente isolado no navegador, com limite de 60 segundos. O runtime é carregado pelo CDN do Pyodide; seu código permanece neste navegador.

Exercício 2

Sugira uma correção

+25 XP

A primeira linha é uma palavra com erro ortográfico. A segunda linha é um dicionário separado por espaços. Imprima a palavra do dicionário com a menor distância de edição até a palavra com erro ortográfico; se houver empate em vários, imprima o que vem primeiro em ordem alfabética.

  • Letras trocadas
  • Carta perdida
main.py
Carregando editor…

O Python é executado em um ambiente isolado no navegador, com limite de 60 segundos. O runtime é carregado pelo CDN do Pyodide; seu código permanece neste navegador.

Dúvidas sobre esta lição

Travou em algum ponto? Pergunte. Descobriu algo? Compartilhe. Explicar também é uma ótima forma de aprender.

Carregando publicações…