Tuesday, October 25, 2011

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


Cuando me fui a hacer la maestría al Reino Unido, ya tenía un proyecto en mente, el cual era hacer un corrector ortográfico inteligente. La idea era usar reglas ortográficas, entre otras cuestiones, para discenir si las palabras de un texto estaban bien escritas. Supuse que tenía que prepararme en algún lenguaje ad hoc para esta tarea y es así como decidí entrarle a la maestría, cuyo pomposo nombre era el de "Inteligencia artificial y bases de datos inteligentes".

Pues bien, después de los correspondientes cursos, poco a poco fui adquiriendo experiencia en Prolog y realmente me fascinó el asunto de programar en este paradigma, particularmente cuando se trata de hablar de paradojas lógicas, de lo que ya escribí antes aquí.

Cuando regresé a México, decidí entonces desarrollar el proyecto que me había llevado a hacer la maestría, el cual le llamé "Lapsus, un corrector ortográfico inteligente". Lo escribí completo en Turbo Prolog 2.0, incluyendo un editor de textos. Sin embargo, me di cuenta que un programa de esta naturaleza debería corer como una aplicación dentro de los programas populares de procesdamiento de palabras, por ejemplo MS Word, y por ende, había que entender cómo hacer para que mi programa y Word actuaran concurrentemente. Así pues, la versión actual de Lapsus corre concurrentemente con MS Word a través de la interfaz OLE (Object Linking and Embedded), pero ya hablaremos de este tema.

Ahora bien, en las decisiones de diseño de Lapsus, tomé las siguientes decisiones:

  1. Ser capaz de usar reglas ortográficas.
  2. Ser capaz de usar un diccionario con unos 500,000 términos (cortesía de una de las aplicaciones en Linux).
  3. Ser capaz de usar diccionarios personalizados.
  4. Ser capaz de usar otras tecnologías para buscar errores, como patrones equivocados de letras.
  5. Ser capaz de usar de un diccionario de verbos ya conjugados.

Estoy de hecho convencido que un corrector ortográfico poderoso debe incluir una serie diferente de técnicas para hallar las palabras mal escritas. Un sistema híbrido sin duda es mejor que un sistema que sólo sigue una técnica en particular.

Pasemos a describir y justificar este diseño:

1. Reglas ortográficas

El español, como todo lenguaje humano es cambiante. Palabras, expresiones y reglas que se usaban en el pasado son obsoletas ahora y en vista de esta situación, se decidió mantener las reglas ortográficas en un archivo especial, el cual es consultado cada vez que el sistema se ejecuta.

Este archivo se denomina Reglas.DB, y contiene alrededor de 260 reglas ortográficas de uso común en el castellano. Las reglas pueden ser editadas con cualquier procesador de palabras (o editor de textos) que utilice el formato ASCII sin caracteres de control o símbolos especiales. Por ejemplo, el block de notas..

Cada una de las reglas ocupa un renglón en el archivo Reglas.Db. Así entonces, escribir una regla nueva significa finalmente, agregar una línea más al archivo ya mencionado. Las reglas ortográficas, para que puedan ser entendidas por el programa, requieren de estar en un formato específico para poder ser leídas por el sistema. Así entonces, puede ser que en un principio, el archivo Reglas.DB le parezca al usuario final difícil de entender. No obstante la aparente complejidad del mismo, sus elementos esenciales son muy fáciles de comprender y usar.

Por ejemplo, he aquí una parte del conjunto de reglas ortográficas (sacadas del pequeño Larousse de la gramática española):

  • v enb p
  • v mob sb mobiliario
  • v prib sb
  • v ebo s sebo cebo efebo mancebo
Hay unas 260 reglas en total. Como éstas residen en un archivo en particular, pueden añadirse más reglas en caso de que se me haya pasado alguna.

A continuación se describe el formato completo de las reglas, indicando la sintaxis que las reglas necesitan y que -en rigor- deben ser escritas correctamente para que Lapsus pueda trabajar con las mismas:

Las reglas ortográficas tienen tres posibles alternativas, las cuales pueden aplicar a:

  • prefijo (p) de la palabra analizada (parte inicial de la palabra en cuestión)
  • sufijo (s) de la palabra analizada (parte final de la palabra en cuestión)
  • subcadena (sb) de la palabra analizada (en cualquier subparte de la palabra en cuestión)
Las letras "p", "s", y "sb" corresponden respectivamente a prefijo, sufijo y subcadena, y estas letras serán usadas para informarle a Lapsus en qué parte de la palabra se aplica la regla ortográfica.

La regla entonces sigue el siguiente formato:

letra palabra clave lista

Pasemos al análisis de esta estructura. En primer término aparece la palabra seguido de paréntesis que abre. Esto debe aparecer en minúscula estrictamente. Acto seguido, pueden verse cuatro parámetros, a saber:

  •  letra    Indica la letra a la cual se aplica la regla. Por ejemplo, si la regla ortográfica es sobre el uso de la v, éste es el parámetro que se utiliza. (Véanse los ejemplos más adelante).
  •  palabra    Indica la palabra que no cumple precisamente con la regla que está siendo definida, es decir, muestra el ejemplo de la contraposición a la regla ortográfica misma.  
  • clave    es exactamente lo que indica el alcance de aplicación de la regla (prefijo, sufijo o subcadena). Utilícese solamente las siguientes palabras claves (entre doble comillas: p, s, sb).
  • lista        Se refiere a la lista de palabras que son la excepción a la regla en cuestión. Tales palabras deben aparecer separadas por espacios entre sí.
Algunos ejemplos pueden ser realmente ilustrativos. Considérese la siguiente regla:

Las palabras que empiezan con env se escriben siempre con v.

La regla en el archivo Reglas.DB se escribirá entonces así:

v enb p

Lapsus reconoce la regla de la siguiente manera: Las excepciones a las palabras que empiezan con env nada más pueden ser aquellas que comienzan con enb, que en este caso no hay tales excepciones a la regla y el rango de aplicación de la misma es con todos los prefijos de las palabras.

La regla descrita se refiere a palabras en donde el rango de aplicación corresponde al prefijo de las misma. Ahora considérese la siguiente regla:

Todas las palabras que terminan con ave se escriben con v.

Esta regla puede expresarse en el lenguaje descrito de la siguiente forma:

v abe s árabe jarabe

La cual puede ser descrita de la siguiente manera: Las excepciones a las palabras que terminan en ave nada más pueden ser aquellas que terminan con abe, las cuales son, árabe y jarabe (y nada más), y el rango de aplicación de la regla son los sufijos de las palabras.

Por último, un ejemplo de una regla que se refiera a subcadenas puede ser la siguiente:

Las palabras que tienen dentro de ellas (en cualquier parte de la misma) las letras ilv se escriben siempre con v.

La cual se traduce en el archivo de reglas de la siguiente forma:

v ilb sb bilbao

Y se interpreta de la siguiente manera: Las excepciones a las palabras que tienen como subpalabra ilv se escriben siempre con v, excepto la palabra bilbao.

Lapsus contiene un editor de reglas para hacer la vida más fácil al usuario (ver siguiente imagen).



2. Diccionario principal

Todo programa de corrección ortográfica requiere de un diccionario, que mientras más grande sea, mejor. Actualmente el diccionario de Lapsus contiene unos 500,000 términos. Originalmente tenía un diccionario de unos 250,000 términos, pero el Gemelo, Jesús Ortega, campeón de Scrabble, me dio el diccionario que hoy uso.

Obviamente para poder buscar en un diccionario con tantos términos, se necesita alguna técnica que sea eficiente. Cuando se trata de datos ordenados alfabéticamente, no hay mejor técnica que la búsqueda binaria. Por ejemplo, para ver si una palabra se encuentra en el diccionario necesitamos solamente 19 búsquedas. ¡Eso es eficiencia! Por supuesto que hay otras técnicas, como las funciones de hash, las cuales podrían hallar el término en una sola búsqueda, pero aquí hay que lidiar con hallar una función de hash adecuada (cosa nada fácil) y además, pelearse con las inevitables colisiones (cuando dos palabras ocupan el mismo sitio). Por ello, la decisión fue usar una búsqueda binaria, la cual es extremadamente rápida, más si se toma en cuenta la velocidad actual de las computadoras.


3. Diccionarios especializados

Los diccionarios tradicionales traen las palabras que normalmente se usan en un lenguaje. Sin embargo, puede pasar que no contemple palabras de algún nicho particular. Por ejemplo, pensemos en el lenguaje específico que usan los doctores. Probablemente algunos términos no aparezcan en el diccionario principal, por lo que aquí se pueden alimentar esos términos muy específicos.

Otro caso: cuando una empresa usa, por ejemplo, un nombre mal escrito. Hay en México una compañía que hace bolsas de polietileno, cuya razón social es "Volzas S.A.". Obviamente si dicha empresa escribe cartas a sus clientes y escribe la palabra "volzas", el corrector brincará anunciándonos que esa palabra está mal escrita (y tendrá razón normalmente, pero no en el contexto mencionado). Así, se pueden poner estos términos, incluso mal escritos, para evitar que Lapsus se dedique a señalarlos cuando no queremos. Un caso similar es el de la palabra "clabe", que significa en el mundo de los bancos "clave bancaria estandarizada", o algo así. Algún ingenioso le puso "clabe", lo cual es mala idea, porque nos acordamos de cómo se escriben las palabras, normalmente, porque las leemos de una manera. Por ello, cuando tenemos dudas sobre cómo se escribe un término, muchas veces la escribimos en un papel a ver cuál es la que vemos como escrita correctamente.

4. Patrones equivocados de letras

Las palabras en español no admiten ciertas combinaciones de letras. Por ejemplo, hasta donde me acuerdo, la combinación TH no existe en español. Así, si leemos un texto y partimos en bigramas ("palabras" de dos letras), podemos ver si una palabra está mal escrita sin siquiera revisar con reglas o diccionarios. Ya una implementación de esta técnica la escribí antes y se puede ver esto aquí.

5. Verbos


El español tiene alrededor de 10,000 verbos. Cada verbo tiene unas 50 conjugaciones. Por ende, esto da unos 500,000 términos que podrían ser añadidos a un diccionario de verbos conjugados. Cabe decir que se puede escribir un programa que haga esto automáticamente, pero solamente será útil para la mayoría de verbos que resulten ser regulares. En cualquier caso, la idea de un diccionario de verbos conjugados (cosa que no se verá normalmente en los diccionarios normales), puede ayudar a que la corrección sea más poderosa.

Seguiremos hablando de esto próximamente.

4 comments:

Mau said...

Me gusta mucho. Lo piensas distribuir solo para MS Word?

Morsa said...

no, Mau, espero poder portarlo a linux, a openoffice.

saludos

Norma said...

Hola. ¿Cómo programaste en Prolog las reglas de algunas palabras, por ejemplo, "Se escribe con /b/ las palabras después de las sílabas iniciales ha-, he-, hi-, hu-: haba, habano, habitar, habitual, hebilla, hibernar? Es decir, qué hiciste en Prolog para instruirlo a que entendiera algo tan complejo? Gracias!

Morsa said...

Norma,

En el artículo menciono cómo le hice, pero te explico. Hay que hacer una regla con todas las palabras que empiezan con "hab", con "heb", con "hib", etc.

La regla, por ejemplo para "hab" es: 'todas las palabras que EMPIEZAN con "hab" se escriben con B. La regla entonces en prolog se pone así:

excepcion('b', 'hav', 'p', []).

que quiere decir que la regla es sobre el uso de la 'b'. Después viene cómo NO se escribe 'hav', después se le indica a prolog que es una regla de prefijo, es decir que tiene que buscar en el inicio de la palabra. Y finalmente la lista [] está vacía porque o encuentro excepciones a la regla.

Obviamente tengo trers predicados, uno para procesar las palabras que EMPIEZAN CON, las que TERMINAN CON y las que CONTIENEN en alguna parte (que no sea el principio o final), la cadena buscada.

Espero eso aclare el asunto.

saludos
Manuel