Distância de Edição

A distância de edição entre cadeias é usada, neste contexto, com vistas a alcançar o objetivo de encontrar ocorrências não necessariamente exatas mas suficientemente "próximas" a um padrão P num texto T.

Distância entre cadeias

Uma função de distância num conjunto A é uma função

d: A x A -> ℝ

satisfazendo as seguintes condições:

• d(α,β) >= 0 ∀ α,β ∈ A
• d(α,β) = 0 ⇔ α = β
• d(α,β) = d(β,α) ∀ α,β ∈ A
• d(α,β) + d(β,γ) >= d(α,γ) ∀ α,β,γ ∈ A

Distância de Levenshtein / de edição

Função definida por:

dl: Σ* x Σ * -> ℤ*
(X = x1, ..., xm, Y = y1, ..., yn) |-> dl(x,y) = min { dl(X[:m-1], Y[:n-1]) + φ(X[m], Y[n]), 
                                                       dl(X[:m-1], Y) + 1, 
                                                       dl(X, Y[:n-1]) + 1 }

onde

φ(a, b) = { 0, se a = b
            1, se a != b }

por definição, d(ε,ε) = 0.

A distância de edição corresponde ao número mínimo de operações de edição (substituição, inserção e remoção) necessárias para transformar uma cadeia em outra.

Exemplo

X = CADA; Y = ABADAC;

   * *       *
X: C - A D A -
Y: A B A D A C

dl(X,Y) = 3

Cálculo da distância de edição

A definição de dl indica que podemos computá-la por Programação Dinâmica, criando uma matriz de programação dinâmica da seguinte maneira:

D[i,j] := dl(X[:i], Y[:j])

com 0 <= i <= m e 0 <= j <= n, em que m e n são os tamanhos das cadeias X e Y, respectivamente.

Exemplo

   Y 0 1 2 3 4 5 6
X    ε A B A D A C  
0  ε 0 1 2 3 4 5 6
1  C 1 1 2 3 4 5 5
2  A 2 1 2 2 3 4 5
3  D 3 2 2 3 2 3 4
4  A 4 3 3 2 3 2 3

Obs.:

• A distância de edição se encontra na última coluna da última linha (dl(X,Y) = D[m,n]).
• Tempo = O(m x n)
• Espaço = O(m)