LIBNADFA

La finalidad de este proyecto es desarrollar una librería en C que permita gestionar, de forma eficiente y minimizando el consumo de memoria, diccionarios de grandes dimensiones de muy diversa índole utilizando, para ello, autómatas finitos acíclicos deterministas numerados. Entendiendo por diccionario, en este contexto, cualquier estructura que permita asociar a las entradas del mismo (palabras) cualquier tipo de información. Para el desarrollo de esta librería se han seguido dos máximas:

Minimizar el consumo de memoria necesario para almacenar los diccionarios.
Minimizar el tiempo de ejecución para que puedan ser utilizados en sistemas que necesiten un rendimiento elevado.

La librería está formada por dos partes: una utilizada para construir el compilador encargado de compilar o comprimir los diccionarios de palabras, y la otra responsable de facilitar el acceso a estos diccionarios ya compilados.

Lo que el compilador necesita para generar un diccionario comprimido es una lista de palabras junto con la información asociada a ellas. A partir de esta información, genera un diccionario compilado (comprimido) en formato binario, al que se puede acceder desde cualquier programa independiente utilizando la segunda parte de la librería.

Las características fundamentales que diferencian esta librería de otras propuestas ya existentes son:

Puede almacenar cualquier tipo de información asociada a las palabras. Los diccionarios realmente almacenan enteros y/o flotantes pero, dado que estos enteros pueden interpretarse como índices a cualquier estructura externa a la librería, pueden referenciarse datos de cualquier tipo, incluso cadenas de caracteres.
Posibilita la gestión de diversos diccionarios simultáneamente y con referencias entre ellos. Debido, precisamente, a que los datos de tipo entero pueden interpretarse de diferentes formas, un caso particular es considerarlos como índices a otros diccionarios, lo que permite relacionar varios diccionarios entre si.

Para el almacenamiento de las palabras la librería utiliza un autómata finito acíclico determinista numerado, que es construído por el compilador utilizando el algoritmo de construcción de autómatas propuesto por Jan Daciuk en su artículo: Incremental Construction of Minimal Acyclic Finite-State Automata. De este modo, el autómata se construye de manera incremental y mínima, optimizando así el uso de memoria y la velocidad en el reconocimiento de palabras que caracteriza a los autómatas.

Para el almacenamiento de la información, en cambio, utilizamos los planteamientos presentados por Jorge Graña en su artículo: Compilation Methods of Minimal Acyclic Finite-State Automata for Large Dictionaries y generalizamos algunos aspectos para poder utilizar la librería en contextos diferentes al tratado en ese trabajo: almacenamiento de cualquier tipo de información asociada a las palabras, eliminación de límites en el número de campos de información, posibilidad de utilizar más de un tablero de conversión (mapping), posibilidad de acceder a la información en disco y/o en memoria, etc.