Células preenchidas
Distância de edição
Letras mantidas

  • A preencher
  • Lida
  • Resposta

Mais sobre a distância de edição

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

  1. Escreva duas palavras: a primeira fica ao longo do lado esquerdo da tabela e a segunda ao longo do topo.
  2. 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.
  3. 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