Анализатор морфологии на автоматах

Периодически на хабре проскакивают статьи о том, как написать программу для анализа морфологии. В основном авторы пользуются базами данных, либо стандартными структурами, такими как словари. Но это не всегда удобно. Во-первых, страдает скорость. Во-вторых, некоторые алгоритмы, такие как предсказание морфологии незнакомых слов, реализуются нетривиально.

Здесь я привожу версию, основанную на конечных автоматах, где попробую избежать данных проблем. Как это работает можно посмотреть здесь.
Итак, чего мы хотим от морфологии. Обычно, от модуля анализа морфологии требуют:

• получение леммы по заданному слову
• получение морфологической информации по заданному слову
• предсказание морфологии

Готовить все это будем из двух ингредиентов: морфологического словаря и библиотеки автоматов. Первый возьмем (как уже принято) из проекта aot.ru, спасибо им за LGPL. А библиотеку автоматов — отсюда: openfst.org. Кода будет по минимуму: все нужные операции уже реализованы в библиотеке.

Шаг первый. Парсим морфологический словарь.

В морфологическом словаре находятся строки вида:
МГЛ А га Ы гб Е гв У гг ОЙ гд ОЮ гд Е ге Ы гж АМ ги Ы гй АМИ гк АХ гл
Здесь приведен пример для слова 'мгла'. Буквы МГЛ — это корень слова. Остальное — окончания (флексии). Лемму, или нормализованное слово мы можем получить, сложив корень и первую флексию, в данном случае — МГЛА. Малые двухбуквенные сочетания — это анкод. Т.е. это код, однозначно определяющий морфологию словоформы. К примеру для 'га' это — 'существительное, женский род, единственное число, именительный падеж'.

Перейдем к действиям. Для каждой строки словаря строим вот такую структуру.


Это конечный преобразователь. Работает следующим образом. Каждый переход маркируется двумя буквами, где первая — входной символ, вторая — символ на выходе. Если мы «соберем» входящие и исходящие символы вдоль любого из путей из начального состояния в конечное, то получим два слова. Магия в том, что здесь входным словом будет одна из морфологических форм слова, а выходом — лемма + анкод. К примеру, «скормив» в этот автомат слово «МГЛОЮ», мы получим навыходе «МГЛАмг». Стоит отметить, что "-" обозначает пустой символ, и при проходе по графу мы можем его игнорировать.

Вообще, получить выходное слово по входному можно применив стандартную операцию композиции:
если D — словарь, как на картинке выше,
W — слово, где W = <(М, М)(Г, Г)(Л, Л)(О, О)(Ю, Ю),(И, И)>
То M — результат композиции — будет равен (за вычетом пустых символов)
M = W o D = <(М, М)(Г, Г)(Л, Л)(А, А)(а, а)(м, м)

Шаг второй. Оптимизация.

У структуры на рисунке выше есть проблема. Она не оптимальна. Первое — много лишних пустых символов, которые бесполезно «раздувают» преобразователь. Второе — этот преобразователь сам по себе не оптимален. Если построить такую конструкцию для полного словаря, последний будет очень большим.

И так, сначала сдвигаем исходящие символы в сторону начального состояния. Этим мы уменьшим количество пустых символов. В библиотеке openfst реализована такая операция. Зовется fstpush.

Как видно на рисунке появились дуги с метками "-:-". Они удалятся в процессе упаковки.
Далее, упаковываем преобразователь. Здесь есть тонкость. В общем случае конечный преобразователь не может быть упакован как обычный конечный автомат. Дело в том, что для минимизации преобразователя, как и автомата, он должен быть детерминирован (каждому входному слову соответствует единственное выходное). Но данный преобразователь таковым не является.
Чтобы решить эту проблему, можно

• привести преобразователь к конечному автомату
• упаковать автомат (по стандартному алгоритму)
• привести получившийся автомат к преобразователю

Все эти операции стандартны, код писать нет нужды. Результат для слова «мгла» на картинке ниже.


Как видно из рисунка, количество состояний и переходов заметно сократилось. А это и есть наша цель.

Шаг третий. Предсказание морфологии неизвестного слова.

Здесь все просто. Все что нам нужно — для входящего слова W построить композицию с двумя преобразователями и найти кратчайший путь до конечного состояния:
P = shortest(W o T o D)
где, D — словарь
T — специальный преобразователь с весами, который поглощает префикс слова, при этом штрафуя за каждый «съеденный» символ.


Предсказание я пока не реализовал в примере. Возможно, позже.

Выводы

На мой взгляд это довольно интересный способ работать с морфологией. Я могу выделить два существенных плюса:

• скорость и ресурсы
• простота разработки
• универсальность алгоритмов

Относительно скорости в данном примере мне не удалось с наскока добиться хороших результатов. Получилось что-то вроде 2000 слов/сек. Но я использовал стандартную библиотеку и не очень заботился об оптимизации. Возможно, если использовать другие виды трансдьюсеров скорость может возрасти. Словарь весил около 35М (однако, если использовать компактное представление, он сжимается в 3 раза).

На счет простоты: здесь ненужно много кода. Достаточно пользоваться стандартными операциями: композиция, конкатенация, объединение и поиск кратчайшего пути. Конструкция словаря заняло что-то около 50 строк кода. Тарбол примера с исходниками и питоновскими байндингами можно скачать здесь.

Кроме того, у данного подхода есть очень интересная особенность. Он позволяет выстраивать сложные преобразования за счет объединения трансдьюсеров в более сложные схемы. К примеру, добавив в предиктор автомат из моей прошлой статьи о спелчекере мы получим логический дивайс, который ответит на вопрос: «а является ли это слово действительно неизвестным, или оно содержит ошибку».
Пожалуй, пока все. Надеюсь, было интересно.