Как работает pymorphy
#####################

Общая информация
================

pymorphy - библиотека для морфологического анализа на Python,
распространяется по лицензии MIT.

За основу были взяты наработки с сайта aot.ru.
Словари (LGPL) для русского и английского, а также идеи - оттуда.

На aot.ru описаны и конкретные алгоритмы реализации, но в терминах
теории автоматов. Реализация в pymorphy независимая, не использует
конечные автоматы, данные хранятся в key-value хранилище (поддерживаются разные
варианты), все алгоритмы переписаны с учетом этого факта.

В pymorphy также есть некоторые возможности, отсутствующие
в оригинальной реализации, например:

* поддерживается разбор слов с дефисами, разбор слов со сложными префиксами;
* реализовано склонение слов, постановка слов во множественное число;

Cловари aot.ru
==============

Словари с сайта aot.ru содержат следующую информацию:

1. парадигмы слов и конкретные правила образования;
2. ударения;
3. пользовательские сессии;
4. набор префиксов (продуктивных приставок);
5. леммы (незменяемые части слова, основы);
6. грамматическая информация - в отдельном файле.

.. note::

    См. также :ref:`описание формата mrd-файла <mrd-file>`

Из этого всего нам интересны правила образования слов, префиксы, леммы и
грамматическая информация.

Все слова образуются по одному принципу::

    префикс + приставка + основа + окончание

.. glossary::

    Префиксы
        Префиксы - это всякие "мега", "супер" и т.д. Набор префиксов
        хранится просто списком.

    Приставки
        Имеются в виду приставки, присущие грамматической форме,
        но не присущие неизменяемой части слова ("по", "наи"). Например,
        "наи" в слове "наикрасивейший", т.к. без превосходной степени
        будет "красивый".

    Правила образования слов
        Это то, что надо приписать спереди и сзади основы, чтобы получить
        какую-то форму. В словаре хранятся пары "приставка - окончание",
        + "номер" записи о грамматической информации (которая хранится
        отдельно).

    Парадигмы
        Правила образования слов объединены в *парадигмы*. Например, для
        какого-нибудь класса существительных может быть описано, как слово
        выглядит во всех падежах и родах. Зная, что существительное
        принадлежит к этому классу, мы сможем правильно получить любую его
        форму. Такой класс - это и есть парадигма.

    Леммы
        Леммы - это неизменяемые части слов. В словаре хранится
        информация о том, какой лемме соответствуют какие парадигмы
        (какой набор правил для образования грамматических форм слова).
        Одной лемме может соответствовать несколько парадигм.

    Грамматическая информация
        Грамматическая информация - просто пары ("номер" записи, грам. информация).
        "Номер" в кавычках, т.к. это 2 буквы, просто от балды, но все разные.

.. note::

    Неправильно считать, что :term:`лемма <Леммы>` - это корень слова,
    или :term:`приставки <Приставки>` означают то же самое, что и на уроке
    русского языка. Привычные со школы категории (корень, суффикс, приставка,
    окончание) в pymorphy не используются или имеют другой смысл, т.к. эти
    категории слишком слабо формализованы и поэтому не очень подходят
    для машинного морфологического анализа.

Файл со словарем - обычный текстовый, для каждого раздела сначала указано
число строк в нем, а потом идут строки, формат их описан тут.

Поняв структуру словаря, можно написать первую версию морфологического анализатора.

Морфологический анализ
======================

По сути, нам дано слово, и его надо найти среди всех разумных комбинаций вида::

    префикс + приставка + лемма + окончание

и::

    приставка + лемма + окончание

Дело упрощает то, что оказалось (как показала пара строчек на питоне),
что "приставок" у нас в языке (да и в английском вроде тоже) всего 2.
А префиксов в словаре - порядка 20 для русского языка. Поэтому искать
можно среди комбинаций::

     префикc + лемма + окончание

объединив в уме список приставок и префиксов, а затем выполнив
небольшую проверочку.

Если слово начинается с одного из возможных префиксов,
то мы его (префикс) отбрасываем и пытаемся морфологически
анализировать остаток (рекурсивно), а потом просто припишем
отброшенный префикс к полученным формам.

В итоге получается, что задача сводится к поиску среди комбинаций::

    лемма + окончание

Ищем подходящие леммы, потом смотрим, есть ли для них подходящие окончания. [#]_

Для поиска задействован стандартный питоновский ассоциативный массив
(dict, или любой объект, поддерживающий ``__getitem__``,
``__setitem__`` и ``__contains__``), в который поместил все леммы.
Получился словарь вида::

    lemmas: {base -> [paradigm_id]}

т.е. ключ - это лемма, а значение - список номеров допустимых парадигм.
А дальше поехали - сначала считаем, что лемма - это первая буква слова,
потом, что это 2 первых буквы и т.д. По лемме пытаемся получить список
парадигм. Если получили, то в каждой допустимой парадигме пробегаем по
всем правилам и смотрим, получится ли наше слово, если правило применить.
Получается - добавляем его в список найденных форм.

.. rubric:: Примечания

.. [#] Еще был вариант - составить сразу словарь всех возможных слов
       вида ``лемма + окончание``, получалось в итоге где-то миллионов 5
       слов, не так и много, но вариант, вообщем, мне не очень понравился.


Дополнительные детали работы морфологического анализатора
---------------------------------------------------------

Слова без неизменяемой части
^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Если вспомнить пример, который был в начале, про "ЛЮДЕЙ" - "ЧЕЛОВЕК", то
станет понятно, что есть слова, у которых неизменяемая часть отсутствует.
Выяснилось, что есть в словаре такая хитрая магическая лемма "#", которая и
соответствует всем пустым леммам. Для всех слов нужно искать еще и там.

Склонение слов
^^^^^^^^^^^^^^

Для "склонения" слова (постановке его в определенную грамматическую форму)
анализатор сначала составляет список всех форм, в которых может находиться
данное слово, потом убирает из них те, которые не соответствуют переданной
форме, а потом выбирает из оставшихся вариант, по форме наиболее близкий к
исходному.

Постановка слов во множественное число после этого тривиальным образом
реализуется через "склонение".

.. _prediction-algo:

Предсказатель
-------------

Реализован "предсказатель", который может работать со словами,
которых нет в словаре. Это не только неизвестные науке редкие слова,
но и просто описки, например.

Для предсказателя реализованы 2 подхода, которые работают совместно.

Первый подход: угадывание префикса
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Если слова отличаются только тем, что к одному из них приписано
что-то спереди, то, скорее всего, склоняться они будут однаково.

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

Второй подход: предсказание по концу слова
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

Если 2 слова оканчиваются одинаково, то и склоняться они, скорее всего,
будут одинаково.

Второй подход чуть сложнее в реализации (так-то сильно сложнее, если нужна
хорошая реализация)) и "поумнее" в плане предсказаний.

Первая сложность связана с тем, что конец слова может состоять не только из
окончания, но и из части леммы. Для простоты тут задействован опять
ассоциативный массив (или duck typing-заменитель) с предварительно
подготовленными всеми возмоными окончаниями слов (до 5 букв).
Их получилось несколько сот тысяч. Ключ массива - конец слова, значение -
список возможных правил. Дальше - все как при поиске подходящей леммы,
только у слова берем не начало, а 1, 2, 3, 4, 5-буквенные концы, а вместо лемм
у нас теперь новый монстромассив.

Вторая сложность - получается много заведомого мусора. Мусор этот отсекается,
если учесть, что полученные слова могут быть только существительными,
прилагательными, наречиями или глаголами.

Даже после этого у нас остается слишком много не-мусорных правил.
Для определенности, для каждой части речи оставляем только самое
распространенное правило.

.. note::

    Если слово не было предсказано как существительное,
    хорошо бы добавить вариант с неизменяемым существительным
    в ед.ч. и.п., но этот участок кода сейчас закомментирован,
    т.к. на практике он не давал почти никакого улучшения качества
    разбора при большом числе ложных срабатываний.

Сложные слова
-------------

В версии 0.5 появилась поддержка разбора сложных слов, записанных через дефис
(например, "ПО-БРАТСКИ" или "ЧЕЛОВЕК-ПАУК").

Поддерживаются слова, образованные 2 способами:

* левая часть - неизменяемая приставка/основа (например, "ИНТЕРНЕТ-МАГАЗИН",
  "ВОЗДУШНО-КАПЕЛЬНЫЙ". В этом случае форма слова определяется второй частью.
  Этот случай добавляется в возможные варианты разбора всегда.
* 2 равноправные части, склоняемые вместе (например, "ЧЕЛОВЕК-ПАУК"). Этот
  случай добавляется в возможные варианты разбора только тогда, когда обе части
  имеют одинаковую форму (есть варианты разбора первой части, которые
  совпадают с вариантами разбора второй).

