Distancia Mínima de Edición Ponderada

Hay ocasiones en donde el algoritmo anterior (ver otros posts de Distancia Mínima de Edición) no se adecua del todo a nuestras necesidades. Pensemos por un momento en un corrector ortográfico, un usuario que tipea: "cattera", las palabras más cercanas son: "cartera" y "cantera" cada una con una distancia de 2.
   Sin embargo es mucho más probable que sea "cartera" que "cantera", porque la "T" y la "R" están juntas en un teclado Querty y dan lugar a errores comunes de tipeo, mientras que la "T" y la "N" están lejos y muy rara vez producen este tipo de error.

    No todos los errores comunes se dan por la disposición de las teclas, muchos se dan por fonética. Si tuviésemos una tabla de errores comunes podríamos generar Distancias Mínimas de Edición Ponderadas.

Distancias Mínimas de Edición Ponderadas

Es tan simple como modificar el algoritmo anterior en este sentido (ver cambios en color azul):

Inicialización

D(i,0) = i

D(0,j) = j

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) + del[X(i)]

                D(i,j) =   min {  D(i, j-1) + ins[Y(j)]

                                   { D(i-1,j-1) +  { 0 si X(i) = Y(j) ó sub[X(i),Y(j)] si X(i) != Y(j) }

Finalización

            La distancia es D(N,M)

Necesitamos, claro está, tablas de donde obtener los valores de errores comunes de borrado, inserción y sustitución. A continuación dejo una tabla de errores comunes de sustitución para el idioma ingles: