- A preencher
- Lida
- Resposta
Distância de edição (distância de Levenshtein)
Quantas alterações de uma só letra transformam kitten em sitting? Três: substituir k por s, substituir e por i e acrescentar um g. Esse número é a distância de edição, e é assim que os corretores ortográficos ordenam as sugestões e os biólogos comparam genes. Escreva duas palavras e veja uma tabela encontrá-la. Prima Reproduzir para ver a tabela a encher-se, ou Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto. Escreva duas palavras: a primeira fica ao longo do lado esquerdo da tabela e a segunda ao longo do topo. Cada célula guarda o menor número de operações que transformam as letras até à sua linha nas letras até à sua coluna. No fim, as operações são lidas de trás para a frente a partir da célula do canto inferior direito. Novo exemplo escolhe outro par de palavras. Com o tabuleiro selecionado, as setas avançam e recuam um passo, a barra de espaço reproduz e pausa, e Home e End saltam para o início e o fim.
Como funciona
- Escreva duas palavras: a primeira fica ao longo do lado esquerdo da tabela e a segunda ao longo do topo.
- Prima Reproduzir, ou use Avançar e Recuar para ir um passo de cada vez. Arraste a barra de passos para saltar para qualquer ponto.
- Veja cada célula escolher o mais barato dos seus três vizinhos e, depois, as operações lidas de trás para a frente a laranja.
Como funciona a tabela
Uma célula guarda o menor número de operações que transformam as letras da primeira palavra até à sua linha nas letras da segunda palavra até à sua coluna. A primeira linha conta inserções, que constroem a segunda palavra a partir do nada, e a primeira coluna conta eliminações. Se as duas letras de uma célula forem iguais, ela copia a célula acima e à esquerda: não é preciso nenhuma operação. Caso contrário, vale mais um do que o menor de três vizinhos: acima e à esquerda para uma substituição, acima para uma eliminação e à esquerda para uma inserção.
Ler as operações de trás para a frente
A célula do canto inferior direito é a distância de edição. A partir daí, a aplicação descobre de que vizinho veio o valor da célula e passa para ele: na diagonal para uma letra mantida ou substituída, para cima para uma letra eliminada e para a esquerda para uma letra inserida. Lidos a partir do canto superior esquerdo, os passos formam uma lista de operações o mais curta possível, mostrada por baixo da tabela: uma letra simples é mantida, k→s é uma substituição, −e uma eliminação e +g uma inserção.
Perguntas frequentes
O que é a distância de Levenshtein?
É outro nome para esta distância de edição: o menor número de inserções, eliminações e substituições de uma só letra que transformam uma string noutra. Tem o nome de Vladimir Levenshtein, que a descreveu em 1965.
Qual é a distância de edição entre kitten e sitting?
3: substituir k por s, substituir e por i e inserir g no fim. A tabela mostra que não existe nenhuma lista de operações mais curta.
Quão rápido é o algoritmo da distância de edição?
Para palavras de comprimentos m e n, a tabela tem (m + 1)·(n + 1) células, cada uma preenchida num passo, por isso demora um tempo O(m·n). Se só for precisa a distância, bastam duas linhas da tabela.
Que outras distâncias de edição existem?
A distância de Damerau–Levenshtein conta também a troca de duas letras vizinhas como uma só operação, o que se adequa aos erros de digitação. A distância de Hamming só permite substituições e funciona para strings do mesmo comprimento. A distância LCS só permite inserções e eliminações.
Algum dado é enviado para algum lado?
Não. Tudo é calculado no seu navegador, e as suas últimas definições ficam guardadas no armazenamento local deste navegador.
Pronto para experimentar?
Abra o PictorX no seu navegador – sem instalação, sem necessidade de cartão de crédito para começar.
Ir para o editor