Есть хорошая книжка по этой теме Walter Daelemans, Antal van den Bosch Memory-Based Language Processing. Так же еще можно прочитать статью на хабре про реализацию морфологии на python. И конечно сайт aot.ru.
В аот насамом деле используются два автомата. Один для слов из словаря. Второй для предсказания. Я писал такой автомат на Java, но увы он занимал слишком много памяти и был сложный в реализации.
В моем случая было критично объем оперативной памяти используемой программой. Кодирование к целым числам наоборот замедляют работу, но экономят используемую память.
Так же у меня используется упорядоченная структура, что бы угадывать правило для незнакомого слова, это тоже замедляет работу алгоритма.
Дерево пока не использовалось, возможно на такое представление будет сделан переход в следующей версии программы и оно должно даст значительный прирост производительности, но не уверен, что будет выгрыш по памяти, учитывая особенности языка java.
В английской литературе есть понятие Memory-Based Algorithm. Они основанные запоминание уже разобранных образцов использование их в дальнейшем. Я понимаю, что по русски это немного режет, но у меня нет лучшего перевода. Если интересно можете посмотреть книгу Walter Daelemans, Antal van den Bosch Memory-Based Language Processing. Там довольно много подобных алгоритмов.
Задача по слову определить его нормальную форму. Например для существительного нормальная форма это именительный падеж, единственное число. Для глагола это инфинитив. Для прилагательного именительный падеж, мужской род и т.д.
На похожем принципе построена реализация морфологи от AOT aot.ru/docs/sokirko/Dialog2004.htm. Так же там есть ссылка на статью (an Daciuk, Bruce Watson, and Richard Watson, Incremental Construction of Minimal Acyclic Finite State Automata and Transducers), где описывается инкрементальное построение автомата, для проверки правильности написания слова. Для всех русской морфологии размер автомата будет около 400 тысяч вершин и около 850 тысяч переходов.
Смотрю я на платформу .net и понимаю, что увы java начинает потихоньку проигрывать. И C# как язык развивается быстрее. Вот и пакетный менеджер появился. Как-то мне от этого грустно.
Так же у меня используется упорядоченная структура, что бы угадывать правило для незнакомого слова, это тоже замедляет работу алгоритма.
Дерево пока не использовалось, возможно на такое представление будет сделан переход в следующей версии программы и оно должно даст значительный прирост производительности, но не уверен, что будет выгрыш по памяти, учитывая особенности языка java.