<p>Sin duda, una de las principales tareas a las que nos enfrentamos los programadores, es <b>la gestión de palabras</b>. Un nombre de usuario, un modelo de coche, una carpeta, etc… constantemente solicitamos al usuario que introduzca palabras pero, <b>¿están bien escritas?</b>.</p></p>
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?.
<h2>Definiendo el problema</h2></p>
<p>Cuando escribimos un documento podemos activar el corrector ortográfico, en tal caso, es habitual que mientras escribimos, se resalten aquellas palabras que <b>no aparecen en el diccionario</b>. Además, se nos muestra una palabra (o varias) que <b>probablemente</b> sea la que queríamos escribir.</p>
<p>En nuestras aplicaciones, no solemos incluir un <i>“corrector ortográfico”</i>, 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 <b>coincide exactamente</b> con los de la libreta de contactos. Por ejemplo, si escribís <i>“juan”</i>, se sugerirá <i>“juanmonfor@genbetadev.com”</i>, pero si os habéis equivocado y ponéis <i>“jjuan”</i> ¿porqué no sugiere nada?.</p>
<p>Si nuestra aplicación solicita al usuario un nombre de usuario, de una máquina, una carpeta, etc… ¿porqué exigirle que <b>no cometa errores</b> al escribir?, podemos hacer que nuestro <i>“autocompletado”</i> sea tolerante a fallos.</p>
<h2>Levenshtein, midiendo las palabras</h2>
<p><b>Levenshtein</b> es una distancia ideada por Vladimir Levenshtein en 1965 que nos permite medir la distancia entre dos secuencias, por ejemplo de caracteres.</p>
<p>En concreto, dadas dos secuencias <b>A</b> y <b>B</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.</p>
<p>Por ejemplo, la distancia Levenshtein entre <i>“juan”</i> y <i>“jjuan”</i> es de una única operación (eliminar/insertar una <i>“j”</i>).</p>
<p>La función Levenshtein es realmente sencilla y no requiere explicación, ésta podría ser una implementación en <i>“javascript”</i>:</p>
<h2>Levenshtein de subcadena</h2>
<p>La distancia Levenshtein la podemos aplicar directamente en multitud de escenarios, <b>pero únicamente en aquellos con una palabra</b>, es decir, Levenshtein no funcionará bien en escenarios en los que debamos contrastar la entrada del usuario <i>“vistamar”</i> con un valor en la lista de <i>“hotel vistamar”</i>, es evidente que el usuario sí se refiere al <i>“hotel vistamar”</i> ¡pero Levenshtein ha dado una distancia de 6!. Para poder aplicar Levenshtein en estos escenarios, voy a sugerir una función adicional:</p>
<p>Efectivamente, como habrás pensado, la función LevenshteinSubminimal <b>ya no es una distancia</b> (aunque nos devuelva una), la forma más sencilla de verlo es que ya no se cumple la propiedad de simetría.</p>
<p>Como única aclaración sobre la función LevenshteinSubminimal decir, que tomamos todas las subcadenas <b>b</b> de <b>B</b> tales que <b>len(A) – 1 <= len(b) <= len(A) + 1</b>, esto es así para relajar los caracteres iniciales y finales de cada subcadena.</p>
<h2>Caso práctico</h2>
<p>Como ejemplo real para poder valorar la función LevenshteinSubminimal, vamos a implementar un sencillo <i>“autocompletado”</i> que, dada una lista de palabras, las ordena y resalta en función de la entrada del usuario.</p>
<p>El código es muy sencillo y carece de interés para el caso (puedes descargarlo <a href="https://gist.github.com/2875143">aquí</a> y ejecutarlo localmente), pero un ejemplo con tres palabras <b>incorrectas</b> introducidas sería la mostrada en la siguiente imagen:</p>
<p>El algoritmo funciona bastante bien, fijaros cómo ha sabido dar prioridad a <i>“arnold schwarzenegger”</i> aunque el texto introducido es <i>“swachenegg”</i>.</p>
<h2>Conclusiones y notas adicionales</h2>
<p>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.</p>
<p>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.</p>
<p>Por cierto, ¿en qué casos de uso se te ocurre que podrían ser útiles las funciones que hemos mencionado?.</p>
Más información | Distancia de Levenshtein (Wikipedia), Distancia de Levenshtein en Wolfram