Distancia de edición

El cálculo de la distancia entre palabras es un algoritmo basado en programación dinámica. Imagine que necesitamos calcular , donde $x$ y $y$ son palabras. Se llena una matriz , donde representan el mínimo número de operaciones necesarias para comparar a . Este cálculo es como sigue.

		 


if  then 


else 

donde al final . La relación de las fórmulas mencionadas están como sigue. Primero, y , representa la distancia entre una cadena de longitud o $i$ y la cadena vacía. Las cancelaciones de (respectivamente $i$) son claramente necesarias en cadenas no vacías. Para dos cadenas no vacías de longitud y $i$, asumimos inductivamente que todas las distancias entre las cadenas más cortas han sido calculadas, y tratamos convertir a .

Considerando los últimos caracteres y . Si son iguales, entonces no necesitamos considerarlos y procedemos de la mejor manera posible a convertir en . Por otro lado, si no son iguales, debemos tratarlos de alguna manera. Siguiendo las tres operaciones permitidas, podemos borrar y convertir en la mejor manera en , insertamos al final e y convertimos de la mejor manera en o remplazamos por y convertimos de la mejor manera en . En todos los casos, el costo es 1 más el costo del resto de los procesos. Note que la inserción en una cadena son equivalentes a borrar en la otra. Note también que las implicaciones racionales , la cual es la base para una formulación alternativa de la recurrencia:

donde es cero para y 1 en otro caso.

Los algoritmos de programación dinámica deben llenar la matriz de tal manera que el vecino superior, izquierdo, y el superior izquierdo de una celda son calculados antes de calcular una celda. Esto es fácilmente alcanzado por cualquiera de los dos, recorriendo las columnas de izquierda a derecha o recorriendo las columnas transversal de arriba hacia abajo. La tabla muestra este algoritmo para calcular $d$(``survey'',``surgery'').

Tabla: Algoritmo de programación dinámica, para realizar el cálculo de distancia entre dos palabras, ``survey'' y ``surgery''

		s	u	r	g	e	r	y
	0	1	2	3	4	5	6	7
s	1	0	1	2	3	4	5	6
u	2	1	0	1	2	3	4	5
r	3	2	1	0	1	2	3	4
v	4	3	2	1	1	2	4	4
e	5	4	3	2	2	1	2	3
y	6	5	4	3	3	2	2	2

Por lo tanto, el algoritmo es tiempo en el peor de los casos. Al menos el espacio requerido es solo . Esto es porque, en el caso del procesamiento de una columna, solo las columnas previas deben ser almacenadas en orden para calcular la nueva, y por lo tanto solo guardamos una columna y la actualizamos. Podemos procesar la matriz de renglones o columnas, así el espacio requerido es minimizado.

Por otro lado, la secuencia de operaciones realizadas para transformar $x$ en $y$ pueden ser fácilmente recuperada de la matriz, simplemente desarrollando la celda a la celda siguiendo el camino, esto asocia la fórmula actualizada. En otro caso, al menos, necesitamos guardar la matriz completa o por lo menos una área alrededor de la diagonal principal.