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.
- 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 XPAdivinhe 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.
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:
| ε | c | u | t | |
|---|---|---|---|---|
| ε | 0 | 1 | 2 | 3 |
| c | 1 | 0 | 1 | 2 |
| a | 2 | 1 | 1 | 2 |
| t | 3 | 2 | 2 | 1 |
(ε é a string vazia: ir de nada até “cu” exige duas inserções.)
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"))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.
Calcule a distância de edição
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
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.
Sugira uma correção
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
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…