Distancia de Levenshtein

Se entiende por operación, bien una inserción, eliminación o la sustitución de un carácter.Por ejemplo, la distancia de Levenshtein entre "casa" y "calle" es de 3 porque se necesitan al menos tres ediciones elementales para cambiar uno en el otro.Se apoya en el uso de una matriz (n + 1) × (m + 1), donde n y m son las longitudes de las cadenas.Aquí se indica el algoritmo en pseudocódigo para una función LevenshteinDistance que toma dos cadenas, str1 de longitud lenStr1, y str2 de longitud lenStr2, y calcula la distancia Levenshtein entre ellos: El invariante mantenido a través del algoritmo es que pueda transformar el segmento inicial str1[1..i] en str2[1..j] empleando un mínimo de d[i,j] operaciones.Al final, el elemento ubicado en la parte INFERIOR derecha de la matriz contiene la respuesta.