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

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

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

    Итак, чего мы хотим от морфологии. Обычно, от модуля анализа морфологии требуют:
    • получение леммы по заданному слову
    • получение морфологической информации по заданному слову
    • предсказание морфологии

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

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


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

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

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

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

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


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

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

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

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

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


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

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

    Выводы


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

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

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

    Кроме того, у данного подхода есть очень интересная особенность. Он позволяет выстраивать сложные преобразования за счет объединения трансдьюсеров в более сложные схемы. К примеру, добавив в предиктор автомат из моей прошлой статьи о спелчекере мы получим логический дивайс, который ответит на вопрос: «а является ли это слово действительно неизвестным, или оно содержит ошибку».
    Пожалуй, пока все. Надеюсь, было интересно.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 0

    Only users with full accounts can post comments. Log in, please.