Описание библиотеки libMAFSA

Реализация минимального конечного автомата для хранения словарей. В частности, реализован алгоритм построения, предложенный Jan Daciuk. Из всех известных нам реализаций наша отличается прежде всего качеством написания, она не «течет», и потребляет минимум оперативной памяти для постоения.

MAFSA (Minimal Acyclic Finite State Automaton) — Минимальный Ацикличный Конечный Автомат. Предназначение — хранилище строк из определенного алфавита, но его можно использовать несколько для других целей. Лемматизатор turglem использует автомат для определения номера парадигмы и флексии по заданному слову.

В основе библиотеки лежит тип MAFSA_letter — буква из азбуки автомата. Из букв можно составлять слова, «накормить» ими автомат, а потом проверять наличие того или иного слова в автомате, а также выводить все слова с определенным началом.

Чтобы создать и использовать автомат, нужно сначала определить его азбуку. В примере использования автомата, который идёт вместе с исходниками, приводится пример английской азбуки, которая содержит помимо 26 букв английского алфавита ещё символы «-» и «'», а также специальный символ «разделитель», с помощью которого реализуется возможность получать числа по слову-ключу.