Distancia de Levenshtein

La distancia de Levenshtein, distancia de edición o distancia entre palabras es el número mínimo de operaciones requeridas para transformar una cadena de caracteres en otra, se usa ampliamente en teoría de la información y ciencias de la computación. Se entiende por operación, bien una inserción, eliminación o la sustitución de un carácter. Esta distancia recibe ese nombre en honor al científico ruso Vladimir Levenshtein, quien se ocupó de esta distancia en 1965. Es útil en programas que determinan cuán similares son dos cadenas de caracteres, como es el caso de los correctores de ortografía.

Por ejemplo, la distancia de Levenshtein entre "casa" y "calle" es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro.

  1. casa → cala (sustitución de 's' por 'l')
  2. cala → calla (inserción de 'l' entre 'l' y 'a')
  3. calla → calle (sustitución de 'a' por 'e')

Se le considera una generalización de la distancia de Hamming, que se usa para cadenas de la misma longitud y que solo considera como operación la sustitución. Hay otras generalizaciones de la distancia de Levenshtein, como la distancia de Damerau-Levenshtein, que consideran el intercambio de dos caracteres como una operación.

Como buena "distancia", cumple (aunque es complicado demostrarlo formalmente), que:

Dist(A,B) == Dist(B,A)

Dist(A,B) + Dist(B,C) >= Dist(A,C)


El algoritmo

Se trata de un algoritmo de tipo bottom-up, común en programación dinámica. Se apoya en el uso de una matriz (n + 1) × (m + 1), donde n y m son las longitudes de las cadenas. Aquí se indica el algoritmo en pseudocódigo para una función LevenshteinDistance que toma dos cadenas, str1 de longitud lenStr1, y str2 de longitud lenStr2, y calcula la distancia Levenshtein entre ellos:

int LevenshteinDistance(char str1[1..lenStr1], char str2[1..lenStr2])
   // d is a table with lenStr1+1 rows and lenStr2+1 columns
   declare int d[0..lenStr1, 0..lenStr2]
   // i and j are used to iterate over str1 and str2
   declare int i, j, cost
 
   for i from 0 to lenStr1
       d[i, 0] := i
   for j from 0 to lenStr2
       d[0, j] := j
 
   for i from 1 to lenStr1
       for j from 1 to lenStr2
           if str1[i-1] = str2[j-1] then cost := 0
                                else cost := 1
           d[i, j] := minimum(
                                d[i-1, j] + 1,     // deletion
                                d[i, j-1] + 1,     // insertion
                                d[i-1, j-1] + cost   // substitution
                            )
 
   return d[lenStr1, lenStr2]

El invariante mantenido a través del algorítmo es que pueda transformar el segmento inicial str1[1..i] en str2[1..j] empleando un mínimo de d[i,j] operaciones. Al final, el elemento ubicado en la parte INFERIOR derecha de la matriz contiene la respuesta.

Other Languages