Distancia Mínima de Edición: Backtrace

Algunas veces no alcanza con solo encontrar la distancia mínima de edición sino que queremos alinear los strings de forma optima. Para eso necesitamos saber exactamente que operaciones aplicamos para ir del string A al B.

Esto se soluciona fácilmente dejando un rastro (backtrace en ingles) de las operaciones que nos llevaron a la celda actual de la tabla (ver post anterior.)



Backtrace

Retomando el algoritmo antes descripto:

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   (esta transición implica borrado)

                D(i,j) = min   {  D(i, j-1) +1   (esta transición implica inserción)

                                   {  D(i-1,j-1) +  {  0 si X(i) = Y(j)  

                                                       {  2 si X(i) != Y(j) (esta transición implica sustitución)

veamoslo rápidamente:

para pasar de "ALA" a "AL" debo borrar un carácter

Cuando la distancia escogida (la mínima) la obtuve al sumar uno a la distancia que estaba en la celda de abajo, entonces lo que hice fue borrar el carácter.

A	3	1	1
L	2	1	0
A	1	0	1
		1	2
		A	L

En cambio si la distancia mínima la obtuve al sumar uno a la distancia de la izquierda lo que hice fue insertar un carácter.

Por último el caso más fácil de ver es el de la sustitución, que se da cuando la distancia mínima se obtuvo al sumar 2 a la distancia en la celda en diagonal (si sumé 0 era la misma letra) 

Entonces en la celda i,j agrego uno de tres valores: ABAJO, DIAGONAL o IZQUIERDA dependiendo de cual fue la distancia anterior usada para calcular la nueva distancia (la de la celda i,j.)

Se puede dar el caso de que la distancia mínima i,j es igual ya sea que borre, inserte o sustituya un carcater en este caso marco todas las opciones.

Siguiendo con el ejemplo anterior:  INTENCIÓN => EJECUCIÓN

Recorriendo la tabla en sentido inverso, yendo siempre al número menor y siguiendo las flechas, obtenemos la lista exacta de operaciones que realizamos para ir de un string a otro: b,s,*,i,s,*,*,*,* (los * indican que no hubo operación.)

Como habíamos visto anteriormente para reducir la distancia alineamos los strings de forma tal que coincida la última parte: "ción" y la primer "e" de "intención". Por ello borramos la primer letra: "i" pero insertamos una "c" después de la "e":

I  N  T  E  *  N  C  I  Ó  N

|  |  |  |  |  |  |  |  |  |

*  E  J  E  C  U  C  I  Ó  N