Словари

В pymorphy2 используются словари из проекта OpenCorpora, специальным образом обработанные для быстрых выборок.

Исходный словарь

Исходный словарь из OpenCorpora представляет собой файл, в котором слова объединены в лексемы следующим образом:

ёж      NOUN,anim,masc sing,nomn
ежа     NOUN,anim,masc sing,gent
ежу     NOUN,anim,masc sing,datv
ежа     NOUN,anim,masc sing,accs
ежом    NOUN,anim,masc sing,ablt
еже     NOUN,anim,masc sing,loct
ежи     NOUN,anim,masc plur,nomn
ежей    NOUN,anim,masc plur,gent
ежам    NOUN,anim,masc plur,datv
ежей    NOUN,anim,masc plur,accs
ежами   NOUN,anim,masc plur,ablt
ежах    NOUN,anim,masc plur,loct

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

Две основные операции, которые умеет делать морфологический анализатор - разбор и склонение слов. Если у нас есть словарь с лексемами, и мы хотим разобрать/просклонять словарное слово, то эти операции очень простые:

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

Если все, что нужно - разбор словарных слов, то можно загрузить все слова и их грамматическую информацию в память “как есть”, либо сохранить в какую-то БД общего назначения. С этим есть 2 проблемы:

  • в словаре OpenCorpora для русского языка около 400тыс. лексем и 5млн отдельных слов; если все загрузить в питоний list, то потратим примерно 2Гб оперативной памяти (в dict - еще больше);
  • хотелось бы, чтоб операции по анализу и склонению слов осуществлялись быстро - в том числе для слов, отсутствующих в словаре, и слов, записанных каким-то “упрощенным” способом (например, с буквой е вместо ё).

Чтобы сэкономить оперативную память и обеспечить быстрый анализ как словарных, так и несловарных слов, pymorphy2:

  • извлекает “парадигмы” из лексем;
  • преобразует информацию в цифры, когда можно;
  • кодирует слова в DAFSA.

Извлечение парадигм

Рассмотрим лексему слова “хомяковый”:

  СЛОВО       ТЕГ
  хомяковый   ADJF,Qual masc,sing,nomn
  хомякового  ADJF,Qual masc,sing,gent
              ...
  хомяковы    ADJS,Qual plur
  хомяковее   COMP,Qual
  хомяковей   COMP,Qual V-ej
похомяковее   COMP,Qual Cmp2
похомяковей   COMP,Qual Cmp2,V-ej

Можно заметить, что каждое слово в лексеме можно разбить на 3 части - “префикс”, “стем” и “хвост”:

ПРЕФИКС СТЕМ      ХВОСТ   ТЕГ
        хомяков   ый      ADJF,Qual masc,sing,nomn
        хомяков   ого     ADJF,Qual masc,sing,gent
                  ...
        хомяков   ы       ADJS,Qual plur
        хомяков   ее      COMP,Qual
        хомяков   ей      COMP,Qual V-ej
    по  хомяков   ее      COMP,Qual Cmp2
    по  хомяков   ей      COMP,Qual Cmp2,V-ej

“Стем” тут - часть слова, общая для всех слов в лексеме. Откинем его:

ПРЕФИКС           ХВОСТ   ТЕГ
                  ый      ADJF,Qual masc,sing,nomn
                  ого     ADJF,Qual masc,sing,gent
                  ...
                  ы       ADJS,Qual plur
                  ее      COMP,Qual
                  ей      COMP,Qual V-ej
    по            ее      COMP,Qual Cmp2
    по            ей      COMP,Qual Cmp2,V-ej

По этой новой таблице можно склонять не только слово “хомяковый”, но и другие слова - например, “красивый” или даже “бутявковый”. Полученная таблица - это и есть парадигма, образец для склонения или спряжения слов.

При компиляции словаря OpenCorpora pymorphy2 для каждой лексемы определяет ее парадигму. Для русского языка получается примерно 3 тысячи уникальных парадигм (из примерно 400 тысяч лексем).

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

Хранение парадигм

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

Пример закодированой таким образом парадигмы:

prefix_id        suffix_id   tag_id
        0        66          78
        0        67          79
                 ...
        0        37          94
        0        82          95
        0        121         96
        1        82          97
        1        121         98

Каждая парадигма упаковывается в одномерный массив (array.array): сначала идут все номера хвостов, потом все номера тегов, потом все номера префиксов:

66 67 ... 37 82 121 82 121 | 78 79 ... 94 95 96 97 98 | 0 0 ... 0 0 0 1 1

Пусть парадигма состоит из N форм слов; в массиве будет тогда N*3 элементов. Данные о i-й форме можно получить с помощью индексной арифметики: например, номер грамматической информации для формы с индексом 2 (индексация с 0) будет лежать в элементе массива с номером N + 2, а номер префикса для этой же формы - в элементе N*2 + 2.

Note

Особенности реализации в Python:

Тройки “номер хвоста, номер грамматической информации, номер префикса” в tuple хранить расточительно, т.к. этих троек получается очень много (сотни тысяч), а каждый tuple требует дополнительной памяти:

>>> import sys
>>> sys.getsizeof(tuple())
56

В отличие от питоньего list, array.array хранится одним куском памяти, накладные расходы меньше. В питоне list - массив указателей на объекты.

Строки кодируются в цифры, чтобы их можно было хранить в array.array, и чтобы не хранить одну и ту же строку много раз (в питоне не гарантировано, что id(string1) == id(string2), если string1 == string2).

Связи между лексемами

В словаре OpenCorpora доступна информация о связях между лексемами. Например, может быть связана лексема для инфинитива и лексема с формами глагола, соответствующими этому инфинитиву. Или, например, формы краткого и полного прилагательного.

Эта информация позволяет склонять слова между частями речи (например, причастие приводить к глаголу).

В pymorphy2 все связанные лексемы просто объединяются в одну большую лексему на этапе подготовки (компиляции) исходного словаря; в скомпилированном словаре информация о связях между лексемами в явном виде недоступна.

Упаковка слов

Для хранения данных о словах используется конечный автомат (Deterministic Acyclic Finite State Automaton, wiki) с использованием библиотек DAWG (это обертка над C++ библиотекой dawgdic) или DAWG-Python (это написанная на питоне реализация DAWG, которая не требует компилятора для установки и работает быстрее DAWG под PyPy).

В структуре данных DAFSA некоторые общие части слов не дублируются (=> требуется меньше памяти); кроме того, в DAWG можно быстро выполнять не только точный поиск слова, но и другие операции - например, поиск по префиксу или поиск с заменами.

В pymorphy2 в DAWG помещаются не сами слова, а строки вида

<слово> <разделитель> <номер парадигмы> <номер формы в парадигме>

Пусть, для примера, у нас есть слова (в скобках - допустимые разборы, определяемые парами “номер парадигмы, номер формы в парадигме”).

двор    (103, 0)
ёж      (104, 0)
дворник (101, 2) и (102, 2)
ёжик    (101, 2) и (102, 2)

Тогда они будут закодированы в такой граф:

digraph foo { rankdir=LR; size=9; node [shape = doublecircle]; 10 14; node [shape = circle]; 0 -> 2 [label=Д]; 0 -> 3 [label=Ё]; 1 -> 4 [label=О]; 2 -> 1 [label=В]; 3 -> 16 [label=Ж]; 4 -> 6 [label=Р]; 5 -> 8 [label=К]; 6 -> 7 [label=Н]; 6 -> 22 [label=sep]; 7 -> 5 [label=И]; 8 -> 9 [label=sep]; 9 -> 12 [label="103"]; 9 -> 15 [label="102"]; 12 -> 10 [label="2"]; 13 -> 14 [label="0"]; 15 -> 10 [label="2"]; 16 -> 32 [label=И]; 16 -> 54 [label=sep]; 17 -> 14 [label="2"]; 22 -> 13 [label="103"]; 32 -> 8 [label=К]; 54 -> 17 [label="104"]; }

Этот подход позволяет экономить память (т.к. как сами слова, так и данные о парадигмах и индексах сжимаются в DAWG), + алгоритмы упрощаются: например, для получения всех возможных вариантов разбора слова достаточно найти все ключи, начинающиеся с

<слово> <разделитель>

– а эта операция (поиск всех ключей по префиксу) в используемой реализации DAWG достаточно эффективная. Хранение слов в DAWG позволяет также быстро и правильно обрабатывать букву “ё”.

Note

На самом деле граф будет немного не такой, т.к. текст кодируется в utf-8, а значения в base64, и поэтому узлов будет больше; для получения одной буквы или цифры может требоваться совершить несколько переходов.

Кодировка utf-8 используется из-за того, что кодек utf-8 в питоне в несколько раз быстрее однобайтового cp1251. Кодировка цифр в base64 - тоже деталь реализации: C++ библиотека, на которой основан DAWG, поддерживает только нуль-терминированные строки. Байт 0 считается завершением строки и не может присутствовать в ключе, а для двухбайтовых целых числел сложно гарантировать, что оба байта ненулевые.

Note

Подход похож на тот, что описан на aot.ru.

Итоговый формат данных

Таблица с грамматической информацией

['tag1', 'tag2', ...]

tag<N> - тег (грамматическая информация, набор граммем): например, NOUN,anim,masc sing,nomn.

Этот массив занимает где-то 0.5M памяти.

Парадигмы

paradigms = [
    array.array("<H", [
        suff_id1, .., suff_idN,
        tag_id1, .., tag_idN,
        pref_id1, .., pref_idN
    ]),

    array.array("<H", [
        ...
    ]),

    ...
]

suffixes = ['suffix1', 'suffix2', ...]
prefixes = ['prefix1', 'prefix2', ...]

suff_id<N>, tag_id<N> и pref_id<N> - это индексы в таблицах с возможными “окончаниями” suffixes, грамматической информацией (тегами) и “префисками” prefixes соответственно.

Парадигмы и соответствующие списки “окончаний” и “префиксов” занимают примерно 3-4M памяти.

Слова

Все слова хранятся в dawg.RecordDAWG:

dawg.RecordDAWG

    'word1': (para_id1, para_index1),
    'word1': (para_id2, para_index2),
    'word2': (para_id1, para_index1),
    ...

В DAWG эта информация занимает примерно 7M памяти.

Алгоритм разбора по словарю

С описанной выше структурой словаря разбирать известные слова достаточно просто. Код на питоне:

result = []

# Ищем в DAWG со словами все ключи, которые начинаются
# с <СЛОВО><sep> (обходом по графу); из этих ключей (из того, что за <sep>)
# получаем список кортежей [(para_id1, index1), (para_id2, index2), ...].
#
# RecordDAWG из библиотек DAWG или DAWG-Python умеет это делать
# одной командой (с возможностью нечеткого поиска для буквы Ё):

para_data = self._dictionary.words.similar_items(word, self._ee)

# fixed_word - это слово с исправленной буквой Ё, для которого был
# проведен разбор.

for fixed_word, parse in para_data:
    for para_id, idx in parse:

        # по информации о номере парадигмы и номере слова в
        # парадигме восстанавливаем нормальную форму слова и
        # грамматическую информацию.

        tag = self._build_tag_info(para_id, idx)
        normal_form = self._build_normal_form(para_id, idx, fixed_word)

        result.append(
            (fixed_word, tag, normal_form)
        )

Настоящий код немного отличается в деталях, но суть та же.

Т.к. парадигмы запакованы в линейный массив, требуются дополнительные шаги для получения данных. Метод _build_tag_info реализован, например, вот так:

def _build_tag_info(self, para_id, idx):

    # получаем массив с данными парадигмы
    paradigm = self._dictionary.paradigms[para_id]

    # индексы грамматической информации начинаются со второй трети
    # массива с парадигмой
    tag_info_offset = len(paradigm) // 3

    # получаем искомый индекс
    tag_id = paradigm[tag_info_offset + tag_id_index]

    # возвращаем соответствующую строку из таблицы с грамматической информацией
    return self._dictionary.gramtab[tag_id]

Note

Для разбора слов, которых нет в словаре, в pymorphy2 есть предсказатель.

Формат хранения словаря

Итоговый словарь представляет собой папку с файлами:

dict/
    meta.json
    gramtab-opencorpora-int.json
    gramtab-opencorpora-ext.json
    grammemes.json
    suffixes.json
    paradigms.array
    words.dawg
    prediction-suffixes-0.dawg
    prediction-suffixes-1.dawg
    prediction-suffixes-2.dawg

Файлы .json - обычные json-данные; .dawg - это двоичный формат C++ библиотеки dawgdic; paradigms.array - это массив чисел в двоичном виде.

Note

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

Характеристики

После применения описанных выше методов в pymorphy2 словарь со всеми сопутствующими данными занимает около 15Мб оперативной памяти; скорость разбора - от нескольких десятков тыс. слов/сек до > 100тыс. слов/сек (в зависимости от интерпретатора, настроек и выполняемой операции). Для сравнения:

  • в mystem словарь + код занимает около 20Мб оперативной памяти, скорость > 100тыс. слов/сек;
  • в lemmatizer из aot.ru словарь занимает 9Мб памяти (судя по данным отсюда), скорость > 200тыс слов/сек.;
  • в варианте морф. анализатора на конечных автоматах с питоновской оберткой к openfst (http://habrahabr.ru/post/109736/) сообщается, что словарь занимал 35/3 = 11Мб после сжатия, скорость порядка 2 тыс слов/сек без оптимизаций;
  • написанный на питоне вариант морф. анализатора на конечных автоматах (автор - Konstantin Selivanov) требовал порядка 300Мб памяти, скорость порядка 2 тыс. слов/сек;
  • в pymorphy 0.5.6 полностью загруженный в память словарь (этот вариант там не документирован) занимает порядка 300Мб, скорость порядка 1-2тыс слов/сек.
  • Про MAnalyzer v0.1 (основанный на алгоритмах из pymorphy1, но написанный на C++ и с использованием dawg) приводят сведения, что скорость разбора 900тыс слов/сек при потреблении памяти 40Мб;
  • в первом варианте формата словарей pymorphy2 (от которого я отказался) получалась скорость 20-60тыс слов/сек при 30M памяти или 2-5 тыс слов/сек при 5Мб памяти (предсказатель там не был реализован).

Цели обогнать C/C++ реализации у pymorphy2 нет; цель - скорость базового разбора должна быть достаточной для того, чтоб “продвинутые” операции работали быстро. 30 тыс. слов/сек или 300 тыс. слов/сек - это не очень важно для многих задач, т.к. накладные расходы на обработку и применение результатов разбора все равно, скорее всего, “съедят” эту разницу (особенно при использовании из питоньего кода).