Operaciones básicas de edición

Las operaciones básicas de edición que se consideran habitualmente son la adición, eliminación, sustitución y transposición. Además en la tecnología de DAEDALUS se ha incluido otra operación extra, consistente en la partición de palabras en varios términos. El significado de cada una de estas operaciones es el siguiente:

• Adición: Transforma la palabra original añadiendo un carácter en cualquier lugar de ella
• Eliminación: Transforma la palabra original eliminando uno de sus caracteres
• Sustitución: Transforma la palabra original sustituyendo uno de sus caracteres por otro diferente
• Transposición: Transforma la palabra original intercambiando dos caracteres adjuntos entre sí
• Partición: Transforma la palabra original separándola por cualquier punto en dos posibles palabras independientes

De estas cinco operaciones básicas tan solo tres serían realmente necesarias (típicamente se consideran adición, eliminación y partición). Por ejemplo, la sustitución de un carácter por otro es equivalente a la eliminación del carácter original y la adición del nuevo; la transposición sería equivalente a la eliminación del primer carácter y su posterior adición una posición más adelante.

Se consideran las cinco operaciones básicas de edición porque corresponden más exactamente con los cinco errores que típicamente se cometen al escribir texto: la omisión de un carácter (compensada con la adición), la inserción de un carácter innecesario (compensada con la eliminación), la inserción de un carácter por otro (compensada con la sustitución), la inserción de caracteres en orden incorrecto (compensada por la transposición) y la omisión de un espacio separador entre palabras contiguas.

Cada una de las operaciones descritas tiene asociada dentro del módulo una penalización, dependiendo de diferentes factores como el entorno del carácter en el que se realiza la operación (letras contiguas al carácter editado), la posición que ocupa el carácter editado dentro de la palabra y el número de operaciones de edición realizadas dentro de la palabra en relación con su longitud.

En este sentido, por ejemplo, en castellano es más probable la sustitución de una 'b' por una 'v' que la de una 'p' por una 's', por lo que la penalización que el sistema maneja internamente en el primer caso es menor que en el segundo. Asimismo, es más raro cometer errores en las primeras letras de la palabra que en las últimas. Del mismo modo, resulta más frecuente cometer algún tipo de error de ortografía cuando la palabra es larga que cuando es muy corta.

Proceso de generación de sugerencias

Una vez entendido el concepto de operación básica de edición y el porqué de la existencia de diferentes penalizaciones según cada caso, es necesario entender el modo en que trabaja el sistema internamente para generar las sugerencias.

Se parte de la palabra original, sobre la que se aplican las diferentes transformaciones básicas en todas las posiciones en que tiene sentido realizarlas (sirven para "acercarse" a palabras existentes). Cada una de estas "sugerencias parciales" (que pueden ser ya términos correctos, o no) se ordena según su penalización.

A continuación, se extrae la sugerencia parcial con menor penalización y se le aplican las operaciones simples de edición que tienen sentido, volviendo a generar una nueva lista de sugerencias parciales, con su penalización asociada (típicamente la penalización de la sugerencia parcial original más la penalización de la operación aplicada), que se mezcla ordenadamente con la lista de sugerencias parciales anterior.

Para cada sugerencia parcial que se inserta en la lista, se comprueba si la palabra existe entre los términos válidos, en cuyo caso, además de aplicarle las operaciones de edición pertinentes, se la incluye en la lista de sugerencias ofrecidas con la penalización correspondiente.

Este proceso se repite hasta que se ha generado un número suficiente de sugerencias (parámetro de configuración del módulo) o hasta que se haya procesado un número máximo de sugerencias parciales. Este segundo límite permite acotar el tiempo máximo de respuesta del sistema, al limitar el número de interacciones que se realizarán. En caso de no existir este límite, una palabra incorrecta de una longitud excesiva podría hacer que el tiempo de respuesta del módulo se resintiese demasiado, afectando a otras consultas y no solo a la actual.

Este proceso debe estar optimizado para prevenir la generación circular de sugerencias (por ejemplo, la inserción y posterior borrado de una letra en la palabra daría lugar a la misma palabra) y generar únicamente sugerencias parciales con probabilidades de dar lugar a una sugerencia real. Para ello en DAEDALUS utilizamos diccionarios incrementales en forma de árbol: la estructura trie.

Asimismo, el proceso de generación de sugerencias está especialmente pensado para la obtención de la palabra alternativa más probable, teniendo en cuenta las penalizaciones definidas en el sistema. De este modo se evita perder tiempo en la generación de alternativas poco probables, mejorando el rendimiento global del sistema.