Distancia de Levenshtein

Detalles

Categoría: Programación

Publicado el Martes, 03 Octubre 2006 12:58

La distancia de Levenshtein es un algoritmo tal que dadas dos cadenas, devuelve un entero que da una idea de la distancia (o parecido) entre ellas.

Debe su nombre al matemático ruso Vladimir Levenshtein.

Este entero se calcula contando las transformaciones que es necesario hacer sobre una de estas cadenas para obtener la otra.

Estas posibles tranformaciones 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.

Es tentador pensar que la distancia de Levenshtein puede ayudarnos con las búsquedas fonéticas (Ver Algoritmos fonéticos:algoritmos-foneticos-soundex), pero generalmente no va a ser así. Mientras la distancia de Levenshtein mide diferencias en la grafía de dos cadenas, es decir, en la secuencia de carácteres que la forman, los algorimos fonéticos intentan encontrar similitudes en la pronunciación. Así, la distancia de Levenshtein, por ejemplo, entre "GATO" y "PATO" es tan solo de 1, mientras que los algoritmos fonéticos no deberían clasificar como próximas estas dos cadenas, ya que fonética y etimológicamente no tienen nada que ver.

El algoritmo para hallar la distancia de Levenshtein es el que se muestra a continuación. 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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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]

Este fragmento de código en C# calcula la distancia de Levenshtein entre dos cadenas.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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];
    }

Puedes comprobar el resultado que devuelve el algoritmo con ésta minidemo:

• < Previo
• Siguiente >