Na linguística computacional e na ciência da computação , a edição de distância é uma maneira de quantificar como duas cadeias diferentes (por exemplo, palavras) se relacionam contando o número mínimo de operações necessárias para transformar uma cadeia na outra. As distâncias de edição localizam aplicativos no processamento de linguagem natural , em que a correção ortográfica automática pode determinar as correções candidatas para uma palavra incorreta, selecionando palavras de um dicionário com uma distância baixa da palavra em questão. Na bioinformática , ela pode ser usada para quantificar a similaridade de seqüências de DNA , que podem ser vistas como cadeias das letras A, C, G e T.

Diferentes definições de uma distância de edição usam diferentes conjuntos de operações de string. As operações de distância do Levenshtein são a remoção, inserção ou substituição de um caractere na string. Sendo a métrica mais comum, a distância de Levenshtein é geralmente o que significa “distância de edição”. [1]

Dadas duas seqüências a e b em um alfabeto Σ (por exemplo, o conjunto de caracteres ASCII , o conjunto de bytes [0..255], etc.), a distância de edição d ( a , b ) é a série de peso mínimo de edição operações que transformam um em b . Um dos conjuntos mais simples de operações de edição é o definido por Levenshtein em 1966: 

Inserção de um único símbolo. Se a = v , então inserir o símbolo x produz v . Isso também pode ser denotado ε → x , usando ε para denotar a string vazia.
A exclusão de um único símbolo muda v para v ( x → ε).
Substituição de um único símbolo x por um símbolo y ≠ x muda v para v ( x → y ).

Na definição original de Levenshtein, cada uma dessas operações tem custo unitário (exceto que a substituição de um caractere por si só tem custo zero), então a distância de Levenshtein é igual ao número mínimo de operações necessárias para transformar a para b . Uma definição mais geral associa funções de peso não-negativos ins ( x ), del ( x ) e sub ( x ,  y ) com as operações. 

Operações primitivas adicionais foram sugeridas. Um erro comum ao digitar texto é a transposição de dois caracteres adjacentes, formalmente caracterizada por uma operação que muda v em v . Para a tarefa de corrigir a saída OCR , foram usadas operações de mesclagem e divisão que substituem um único caractere em um par delas ou vice-versa. 

Outras variantes da distância de edição são obtidas restringindo o conjunto de operações. A distância mais longa da subseqüência comum (LCS) é a distância de edição com inserção e exclusão como as duas únicas operações de edição, ambas com custo unitário.  Da mesma forma, permitindo somente substituições (novamente a custo unitário), a distância de Hamming é obtida; isso deve ser restrito a seqüências de comprimento igual. A distância de Jaro-Winkler pode ser obtida a partir de uma distância de edição onde somente transposições são permitidas.

Exemplo 

A distância de Levenshtein entre “gatinho” e “sentado” é 3. Um script de edição mínimo que transforma o primeiro no segundo é:

  1. k itten → s itten (substituição de “s” por “k”)
  2. sitt e n → sitt i n (substituição de “i” por “e”)
  3. sittin → sittin g (inserção de “g” no final).

A distância do LCS (inserções e exclusões somente) fornece uma distância e um script de edição mínimos:

  1. excluir k em 0
  2. insira s em 0
  3. delete e em 4
  4. insira i às 4
  5. insira g às 6

para um custo total / distância de 5 operações.

algoritmoedicaodistanciadistanceeditalgoritm

Este algoritmo pode ser generalizado para lidar com transposições, adicionando outro termo na minimização da cláusula recursiva. 

A maneira direta e recursiva de avaliar essa recorrência toma um tempo exponencial . Portanto, é usualmente computado usando um algoritmo de programação dinâmica que é comumente creditado a Wagner e Fischer ,  embora tenha uma história de múltiplas invenções.  Após a conclusão do algoritmo de Wagner-Fischer, uma seqüência mínima de operações de edição pode ser lida como um backtrace das operações utilizadas durante o algoritmo de programação dinâmica, a partir de{ displaystyle d_ {mn}}.

Esse algoritmo tem uma complexidade de tempo de Θ ( n ). Quando a tabela de programação dinâmica completa é construída, sua complexidade espacial também é Θ ( n ) ; Isso pode ser melhorado para Θ (min ( m , n )) , observando que, a qualquer instante, o algoritmo requer apenas duas linhas (ou duas colunas) na memória. No entanto, essa otimização impossibilita a leitura da série mínima de operações de edição. Uma solução de espaço linear para este problema é oferecida pelo algoritmo de Hirschberg . 

 

Referências

Navarro, Gonzalo (1 Março 2001). “Um tour guiado para aproximar correspondência de strings” (PDF) . Pesquisas de Computação ACM . 33 (1): 31-88. CiteSeerX 10.1.1.452.6317 . doi : 10.1145 / 375360.375365 . Retirado 19 de março de 2015 .
Daniel Jurafsky; James H. Martin. Fala e Processamento de Linguagem . Pearson Education International. pp. 107–111.
Esko Ukkonen (1983). Na correspondência aproximada de cadeias . Fundamentos da Teoria da Computação. Springer pp. 487-495.
Schulz, Klaus U .; Mihov, Stoyan (2002). “Correção rápida de string com autômatos de Levenshtein”. Revista Internacional de Análise e Reconhecimento de Documentos . 5 (1): 67-85. CiteSeerX 10.1.1.16.652 . doi : 10.1007 / s10032-002-0082-8 .
Lei Chen; Raymond Ng (2004). Sobre o casamento das normas Lₚ e editar distância (PDF) . Proc. 30 Int’l Conf. em bancos de dados muito grandes (VLDB). 30 .
Kukich, Karen (1992). “Técnicas para Corrigir Automaticamente Palavras em Texto” (PDF) . Pesquisas de Computação ACM . 24 (4): 377-439. doi : 10.1145 / 146370.146380 .
R. Wagner; M. Fischer (1974). “O problema de correção string-para-string”. J. ACM . 21 : 168–178. doi : 10.1145 / 321796.321811 .
Skiena, Steven (2010). The Algorithm Design Manual (2ª ed.). Springer Science + Business Media . ISBN 978-1-849-96720-4 .
Ukkonen, Esko (1985). “Algoritmos para correspondência aproximada de cadeias de caracteres” (PDF) . Informação e Controle . 64 (1–3): 100–118. doi : 10.1016 / S0019-9958 (85) 80046-2 .
Esko Ukkonen (1985). “Encontrando padrões aproximados em strings”. J. Algoritmos . 6 : 132-137. doi : 10.1016 / 0196-6774 (85) 90023-9 .
[1] Bringmann, Karl e Grandoni, Fabrizio e Saha, Barna e Williams, Virginia Vassilevska (2016). Algoritmos verdadeiramente sub-cúbicos para a distância de edição da linguagem e dobragem de RNA através do produto Min-Plus de diferença limitada limitada. FOCS
Aho, A .; Peterson, T. (1972-12-01). “Um Analisador de Correção de Erros de Distância Mínima para Idiomas sem Contexto”. Jornal SIAM em Computação . 1 (4): 305-312. doi : 10.1137 / 0201022 . ISSN 0097-5397 .
Robert A. Wagner. 1974. Correção de ordem n para idiomas regulares. Comum. ACM 17, 5 (maio de 1974), 265-268. DOI = https://dx.doi.org/10.1145/360980.360995
Saha, B. (2014-10-01). O problema da distância de edição do idioma Dyck no tempo quase linear . 2014 IEEE 55º Simpósio Anual de Fundamentos da Ciência da Computação . pp. 611–620. doi : 10.1109 / FOCS.2014.71 . ISBN 978-1-4799-6517-5 .