La distancia de Levenshtein se define como el mínimo número de operaciones requeridas para transformar una cadena de caracteres en otra.
En el siguiente ejemplo, se muestra el proceso de calcular la distancia Levenshtein resultante de transformar la cadena «casa» hasta obtener «calle», siendo necesarios tres «saltos».
casa -> cala = Sustitución de 's' por 'l' cala -> calla = Inserción de 'l' entre 'l' y 'a' calla -> calle = Sustitución de 'a' por 'e'
En el enlace de la entrada en Wikipedia se muestra, tanto en pseudo-código como implementado en múltiples lenguajes, el algoritmo en cuestión. A continuación muestro la implementación en C# lo más limpia posible, sin comentario alguno.
public static int LevenshteinDistance ( string p_strA, string p_strB )
{
int lengthStrA = p_strA.Length;
int lengthStrB = p_strB.Length;
int[,] d = new int[ lengthStrA + 1, lengthStrB + 1 ];
if ( lengthStrA == 0 ) return lengthStrB;
if ( lengthStrB == 0 ) return lengthStrA;
for ( int i = 0; i <= lengthStrA; d[ i, 0 ] = i++ );
for ( int j = 0; j <= lengthStrB; d[ 0, j ] = j++ );
for ( int i = 1; i <= lengthStrA; i++ )
for ( int j = 1; j <= lengthStrB; j++ )
{
int cost = ( p_strA[ i - 1 ] == p_strB[ j - 1 ] ) ? 0 : 1;
d[ i, j ] = Mathf.Min (
Mathf.Min (
d[ i - 1, j ] + 1,
d[ i, j - 1 ] + 1 ),
d[ i - 1, j - 1 ] + cost );
}
return d[ lengthStrA, lengthStrB ];
}
El siguiente código se trata de la misma implementación pero sacará por consola, en Unity, la información paso a paso del proceso realizado, hasta dar con el número de operaciones requeridas para llegar desde la cadena origen hasta la destino.
using System.Text;
...
public static int LevenshteinDistance ( string p_strA, string p_strB )
{
int lengthStrA = p_strA.Length;
int lengthStrB = p_strB.Length;
int[,] d = new int[ lengthStrA + 1, lengthStrB + 1 ];
// Si alguna cadena esta vacia, fin del proceso, porque el numero
// de modificaciones necesarias es igual a la longitud de la otra
if ( lengthStrA == 0 ) return lengthStrB;
if ( lengthStrB == 0 ) return lengthStrA;
for ( int i = 0; i <= lengthStrA; d[ i, 0 ] = i++ );
for ( int j = 0; j <= lengthStrB; d[ 0, j ] = j++ );
/* d.length = int[ 4+1,5+1 ]
* 0 1 2 3 4 5
* 1 0 0 0 0 0
* 2 0 0 0 0 0
* 3 0 0 0 0 0
* 4 0 0 0 0 0 <- El resultado quedara aqui
*/
StringBuilder str = new StringBuilder ();
string op;
str.Append ( p_strA + " -> " + p_strB + "\n" );
for ( int i = 1; i <= lengthStrA; i++ )
{
str.Append ( "i: " + i + "\n" );
for ( int j = 1; j <= lengthStrB; j++ )
{
int cost = ( p_strA[ i - 1 ] == p_strB[ j - 1 ] ) ? 0 : 1;
d[ i, j ] = Mathf.Min (
Mathf.Min (
d[ i - 1, j ] + 1, // Eliminacion
d[ i, j - 1 ] + 1 ), // Insercion
d[ i - 1, j - 1 ] + cost ); // Sustitucion
if ( d[ i, j ] == d[ i - 1, j ] + 1 ) op = "X";
else if ( d[ i, j ] == d[ i, j - 1 ] + 1 ) op = "I";
else op = "S";
str.Append (
" j: " + j +
" cost[ " + p_strA[ i - 1 ] + "==" + p_strB[ j - 1 ] + " ]: " + cost +
" | d[" + i + "," + j + "] = " +
"Min ( " +
d[ i - 1, j ] + "+1, " +
d[ i, j - 1 ] + "+1, " +
d[ i - 1, j - 1 ] + "+" + cost + " )" +
" = " + d[i,j] + " " + op + "\n" );
}
for ( int a = 0; a <= lengthStrA; a++ )
{
for ( int b = 0; b <= lengthStrB; b++ )
str.Append ( d[a,b] );
str.Append ( "\n" );
}
}
Debug.Log ( str.ToString () );
str = null;
return d[ lengthStrA, lengthStrB ];
}
Y el siguiente fragmento muestra la salida por consola del mismo ejemplo mostrado al comienzo, permitiendo ver el progreso del algoritmo hasta dar con la distancia.
casa -> calle i: 1 j: 1 cost[ c==c ]: 0 | d[1,1] = Min ( 1+1, 1+1, 0+0 ) = 0 S j: 2 cost[ c==a ]: 1 | d[1,2] = Min ( 2+1, 0+1, 1+1 ) = 1 I j: 3 cost[ c==l ]: 1 | d[1,3] = Min ( 3+1, 1+1, 2+1 ) = 2 I j: 4 cost[ c==l ]: 1 | d[1,4] = Min ( 4+1, 2+1, 3+1 ) = 3 I j: 5 cost[ c==e ]: 1 | d[1,5] = Min ( 5+1, 3+1, 4+1 ) = 4 I 012345 101234 200000 300000 400000 i: 2 j: 1 cost[ a==c ]: 1 | d[2,1] = Min ( 0+1, 2+1, 1+1 ) = 1 X j: 2 cost[ a==a ]: 0 | d[2,2] = Min ( 1+1, 1+1, 0+0 ) = 0 S j: 3 cost[ a==l ]: 1 | d[2,3] = Min ( 2+1, 0+1, 1+1 ) = 1 I j: 4 cost[ a==l ]: 1 | d[2,4] = Min ( 3+1, 1+1, 2+1 ) = 2 I j: 5 cost[ a==e ]: 1 | d[2,5] = Min ( 4+1, 2+1, 3+1 ) = 3 I 012345 101234 210123 300000 400000 i: 3 j: 1 cost[ s==c ]: 1 | d[3,1] = Min ( 1+1, 3+1, 2+1 ) = 2 X j: 2 cost[ s==a ]: 1 | d[3,2] = Min ( 0+1, 2+1, 1+1 ) = 1 X j: 3 cost[ s==l ]: 1 | d[3,3] = Min ( 1+1, 1+1, 0+1 ) = 1 S j: 4 cost[ s==l ]: 1 | d[3,4] = Min ( 2+1, 1+1, 1+1 ) = 2 I j: 5 cost[ s==e ]: 1 | d[3,5] = Min ( 3+1, 2+1, 2+1 ) = 3 I 012345 101234 210123 321123 400000 i: 4 j: 1 cost[ a==c ]: 1 | d[4,1] = Min ( 2+1, 4+1, 3+1 ) = 3 X j: 2 cost[ a==a ]: 0 | d[4,2] = Min ( 1+1, 3+1, 2+0 ) = 2 X j: 3 cost[ a==l ]: 1 | d[4,3] = Min ( 1+1, 2+1, 1+1 ) = 2 X j: 4 cost[ a==l ]: 1 | d[4,4] = Min ( 2+1, 2+1, 1+1 ) = 2 S j: 5 cost[ a==e ]: 1 | d[4,5] = Min ( 3+1, 2+1, 2+1 ) = 3 I 012345 101234 210123 321123 432223 <- El resultado es "3"
Es curioso fijarse como la elección del operando seleccionado al calcular el menor de los valores, para asignarselo a la distancia de la fila y columna actuales ( d[i,j] ), es totalmente predecible.
Al coincidir el indice de la fila y la columna se escogerá el tercer operando ( sustitución ). Cuando el indice de la columna sea menor que el de la fila, se escogerá el primero ( eliminación ). Y cuando el indice de la columna sea superior al de la fila, se seleccionará el segundo ( inserción ).
En el fragmento anterior aparece este último aspecto indicado a la derecha del todo , con las letras S, X e I respectivamente para Sustitución, Eliminación e Inserción.