LIBNADFA

A finalidade deste proxecto é desenvolver unha libraría en C que permita xestionar, de forma eficiente e minimizando o consumo de memoria, dicionarios de grandes dimensións de moi diversa índole empregando, para este fin, autómatas finitos acíclicos deterministas numerados. Entendendo por dicionario, neste contexto, calquera estrutura que permita asociar ás entradas del (palabras) calquera tipo de información. Para o desenvolvemento desta libraría seguíronse dúas máximas:

Minimizar o consumo de memoria necesario para almacenar os dicionarios.
Minimizar o tempo de execución para que poidan ser utilizados en sistemas que necesiten un rendemento elevado.

A libraría está formada por dúas partes: unha empregada para construír o compilador encargado de compilar ou comprimir os dicionarios de palabras, e a outra responsable de facilitar o acceso a estos dicionarios xa compilados.

O que o compilador necesita para xerar un dicionario comprimido é unha listaxe de palabras xunto coa información asociada a elas. A partir desta información, xenera un dicionario compilado (comprimido) en formato binario, ao que se pode acceder desde calquera programa independente utilizando a segunda parte da libraría.

As características fundamentais que diferencian esta librería doutras propostas xa existentes son:

Pode almacenar calquera tipo de información asociada ás palabras. Os dicionarios realmente almacenan enteiros e/ou flotantes pero, dado que estes enteiros poden interpretarse como índices a calquera estrutura externa á libraría, poden referenciarse datos de calquera tipo, incluso cadeas de caracteres.
Posibilita a xestión de diversos dicionarios simultaneamente e con referencias entre eles. Debido, precisamente, a que os datos de tipo enteiro poden interpretarse de diferentes formas, un caso particular é consideralos como índices a outros dicionarios, o que permite relacionar varios dicionarios entre si.

Para o almacenamento das palabras a libraría emprega un autómata finito acíclico determinista numerado, que é construído polo compilador utilizando o algoritmo de construción de autómatas proposto por Jan Daciuk no seu artigo: Incremental Construction of Minimal Acyclic Finite-State Automata. Deste xeito, o autómata constrúese de maneira incremental e mínima, optimizando así o uso de memoria e a velocidade no recoñecemento de palabras que caracteriza aos autómatas.

Para o almacenamento da información, pola contra, empregamos as ideas presentadas por Jorge Graña no seu artigo: Compilation Methods of Minimal Acyclic Finite-State Automata for Large Dictionaries e xeneralizamos algúns aspectos para poder utilizar a libraría en contextos diferentes ao tratado nese traballo: almacenamento de calquera tipo de información asociada ás palabras, eliminación de límites no número de campos de información, posibilidade de empregar máis dun taboleiro de conversión (mapping), posibilidade de acceder á información en disco e/ou en memoria, etc.