Lapsus: anatomía de un corrector ortográfico VII

Hay otros métodos de corrección ortográfica, de los cuales me gustaría hablar. Uno de ellos es en base a las posibles sílabas legales que se presentan en el español. La idea es muy simple: se toma una palabra, se analiza y se descompone en sílabas y se busca si hay alguna sílaba que no sea legal, que no corresponda al español. El problema aquí es saber ¿cuáles son las sílabas legales del español? ¿Dónde podré hallar semejante lista?

Hurgando en la red (otros dicen "navegando"), hallé este sitio, el cual asegura haber hallado todas las sílabas legales del idioma castellano. Hasta donde entiendo, quien desarrolló este trabajo, lo que hicieron fue un programa para hacer la división silábica correcta de todas las palabras en español. Como las reglas de división silábica son muy específicas, es posible escribir un programa de esta naturaleza, asunto no muy complicado.

Una vez hecho esto, el o los investigadores hicieron una lista de todas las sílabas que hallaron utilizando para ello 36,070 textos de la enciclopedia Encarta (en español, evidentemente). Sin duda el trabajo empezó realmente después, pues hubo que depurar y además, hallar posibles errores. Hubo pues que hacer una buena labor de programación para automatizar este pesado trabajo de clasificación y no me cabe duda que el autor, Jerónimo Armario Toro, con Diplomado en Magisterio y Licenciado en Psicopedagogía, hizo un fuerte trabajo que sin duda vale la pena.

En el documento que presenta en la red, hallamos lo siguiente: "El objetivo principal de este artículo es el de hacer público el resultado de una investigación que nos ha llevado a realizar un listado, esperamos que totalmente completo, de todas las sílabas del español. En efecto, este listado de sílabas será lo que presentemos en subsiguientes entregas, ordenadas convenientemente en una tabla en la que, debido a consideraciones de espacio, sólo aparecerán estas últimas sílabas, sin las palabras que las ejemplifican".

El autor presenta una tabla de las sílabas válidas del español, pero ¡ay! es una imagen y no un archivo de texto (o mejor aún, una tabla en Excel) que contenga esta información. ¿Por qué no dejó el enlace como un simple archivo .txt? En vista de esto, decidí tomar la tabla mencionada y transcribir todas las sílabas válidas del español. Cabe decir que cuando estaba pasando las sílabas a un archivo de texto, en muchas no hallé ninguna palabra que contuviera esa sílaba. Sin embargo, debido al tamaño de la empresa que realizó en investigador, no hubo lugar para ejemplos de muchísimas de las sílabas. En principio, le creo que su trabajo es correcto, aunque habrá que contrastarlo más adelante con los documentos a corregir. A todo esto, el archivo de texto, con todas las sílabas de la tabla mencionada, se puede descargar de aquí.

Así entonces, el procedimiento de revisión de palabras, en una primera instancia es revisar si cada palabra del texto a corregir tiene sílabas válidas. Si no es así, ya no tenemos que buscar en diccionario alguno porque podemos asegurar que la palabra en cuestión está mal escrita. En caso de que la palabra a revisar esté correctamente en términos de sílabas válidas, tendremos que pasar a buscar en un diccionario o usar alguna otra técnica de corrección.

Cabe señalar que Andrés Aldana, mi ayudante en la UNAM, me mandó una serie de sílabas válidas en el español, que halló en este sitio. Este archivo puede bajarse de aquí. Nótese lo que dice el autor de esa página:

Para evitar duplicidades, hemos clasificado las sílabas por fonética, de manera que hemos sustituido algunas sílabas por otras:

•     "ce" por "ze".
•     "ci" por "zi".
•     "ve" por "be".
•     "h" por "(cádena vacia)".
•     "gue" (de guerra) por "ge".
•     "ge" (de geranio" por "je"
•     "ca" (de casa) por "ka".
•     No se tienen en cuenta los acentos.
•     Sílabas como "rio" (imperio) y "rrio" (me rio de algo gracioso) se consideran diferentes.
•     Etc etc etc...

Debe entenderse que un corrector ortográfico es tan bueno como su capacidad de corrección. Un corrector que se le vayan algunas palabras desmerece en su desempeño y entonces ¿cómo podríamos garantizar que los documentos que revisamos están correctos? El asunto es que un verdadero corrector no puede pasar nada por alto.

Lapsus: anatomía de un corrector ortográfico VI

Un corrector ortográfico tiene otras dificultades a resolver. Una de ellas es si el programa será implementado como una aplicación independiente o si bien, interactuará con algún otro sistema. En la primera versión de Lapsus, la cual se escribió en Turbo Prolog 2.0, de Borland, el sistema contenía su propio editor de textos, es decir, quien usara el software estaba obligado a escribir sus documentos en el editor que yo proveía. Sin embargo, es claro que este enfoque tiene una oposición importante: es difícil que la gente cambie el editor de palabras que use por utilizar la herramienta de corrección ortográfica, aunque ésta suene muy poderosa.

Debido a esto, decidí entonces hacer que Lapsus corriera como una aplicación que se pegaba de alguna manera a MsWord, que es el procesador de palabras que la mayoría usa, pues la suite informática de Microsoft es muy popular. Entonces, habría que ver cómo enlazar ambas aplicaciones, por una parte MsWord y por otra Lapsus, para que ambas de platicaran y se intercambiaran información.

La idea básica era simple: Úsese Word y Lapsus -ya ejecutándose- estará al pendiente de cada palabra que se escriba, la cual será enviada al corrector para evaluar si está bien o mal escrita y si se encuentra algún error, mándese algún mensaje de error (desde Lapsus), que permita al usuario hacer la corrección correspondiente.

La idea es simple pero la implementación de la idea no lo fue. Por una parte, había que ver qué mecanismos permitían entablar un proceso de comunicación entre ambos programas. Hallé que Windows tiene un mecanismo llamado DDE - Data Dynamic Exchange, el cual permite intercambiar datos entre aplicaciones.

De acuerdo a la Wikipedia: Dynamic Data Exchange(DDE) es una tecnología de comunicación entre varias aplicaciones bajo Microsoft Windows y en OS/2. Aunque es apto para las últimas versiones de Windows, ha sido reemplazado por su mucho más poderoso sucesor Object Linking and Embedding, COM y OLE Automation. Sin embargo, todavía se usa en varios sitios dentro de Windows, por ejemplo en la asociación de archivos. En particular, DDE permite que una aplicación abra una sesión con otra, enviar comandos al servidor de aplicaciones y recibir respuestas. Sin embargo, este no permite incorporar una interfaz del servidor dentro de la aplicación cliente, tampoco soporta la incorporación de un servidor de datos dentro del archivo cliente (por ejemplo: almacenamiento estructurado); y para usar DDE se tienen que conocer los comandos de DDE que el servidor soporta, lo cual no ha sido generalmente estandarizado (si bien existieron algunos estándares, como la especificación spyglass para navegadores web), Así, para emplear toda la funcionalidad del DDE, se debe agregar código especial en cada aplicación cliente para cada servidor que este quiera controlar, o la aplicación cliente debe facilitar un lenguaje de script o macro. Un uso común de DDE fue para desarrollar aplicaciones personalizadas para controlar software disponible, ejemplo: un aplicación escrita en C o algún otro lenguaje debía usar DDE para abrir una hoja de cálculo Microsoft Excel y llenarla con datos, por medio de una conversación con Excel y el envío de comandos DDE. Sin embargo, hoy se usa el modelo de objeto de Excel con OLE Automation (automatización OLE) (esto es una parte de COM). Windows tiene la habilidad de llamar NetDDE, el cual posibilita que los mensajes DDE sean enviados entre aplicaciones que corren en máquinas diferentes. Su uso es raramente utilizado, pero todavía tiene soporte. El cuaderno de Microsoft (Microsoft Clipbook) y el juego de cartas Corazones (Microsoft Hearts) son algunas de las aplicaciones que usan NetDDE.

Cabe señalar que DDE además, resulta un monstruo difícil de enfrentar. La documentación: unos 60 megabytes, es oscura e impenetrable. Cuando hice mis primeras pruebas de Lapsus con DDE hallé que una vez no funcionaba bien y otra vez tampoco. Aparte de oscuro resultó francamente inestable. Así que después de unos meses de padecer a DDE me declaré incompetente (o lo declaré más bien incompetente) y decidí buscar otra opción.

Por suerte hallé que OLE automation es la solución a muchas de las dificultades. El protocolo de comunicación entre procesos es mucho más claro y además, para Office ya está implementado en muchísimas plataformas, inclusive Delphi. Curiosamente los ejemplos que hallé sobre cómo pasar una palabra desde Word a Lapsus y regresarla corregida son inexistentes. Hay muchos ejemplos de cómo hacer para que Word, a través de una aplicación en Delphi, abra el menú para leer un archivo, o para guardarlo, pero nada de la manipulación de las palabras.

Buscando en la red hallé que la revista Delphi Informant (septiembre y octubre del 2000), traía probablemente esa información. Y aunque la revista había desaparecido, estaba a la venta el CD con todos los artículos en PDF. Tuve dificultades con los que venden el CD (ya lo mencioné en algún artículo pasado), pero finalmente me hice de esos artículos y entonces Lapsus podía entonces cobrar vida, pues la parte medular había sido resuelta.

Ya hablaremos más adelante de los detalles al respecto.

Lapsus: anatomía de un corrector ortográfico V

La búsqueda binaria

Una de las cosas que hacen inevitablemente los correctores ortográficos es buscar en un diccionario si la palabra que buscan existe. Es claro que hay diferentes técnicas para hacer estas búsquedas, pero sin duda la más eficiente es la llamada "búsqueda binaria".

Por ejemplo, supongamos que tenemos 1000 palabras. Asumamos que la lista está desordenada. ¿Cuántas búsquedas tengo que hacer? A lo más 1000, porque la palabra que buscamos pudiese ser la última de la lista. Ahora bien, supongamos que la misma lista está ordenada alfabéticamente, de la A a la Z. ¿Cuántas búsquedas tengo que hacer? 10, porque lo que hacemos es dividir y conquistar, algo así como el procedimiento común que usamos cuando queremos hallar una palabra en un diccionario físico, real: Lo abrimos a la mitad y vemos si ya nos pasamos (es decir, la palabra que buscamos tiene que estar antes), o bien, nos quedamos cortos. Si nos pasamos, tomamos la primera mitad y volvemos a dividir en dos. Vemos de nuevo si nos pasamos o no. Hacemos este procedimiento hasta ver si  está la palabra que buscamos. (La ilustración al inicio de este artículo muestra este procedimiento al tratar de ver si el número 3 está en una lista ordenada de números).

Tratar de encontrar una palabra usando una búsqueda binaria es lo más eficiente, pues a cada paso se van eliminando la mitad de los elementos por  analizar. Por ejemplo, para el caso de un diccionario con 50 millones de palabras, hay que hacer solamente 26 búsquedas. El orden del algoritmo de la búsqueda binaria es logarítmico, es decir, el numero máximo de elementos que consultas es 2 elevado a la n, donde n es el numero de elementos en total.

En una búsqueda elemento por elemento, el orden es N, porque en el peor de los casos, hay que recorrer todo el arreglo para encontrar el elemento (o para verificar que el elemento no existe). En cambio en la busqueda binaria, si se tienen N elementos, en la primera consulta se selecciona N/(2^1) elementos, en la segunda N/(2^2) elementos (queda entonces un cuarto del arreglo por buscar), en la tercera N/(2^3)... así hasta que N/(2^x) sea cero. En otras palabras 2^x > N. donde x es el numero de búsquedas que se realizaron, y vale aproximadamente log2(N+1), que es de orden logaritmico.

Para ilustrar el asunto, muchas veces le pregunto a mis alumnos ¿cuántas búsquedas tienen que hacer si el diccionario tiene 1000 palabras? Alguno responde bien: unas 10. ¿Y si tienen 2000 palabras? Ya algunos se confunden, pero la respuesta correcta son 11 búsquedas. ¿Y si tengo 4000 palabras? 12 búsquedas serán suficientes. Cada vez que duplico la cifra, tengo que aumentar una búsqueda. No creo que exista en este rubro algoritmo más eficiente, amén que encaja perfectamente para el problema de la corrección ortográfica.

Funciones de Hash

Otra alternativa son las funciones de hash. En este caso hablamos d eun  algoritmo o subrutina que mapea un conjunto grande de datos a uno más pequeño, llamado llaves. En el caso de un diccionario, podríamos tomar cada palabra y aplicarle una función que nos regresara un número entero. Así, podríamos usar ese número como un índice en un arreglo para ver si la palabra que está ahí es la que buscamos.

Veamos cómo funciona esto. Asumamos que nuestra función de hash es la suma de los caracteres de la palabra. Para hacerlo más fácil, asumamos que la A es 1, la B es 2, la C es 3, y así sucesivamente. Tomemos por ejemplo, la palabra ROMA. Aplicando la función de hash obtendremos:

R(18) + O(15) + M(13) + A(1) = 47

Ponemos entonces la palabra ROMA en el casillero 47. Así, si busco esa palabra, le aplico la función de hash y me voy al casillero 47 y listo, solamente hice un acceso al diccionario. 

El problema es cuando tenemos otra palabra como AMOR, anagrama de ROMA. En este caso, la función de hash de AMOR será:

A(1) + M(13)+ O(15) + R(18) = 47

 

de nuevo 47. Aquí tenemos lo que se llama una colisión (dos palabras quieren ocupar el mismo casillero). Cuando esto pasa con demasiada frecuencia, es decir, cuando hay muchas colisiones, es momento de buscar una mejor función de hash, aunque hasta donde entiendo, no hay una función que no tenga colisiones. El asunto es minimizar esto y manipular el problema de las colisiones con una lista ligada, por ejemplo. Modos de tratar las colisiones hay muchos, algunos más eficientes que otros, pero finalmente para resolver esto requerimos de tiempo de procesamiento.

Por ejemplo, para evitar las colisiones con nuestra función de hash original, podríamos agregarle peso a la posición de las letras, así multiplicamos por 1 al valor de la primera letra, 2 al valor de la segunda letra, etc. Y con ello resolveríamos el problema de los anagramas, que siempre dan la misma función de hash. En el caso de ROMA y AMOR tendríamos:

Para ROMA:

R(18)(1)+ O(15)(2) + M(13)(3) + A(1)(4) = 

 

R(18) + O(30) + M(39) + A(4) = 91

para AMOR:

A(1)(1) + M(13)(2)+ O(15)(3) + R(18)(4) = 

 

A(1) + M(26)+ O(45) + R(72) = 144

Así evitamos la colisión de ambos anagramas, pero es probable que nuestra función sea muy elemental igualmente y conlleve colisiones con otras palabras. Por ello mismo me inclino a no usar funciones de hash en este problema y mejor aplicar la búsqueda binaria.