Ejemplo de distancia de edicion (PUNTOS EXTRA)

Materia: Lenguajes de Programación

Hola a todos, en esta entrada les voy a explicar paso a paso un ejemplo para que puedan entender bien el tema que expuse de distancia de edición.

Primero que nada les recuerdo que distancia de edición calcula el número de cambios que se tienen que realizar para cambiar de una palabra a otra. Les pondré el pseudocódigo de la presentación y después un ejemplo explicado.

Pseudocodigo


Int  DistanciaEdicion(char pal1[strlen(pal1)], char pal2[strlen(pal2)])
Int  matriz[(strlen(pal1))+1][(strlen(pal2))+1]
Int i,j,c


De i = 0 hasta  strlen(pal1)
matriz[i][0] = i
De j = 0 hasta strlen(pal2)
matriz[0][j] = j


De i = 1 hasta strlen(pal1)
De j = 1 hasta strlen(pal2)
si pal1[i]==pal2[2] Entonces c = 0
else c = 1


matriz[i][j] = minimo{
matriz[i-1][j]+1,            Eliminar
matriz[i][j-1]+1,            Insertar
matriz[i-1][j-1]+c          Sustitución
}
return  matriz[strlen(pal1)][strlen(pal2)]

Mi ejemplo lo puse con las palabras sillon y silla. Calcularemos los pasos necesarios para cambiar de silla a sillón. Así viendo las palabras normalmente nos damos cuenta que solo se tienen que hacer 2 cambios, uno sería sustituir la a por la o y otro sería agregar una letra ya que sillón tiene 1 letra más que silla.

Bueno primero que nada como está en el pseudocódigo se cuentan las letras de cada una de las palabras que se van a comprarar como se los muestro en la siguiente imagen.

El paso siguiente será empezar a llenar la tabla, sabemos que los cambios posibles son: insertar, sustituir y eliminar. Cada cambio tiene un costo, al insertar y eliminar siempre se le sumará +1, en caso de sustituir se evaluará si la letra que estamos comparando de la palabra1 es igual a la letra que estamos comparando de la palabra2, entonces si estas letras son iguales no tendrá ningun costo, o sea no se le sumara nada, en cambio si estas letras son diferentes tendrá un costo de +1.

Esto se tomara en cuenta al llenar una casilla, para llenarla tenemos que evaluar el número que esta arriba, el que esta a la izquierda y el de la esquina superior izquierda. Ya agregando los costos se evaluará cual genera el mínimo costo esto se hace para poder tomar el camino más corto, o sea el camino que menos pasos genere para cambiar una palabra a la otra. Si el mínimo es el de arriba significa que se insertará una letra, si el mínimo es el de la izquierda significa que se eliminará una letra y si se tomó como mínimo el de la esquina superior iquierda significa que se sustituyó una letra por otra.

En la siguiente imagen muestro como llene la primera columna de la tabla. Se muestra también el procedimiento que les comentaba arriba del costo que genera cada cambio, si se fijan cuando comparo la s de sillón con la s de silla y como son iguales no se genero ningún costo en la esquina superior izquierda y en la de arriba y la izquierda se suma +1 por ser insertar y eliminar.

Aquí les muestro ahora como llene la segunda columna de la tabla.

Y para terminar les muestró la tabla terminada.

Lo que está marcado con rojo es el camino más corto que se tomó para cambiar esta palabra y el número 2 que está con morado son los mínimos de cambios que se deben hacer para cambiar de la palabra sillón a silla. Como lo dije al principio de la entrada se generaron dos cambios y se puede ver que el primer cambio se generó al comparar a con o y se agarró el mínimo el 0 que está en la esquina superior izquierda, y el segundo cambio se realizó agregando una letra ya que se tomó como mínimo el 1 de arriba. Así concluimos que son 2 cambios necesarios los mínimos que se tienen que realizar para cambiar de la palabra silla a la palabra sillón.

Espero hayan entendido, cualquier duda que tengan me la hacen saber. Saludos a todos :)