DISTANCIA DE LEVENSHTEIN, DL
Se llama distancia de Levenshtein, DL (X , Y), entre las cadenas X e Y, al mínimo costo de todas las secuencias de edición que transformen X en Y.
Sea S una secuencia S1, S2, . . , Sn de operaciones de edición. Una derivación_S de X hasta Y es una secuencia de cadenas X0, X1, . . . , Xn tal que X = X0, Y = Xn y Xj-1 ? Xj vía Sj ? j = 1, . . . , n.
Sea ? una función arbitraria de costo que asigna un valor real no negativo a cada operación de edición. Se puede extender ? a la secuencia S definiendo:
El costo de cualquier operación de edición se considera unitario