Distancia Mínima de Edición

A veces es importante identificar cuanto se parece una palabra a otra, es decir: cuan cerca está una palabra de otra .
Supongamos un corrector ortográfico, si el usuario tipea : "aselrgia"
¿Cuál es la palabra más cercana: alergia, alegría, alergias?

Distancia Mínima de Edición (Edit Distance)

La distancia mínima de edición entre dos strings es la menor cantidad de operaciones de edición:

• Inserción
• Borrado
• Sustitución

necesarias para convertir un string en otro.

Ejemplo: "intención" y "ejecución"

I  N  T  E  *  N  C  I  Ó  N

|  |  |  |  |  |  |  |  |  |

*  E  J  E  C  U  C  I  Ó  N

b  s  s     i  s => (b: borrado, s: sustitución e i: inserción)

Distancia: 5 (si cada operación cuesta 1)

¿Por qué aparecen unos * en medio de la palabra?

Para encontrar el menor número de operaciones de edición es importante que los strings estén alineados de la forma más conveniente. Esto se ve muy claro en el siguiente ejemplo: "mente" y "sutilmente"

*  *  *  *  *  M  E  N  T  E

|  |  |  |  |  |  |  |  |  |

S  U  T  I  L  M  E  N  T  E

i  i  i  i  i

Distancia: 5 (si cada operación cuesta 1)

Si alineamos las palabras para que coincidan las partes iguales nos ahorramos 5 operaciones.

Algoritmo de Levenshtein para encontrar la Distancia Mínima de Edición

Este algoritmo considera que las operaciones de borrado e inserción tienen un costo de 1 mientras que la de sustitución tiene un costo de 2 ya que la considera como compuesta por una operación de borrado más una de inserción. (esta diferencia es Levenshtein )

• Inserción   => 1
• Borrado    => 1
• Sustitución => 2

Inicialización

D(i,0) = i

D(0,j) = j

Relación recurrente para el computo de la distancia

para cada i de 1 a M

    para cada j de 1 a N

                                   {  D(i-1, j) +1

                D(i,j) = min {  D(i, j-1) +1

                                   { D(i-1,j-1) +  { 0 si X(i) = Y(j) ó 2 si X(i) != Y(j) }

Finalización

            La distancia es D(N,M)

Explicación

       La distancia la calculamos recursivamente, donde la distancia entre la palabra A y la palabra B es la suma de la operación final (inserción,borrado o sustitución) más la distancia entre la palabra A-1 letra y la palabra B, o bien entre A y B -1 letra o bien entre la palabra A-1 letra y B-1 letra. Y así sucesivamente hasta llegar a una sola letra en donde las distancias son las obvias que seteamos en la inicialización.

Este algoritmo se puede realizar también de forma iterativa, utilizando una tabla y muchas veces es útil hacerlo así porque nos interesa seguir la pista de las operaciones realizadas. 

    

Dejo un pseudo código más legible para la versión iterativa:

Inicialización

matrix = new matrix [word1.length + 1][word2.length + 1] //definimos una matriz de enteros

 for(i=0;  i<=word1.length; i++)     matrix [i][0]=i; //inicializamos las distancias de la fila 0, 

 for(j=0; j<=word2.length; j++ )    matrix [0][j]=j; // inicializamos las distancias de la columna 0

Computo

 for(i=1; i<=word1.length; i++)

           for(j=1;j<=word2.length; j++)

           

            if (word1[i-1] == word2[j-1]) factor = 0; //son iguales no hay costo de operación

else  factor = 2;  //sustitucion

            matrix[i][j] = MIN(matrix[i-1][j]+1, matrix[i][j-1]+1, matrix[i-1][j-1]+factor);

Finalización

            return matrix[word1.length][word2.length];

Ejemplo:

Finalizado quedaría así: