Levenshtein, midiendo las palabras

Levenshtein  Info en  Wikypedia

Sin duda, una de las principales tareas a las que nos enfrentamos los programadores, es la gestión de palabras. Un nombre de usuario, un modelo de coche, una carpeta, etc… constantemente solicitamos al usuario que introduzca palabras pero, ¿están bien escritas?.

Verificar un código (DNI, EAN, VISA, …) suele ser muy sencillo, porque es habitual que cuenten con códigos de verificación pero, ¿cómo verificamos si una palabra está bien escrita?, mejor aún ¿cómo podemos sugerir al usuario alternativas correctas?.

Definiendo el problema

Cuando escribimos un documento podemos activar el corrector ortográfico, en tal caso, es habitual que mientras escribimos, se resalten aquellas palabras que no aparecen en el diccionario. Además, se nos muestra una palabra (o varias) que probablemente sea la que queríamos escribir.
En nuestras aplicaciones, no solemos incluir un “corrector ortográfico”, sin embargo, es realmente sencillo y mejora enormemente la experiencia de usuario. Por ejemplo, es probable que en vuestro cliente de correo electrónico, al escribir una dirección de correo, se os sugieran aquellos cuyo prefijo coincide exactamente con los de la libreta de contactos. Por ejemplo, si escribís “juan”, se sugerirá “juanmonfor@genbetadev.com”, pero si os habéis equivocado y ponéis “jjuan” ¿porqué no sugiere nada?.
Si nuestra aplicación solicita al usuario un nombre de usuario, de una máquina, una carpeta, etc… ¿porqué exigirle que no cometa errores al escribir?, podemos hacer que nuestro “autocompletado” sea tolerante a fallos.

Levenshtein, midiendo las palabras

Levenshtein es una distancia ideada por Vladimir Levenshtein en 1965 que nos permite medir la distancia entre dos secuencias, por ejemplo de caracteres.
En concreto, dadas dos secuencias A y B, la distancia Levenshtein nos informa del número mínimo de cambios (inserción, eliminación o sustitución de elementos) que deben hacerse a una cadena para obtener la otra.
Por ejemplo, la distancia Levenshtein entre “juan” y “jjuan” es de una única operación (eliminar/insertar una “j”).
La función Levenshtein es realmente sencilla y no requiere explicación, ésta podría ser una implementación en “javascript”:

// Levenshtein(String, String) -> Integer
function Levenshtein(a, b) {
    var n = a.length;
    var m = b.length;

    // matriz de cambios mínimos
    var d = [];

    // si una de las dos está¡ vacía, la distancia
    // es insertar todas las otras
    if(n == 0)
        return m;
    if(m == 0)
        return n;

    // Inicializamos el peor caso (insertar todas)
    for(var i = 0; i <= n; i++)
        (d[i] = [])[0] = i;
    for(var j = 0; j <= m; j++)
        d[0][j] = j;

    // cada elemento de la matriz será¡ la transición con menor coste
    for(var i = 1, I = 0; i <= n; i++, I++)
      for(var j = 1, J = 0; j <= m; j++, J++)
          if(b[J] == a[I])
              d[i][j] = d[I][J];
          else
              d[i][j] = Math.min(d[I][j], d[i][J], d[I][J]) + 1;

    // el menor número de operaciones
    return d[n][m];
}

Levenshtein de subcadena

La distancia Levenshtein la podemos aplicar directamente en multitud de escenarios, pero únicamente en aquellos con una palabra, es decir, Levenshtein no funcionará bien en escenarios en los que debamos contrastar la entrada del usuario “vistamar” con un valor en la lista de “hotel vistamar”, es evidente que el usuario sí se refiere al “hotel vistamar” ¡pero Levenshtein ha dado una distancia de 6!. Para poder aplicar Levenshtein en estos escenarios, voy a sugerir una función adicional:


/*
LevenshteinSubminimal(String A, String B) -> {k: Integer, t: String}
    A, es la cadena que introduce el usuario
    B, es la cadena candidata a ser alternativa del usuario
    k, es la mínima Levenshtein de A sobre todas las subcadenas de B
    t, es la cadena con menor distancia Levenshtein
*/
function LevenshteinSubminimal(A, B) {
    var a = A.length;
    var b = B.length;
    // siempre comparamos A con las subcadenas de B
    var f = function(s){return Levenshtein(A, s)};
    // si A es mayor que B no comparamos subcadenas
    if(a >= b)
        return {k: f(B), t: B}
    // peor caso y cotas
    var m = {k: b+2, t: null}, c1 = a-1, c2 = a+1;
    for(var p = 0; p < b - c1; p++)
        for(var l = c1, c3 = Math.min(c2, b - p); l <= c3; l++) {
            var t = B.substr(p, l), k = f(t);
            // mejor caso
            if(m.k >= k)
                m = {k: k, t: t};
        }
    return m;
}


Efectivamente, como habrás pensado, la función LevenshteinSubminimal ya no es una distancia (aunque nos devuelva una), la forma más sencilla de verlo es que ya no se cumple la propiedad de simetría.
Como única aclaración sobre la función LevenshteinSubminimal decir, que tomamos todas las subcadenas b de B tales que len(A) – 1 <= len(b) <= len(A) + 1, esto es así para relajar los caracteres iniciales y finales de cada subcadena.

Conclusiones y notas adicionales

Como ves, crear una interface de usuario tolerante a fallos es muy sencillo (no sé porqué mi cliente de correo es tan estricto) y mejorará sustancialmente la experiencia de usuario.
La distancia Levenshtein no es la única posible, existen otras definiciones y variantes de distancia entre secuencias que pueden ser más adecuadas dependiendo del contexto.