Editar distância - Edit distance

Em linguística computacional e ciência da computação , editar a distância é uma forma de quantificar o quão diferentes duas strings (por exemplo, palavras) são uma da outra, contando o número mínimo de operações necessárias para transformar uma string na outra. Editar distâncias localiza aplicativos no processamento de linguagem natural , onde a correção ortográfica automática pode determinar correções candidatas para uma palavra com erros ortográficos, selecionando palavras de um dicionário que têm uma distância baixa para a palavra em questão. Em bioinformática , pode ser usado para quantificar a similaridade de sequências de DNA , que podem ser vistas como strings 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 de Levenshtein são a remoção, inserção ou substituição de um caractere na string. Sendo a métrica mais comum, o termo distância de Levenshtein é freqüentemente usado como sinônimo de distância de edição .

Tipos de distância de edição

Diferentes tipos de distância de edição permitem diferentes conjuntos de operações de string. Por exemplo:

A distância de Levenshtein permite exclusão, inserção e substituição.
A distância de maior subsequência comum (LCS) permite apenas inserção e exclusão, não substituição.
A distância de Hamming permite apenas substituição, portanto, só se aplica a cordas do mesmo comprimento.
A distância Damerau – Levenshtein permite a inserção, exclusão, substituição e a transposição de dois caracteres adjacentes.
A distância de Jaro permite apenas a transposição .

Algumas distâncias de edição são definidas como uma métrica parametrizável calculada com um conjunto específico de operações de edição permitidas, e a cada operação é atribuído um custo (possivelmente infinito). Isso é ainda mais generalizado por algoritmos de alinhamento de sequência de DNA , como o algoritmo Smith-Waterman , que fazem o custo de uma operação depender de onde ela é aplicada.

Definição formal e propriedades

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

Inserção de um único símbolo. Se

a

=

u

v

, então inserir o símbolo

x

produz

u

x

v

. Isso também pode ser denotado ε →

x

, usando ε para denotar a string vazia.

A exclusão de um único símbolo altera

u

x

v

para

u

v

(

x

→ ε).

A substituição de um único símbolo

x

por um símbolo

y

≠

x

altera

u

x

v

para

u

y

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 personagem 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$ em $b$ . Uma definição mais geral associa as funções de peso não negativo $w$ _ins ( $x$ ), $w$ _del ( $x$ ) $ew$ _sub ( $x$ , $y$ ) com as operações.

Operações primitivas adicionais foram sugeridas. A distância Damerau – Levenshtein conta como uma única edição um erro comum: a transposição de dois caracteres adjacentes, formalmente caracterizada por uma operação que muda $u$ $x$ $y$ $v$ em $u$ $y$ $x$ $v$ . Para a tarefa de corrigir a saída do OCR , as operações de mesclagem e divisão foram usadas, as quais substituem um único caractere em um par deles ou vice-versa.

Outras variantes de distância de edição são obtidas restringindo o conjunto de operações. A distância de subsequência comum mais longa (LCS) é a distância de edição com inserção e exclusão como as duas únicas operações de edição, ambas a custo unitário. Da mesma forma, permitindo apenas substituições (novamente a custo unitário), a distância de Hamming é obtida; isso deve ser restrito a strings de comprimento igual. A distância Jaro – Winkler pode ser obtida a partir de uma distância de edição onde apenas 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 último é:

k itten → s itten (substitua "s" por "k")
sitt e n → sitt i n (substituir "i" por "e")
sentado → sentado g (inserção de "g" no final)

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

k itten → itten (exclua "k" em 0)
itten → s itten (insira "s" em 0)
sitt e n → sittn (apague "e" em 4)
sittn → sitt i n (inserir "i" em 4)
sentado → sentado g (inserção de "g" em 6)

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

Propriedades

Editar distância com custo não negativo satisfaz os axiomas de uma métrica , dando origem a um espaço métrico de cordas, quando as seguintes condições são atendidas:

Cada operação de edição tem um custo positivo;
para cada operação, há uma operação inversa com custo igual.

Com essas propriedades, os axiomas métricos são satisfeitos da seguinte forma:

d

(

a

,

b

) = 0 se e somente se a = b, uma vez que cada string pode ser transformada trivialmente em si mesma usando exatamente zero operações.

d

(

a

,

b

)> 0 quando

a

≠

b

, pois isso exigiria pelo menos uma operação a custo diferente de zero.

d

(

a

,

b

) =

d

(

b

,

a

) por igualdade do custo de cada operação e seu inverso.

Desigualdade triangular:

d

(

a

,

c

) ≤

d

(

a

,

b

) +

d

(

b

,

c

).

A distância de Levenshtein e a distância LCS com custo unitário satisfazem as condições acima e, portanto, os axiomas métricos. Variantes de distância de edição que não são métricas adequadas também foram consideradas na literatura.

Outras propriedades úteis de distâncias de edição de custo unitário incluem:

A distância LCS é limitada acima pela soma dos comprimentos de um par de strings.
A distância LCS é um limite superior da distância de Levenshtein.
Para cordas do mesmo comprimento, a distância de Hamming é um limite superior da distância de Levenshtein.

Independentemente do custo / pesos, as seguintes propriedades são válidas para todas as distâncias de edição:

Quando $um$ e $b$ partilham um prefixo comum, esse prefixo não tem efeito sobre a distância. Formalmente, quando $um$ = $uv$ e $b$ = $UW$ , em seguida, $d$ ( $um$ , $b$ ) = $d$ ( $v$ , $w$ ). Isso permite acelerar muitos cálculos envolvendo distância de edição e scripts de edição, uma vez que prefixos e sufixos comuns podem ser ignorados no tempo linear.

Computação

O primeiro algoritmo para calcular a distância mínima de edição entre um par de strings foi publicado pela Damerau em 1964.

Algoritmo comum

Usando as operações originais de Levenshtein, a distância de edição (não simétrica) de a é dada por , definida pela recorrência ${\ displaystyle a = a_ {1} \ ldots a_ {m}}$ ${\ displaystyle b = b_ {1} \ ldots b_ {n}}$ ${\ displaystyle d_ {mn}}$

{\ displaystyle {\ begin {alinhado} d_ {i0} & = \ sum _ {k = 1} ^ {i} w _ {\ mathrm {del}} (a_ {k}), && \ quad {\ text {para }} \; 1 \ leq i \ leq m \\ d_ {0j} & = \ sum _ {k = 1} ^ {j} w _ {\ mathrm {ins}} (b_ {k}), && \ quad { \ text {for}} \; 1 \ leq j \ leq n \\ d_ {ij} & = {\ begin {cases} d_ {i-1, j-1} & {\ text {for}} \; a_ {i} = b_ {j} \\\ min {\ begin {casos} d_ {i-1, j} + w _ {\ mathrm {del}} (a_ {i}) \\ d_ {i, j-1 } + w _ {\ mathrm {ins}} (b_ {j}) \\ d_ {i-1, j-1} + w _ {\ mathrm {sub}} (a_ {i}, b_ {j}) \ end {casos}} & {\ text {para}} \; a_ {i} \ neq b_ {j} \ end {casos}} && \ quad {\ text {para}} \; 1 \ leq i \ leq m, 1 \ leq j \ leq n. \ End {alinhado}}}

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 leva um tempo exponencial . Portanto, é geralmente calculado usando um algoritmo de programação dinâmica que é comumente creditado a Wagner e Fischer , embora tenha um histórico de múltiplas invenções. Após a conclusão do algoritmo de Wagner-Fischer, uma sequência mínima de operações de edição pode ser lida como um backtrace das operações usadas durante o algoritmo de programação dinâmica começando em . ${\ displaystyle d_ {mn}}$

Este algoritmo tem uma complexidade de tempo de Θ ( $m$ $n$ ) onde $m$ e $n$ são os comprimentos das strings. Quando a tabela de programação dinâmica completa é construída, sua complexidade de espaço também é Θ ( $m$ $n$ ) ; isso pode ser melhorado para Θ (min ( $m$ , $n$ )) observando que, em qualquer instante, o algoritmo requer apenas duas linhas (ou duas colunas) na memória. No entanto, essa otimização torna impossível ler a 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 .

Algoritmos aprimorados

Aprimorando o algoritmo Wagner-Fisher descrito acima, Ukkonen descreve várias variantes, uma das quais leva duas strings e uma distância máxima de edição $s$ , e retorna min ( $s$ , $d$ ) . Ele consegue isso apenas computando e armazenando uma parte da tabela de programação dinâmica em torno de sua diagonal. Este algoritmo leva tempo O ( $s$ × min ( $m$ , $n$ )) , onde $m$ e $n$ são os comprimentos das strings. A complexidade do espaço é O ( $s$ ² ) ou O ( $s$ ) , dependendo se a sequência de edição precisa ser lida.

Melhorias adicionais por Landau , Myers e Schmidt [1] fornecem um algoritmo de tempo O ( $s$ ² + max ( $m$ , $n$ )) .

Formulários

Editar distância encontra aplicações em biologia computacional e processamento de linguagem natural, por exemplo, a correção de erros ortográficos ou erros de OCR e correspondência de string aproximada , onde o objetivo é encontrar correspondências para strings curtas em muitos textos mais longos, em situações onde um pequeno número de diferenças é de se esperar.

Existem vários algoritmos que resolvem problemas além do cálculo da distância entre um par de strings, para resolver tipos de problemas relacionados.

O algoritmo de Hirschberg calcula o alinhamento ótimo de duas strings, onde a otimização é definida como a minimização da distância de edição.
A correspondência aproximada de strings pode ser formulada em termos de distância de edição. O algoritmo de Ukkonen de 1985 pega uma string $p$ , chamada de padrão, e uma constante $k$ ; ele então constrói um autômato de estado finito determinístico que encontra, em uma string arbitrária $s$ , uma substring cuja distância de edição para $p$ é no máximo $k$ (cf. o algoritmo Aho-Corasick , que similarmente constrói um autômato para procurar qualquer um de um número de padrões, mas sem permitir operações de edição). Um algoritmo semelhante para correspondência de string aproximada é o algoritmo bitap , também definido em termos de distância de edição.
Os autômatos de Levenshtein são máquinas de estado finito que reconhecem um conjunto de strings dentro da distância de edição limitada de uma string de referência fixa.

Distância de edição de idioma

Uma generalização da distância de edição entre strings é a distância de edição de linguagem entre uma string e uma linguagem, geralmente uma linguagem formal . Em vez de considerar a distância de edição entre uma string e outra, a distância de edição do idioma é a distância de edição mínima que pode ser alcançada entre uma string fixa e qualquer string tirada de um conjunto de strings. Mais formalmente, para qualquer idioma L e string x sobre um alfabeto $Σ$ , a distância de edição de idioma d ( L , x ) é dada por , onde é a distância de edição de string. Quando a linguagem L é livre de contexto , existe um algoritmo de programação dinâmica em tempo cúbico proposto por Aho e Peterson em 1972 que calcula a distância de edição da linguagem. Para famílias menos expressivas de gramáticas, como as gramáticas regulares , existem algoritmos mais rápidos para calcular a distância de edição. ${\ displaystyle d (L, x) = \ min _ {y \ in L} d (x, y)}$ ${\ displaystyle d (x, y)}$

A distância de edição de linguagem encontrou muitas aplicações diversas, como dobramento de RNA, correção de erros e soluções para o problema de geração de pilha ideal.

Languages

In other projects