Distancia de Levenshtein

Vladimir Levenshtein

La distancia de Levenshtein es un algoritmo para comparar dos cadenas: dos palabras, frases o lo que sea, y el algoritmo devuelve un número entero que nos da una idea de lo distintas o parecidas que son.

Cuanto más bajo sea ese entero (la distancia), mas parecidas serán las cadenas. Si ese entero es 0, las cadenas se pueden considerar iguales.

Debe su nombre al matemático ruso Vladimir Levenshtein, que lo desarrolló en los años 60 del siglo XX. Este entero que representa a la distancia entre dos cadenas se calcula contando las transformaciones que es necesario hacer sobre una de estas cadenas para obtener la otra.

Estas posibles transformaciones son:

  • Borrado de un carácter
  • Inserción de un carácter
  • Substitución de un carácter por otro

Por ejemplo, la distancia entre HOLA y TROLA es 2, ya que hay que hacer 2 operaciones sobre la palabra HOLA para obtener TROLA: substituir la H por una R e insertar una T.

Cuanto más corta es la distancia entre las dos cadenas, más parecidas son. Si la distancia es 0, las dos palabras son iguales.

El algoritmo de Levenshtein no tiene en cuenta consideraciones fonéticas.

Hay una categoría de algoritmos llamados algoritmos fonéticos, cuya misión es encontrar el parecido fonético entre dos cadenas (Por ejemplo, ver Algoritmos fonéticos:). Por ejemplo, en español, dos apellidos como Hernandez y Fernández están fonéticamente relacionados y un algoritmo fonético nos dice que están próximos.

La distancia de Levenshtein también nos dice que están próximos (la distancia es 1), pero fijándose exclusivamente en la grafía de las palabras, no en la fonética: es decir, en cómo se escriben, no en como se pronuncian. Así, la distancia de Levenshtein, por ejemplo, entre "GATO" y "PATO" es tan solo de 1, mientras que fonética y etimológicamente no tienen nada que ver, y un algorítmo fonético no las calificaría como próximas.

El algoritmo para hallar la distancia de Levenshtein es el que se muestra a continuación en pseudocódigo. Se basa en crear una matriz de enteros que tenga tantas filas como la longitud de una de las cadenas más uno, y tantas columnas como la longitud de la otra más uno.

La primera fila y la primera columna se rellenan con los valores 0,1,2,3... hasta llenarlas por completo, y a partir de ahí se va rellenando el resto de la matriz sumando costes de transformaciones, y quedándonos siempre con el mínimo. Cuando la matriz está completamente llena, la última casilla de la matriz nos dará el coste de la transformación.

Éste es el algoritmo expresado en peseudocódigo, con anotaciones como comentarios

funcion Levenshtein(s1, s2: cadena):entero
   -sea n1 la longitud de s1
   -sea n2 la longitud de s2
   -si n2 vale 0, devolver n1 y terminar
   -si n1 vale 0, devolver n2 y terminar
   -sea m una matriz de enteros m[n1+1][n2+1]
   //inicializar la primera fila con los valores 0,1,...,n2 y
   //la primera columna con los valores 0,1,...,n1
   -para i=0 hasta n1
      -m[i][0]←i
   -fin para
   -para i=0 hasta n2
      -m[0][i]←i
   -fin para
   //comparar cada caracter de s1 con cada caracter de s2
   //tomando nota de su posición en cada cadena
   //y asignar a cada elemento de m el minimo de:
   // * El elemento de la fila superior más uno
   // * El elemento de la izquierda más uno
   // * El elemento anterior de la diagonal más el coste

   -para cada caracter en la posición i1 de s1 (empezando a contar por 1)
      -para cada caracter i2 de s2 (empezando a contar por 1)
         -si s1[i1] es igual a s2[i2] entonces  //aquí se calcula el coste
            -sea coste←0
         -si no
            -sea coste←1
         -fin si
         -m[i1,i2]←minimo( m[i1-1][i2]+1, m[i1][i2-1]+1, m[i1-1][i2-1]+1 )
      -fin para
   -fin para
   -devolver m[n1][n2]

Implementarlo en cualquier lenguaje de programación no es complicado. Por ejemplo, en lenguaje C#, una función que realice los cálculos del algoritmo podría quedar de ésta manera:

static int Levenshtein(string s1, string s2) {
  int coste = 0;
  int n1 = s1.Length;
  int n2 = s2.Length;
  int[,] m=new int[n1+1,n2+1];

  for (int i = 0; i <= n1; i++) {
    m[i,0] = i;
  } 
  for (int i = 1; i <= n2; i++) { 
    m[0,i] = i;
  }
  for (int i1 = 1; i1 <= n1; i1++) { 
    for (int i2 = 1; i2 <= n2; i2++) {
      coste = (s1[i1 - 1] == s2[i2 - 1]) ? 0 : 1;
      m[i1, i2] = Math.Min(
        Math.Min(
          m[i1 - 1, i2] + 1,
          m[i1, i2 - 1] + 1
        ),
        m[i1 - 1, i2 - 1] + coste
      );
    }
  }
  return m[n1, n2];
}

Demo

Comprueba cómo se comporta el algoritmo con la demo a continuación. También puedes ver la implementación del algoritmo en javascript.