La distancia de Levenshtein

Un problema con el que podemos enfrentarnos de forma relativamente habitual es medir el grado de similitud de dos registros. Cuando los registros con los que trabajamos contienen valores numéricos una de las primeras opciones es la distancia euclídea. Pero cuando trabajamos con cadenas de texto deberemos usar otros algoritmos como puede ser el caso de la distancia de Levenshtein. Una distancia que lleva el nombre de Vladimir Levenshtein, quien definió la distancia en 1965.

La distancia de Levenshtein

En primer podemos definir informalmente la distancia de Levenshtein entre dos cadenas de caracteres como el número mínimo de ediciones (es decir, inserciones, eliminaciones o sustituciones) de un solo carácter que son necesarias para para cambiar una cadena por otra.

Matemáticamente, la distancia de Levenshtein entre dos cadenas de caracteres $a$ y $b$ , cuya longitud son respectivamente $|a|$ y $|b|$ , se puede expresar como $lev_{a,b}(|a|,|b|)$ donde

lev_{a,b}(i,j)=\left\{\begin{matrix} max(i,j) & si \, \min(i,j)= 0, \\ \min \left\{\begin{matrix} lev_{a,b}(i-1,j) + 1 \\ lev_{a,b}(i,j-1) + 1 \\ lev_{a,b}(i-1,j-1) + 1_{a_i \ne b_j} \end{matrix}\right.& si \, min(i,j) \ne 0 \end{matrix}\right.

En esta expresión $1_{a_i \ne b_j}$ denota una función que devuelve 0 cuando las los cadenas de caracteres, $a_i$ y $b_i$ , son iguales y 1 en caso contrario, es decir son diferentes. Por otro lado, nótese que la función $lev_{a,b}(i, j)$ es la distancia entre los primeros i caracteres de la cadena $a$ y los $j$ primeros de la cadena $b$ .

En la función mínimo de la expresión cada una de las líneas miden una de las tres posibles transformaciones. La primera fila representa la eliminación de un carácter en la cadena $a$ , la segunda fila corresponde a la inhesión de un carácter y la tercera fila corresponde a la sustitución.

Ejemplo

Posiblemente como mejor se puede entender la distancia de Levenshtein es mediante un ejemplo. Para lo que se puede usar la definición informal: el número mínimo de ediciones de un solo carácter requeridas para cambiar una cadena de caracteres por la otra. A sí se puede ver fácilmente que la distancia entre las cadenas “cama” y “cana” es 1, ya que solamente se tiene que reemplazar un carácter por otro el “m” por un “n”.

Otro ejemplo fácil de calcular es la distancia entre “cama” y “calle”, la que es de 3. En este caso solamente es necesario realizar tres ediciones para convertir una cadena en otra. Esto es cambiar “m” por “l” (“cala”), insertar una “l” (“calla”) y, finalmente, cambiar la segunda “a” por una “e”.

Nótese que en caso cambiar un carácter por el mismo en mayúscula es una sustitución. Por lo que habitualmente se suele convertir las cadenas a minúsculas (o mayúsculas) antes de aplicar el algoritmo.

Aplicaciones

Las aplicaciones de este algoritmo, al igual que otras métricas para cadenas de texto, son amplias. Por ejemplo, los correctores ortográficos o el reconocimiento óptico de caracteres. Ya que permite identificar la palabra de un diccionario que más se aproxima a la que se ha escrito o identificado, permitiendo así sustituir una por otra.

Generalmente la distancia de Levenshtein se utiliza para medir la distancia entre cadenas cortas, ya que el coste computacional crece rápidamente con la longitud de estas.

Implementación de la distancia de Levenshtein

A continuación, se muestra cómo se puede implementar en R este algoritmo.

levenshtein_distance <- function(str_1, str_2) {
  str_1 <- tolower(str_1)
  str_2 <- tolower(str_2)

  if (str_length(str_1) == 0 || str_length(str_2) == 0) {
    return(max(str_length(str_1), str_length(str_2)))
  }

  previous_row <- 0:str_length(str_2);

  for (i in 1:str_length(str_1)) {
    current_row    <- rep(0, str_length(str_2))
    current_row[1] <- i

    for (j in 1:str_length(str_2)) {
      insertions         <- previous_row[j + 1] + 1
      deletions          <- current_row[j] + 1
      substitutions      <- previous_row[j] + (str_sub(str_1, i, i) != str_sub(str_2, j, j))
      current_row[j + 1] <- min(insertions, deletions, substitutions)
    }

    previous_row <- current_row
  }

  return(current_row[length(current_row)])
}

En el código en primer lugar, se comprueba si alguna cadena es vacía, lo que nos indica que la distancia es igual a la longitud de la cadena más larga. Esto es, el coste de escribir la cadena o borrarla. Posteriormente se itera sobre las dos cadenas comprobando cuales son las transformaciones necesarias para convertir una cadena en otra.

Similitud

Levenshtein cuenta el número de ediciones (inserciones, eliminaciones o sustituciones) necesarias para convertir una cadena en otra. Siendo el resultado un número entero. Lo que representa un problema, ya que el número de errores que se pueden esperar en una cadena es proporcional a la longitud de esta. Un problema que se puede solucionar normalizando la distancia para obtener el grado de similitud

1 - (lev_{a,b}(|a|,|b|) / max(|a|,|b|))

Un valor que se encuentra entre 1, las cadenas son iguales, y 0, las cadenas son completamente diferentes. Independientemente de la longitud de las cadenas comparadas.

La fórmula de la similitud de levenshtein se puede implementar fácilmente una vez tenemos ya implementada la distancia.

levenshtein <- function(str_1, str_2) {
  distance   <- levenshtein_distance(str_1, str_2)
  similarity <- 1 - distance / max(str_length(str_1), str_length(str_2))
  return(similarity)
}

Conclusiones

En esta entrada se ha visto una distancia para medir la distancia entre dos cadenas de caracteres. Algo que es útil ya que cada vez es más habitual trabajar con tipos de datos no solamente numéricos.

Imagen de Markus Spiske en Pixabay