Словари

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

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

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

1
ёж      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

Сначала указывается номер лексемы, затем перечисляются формы слова и соответствующая им грамматическая информация (тег). Первой формой в списке идет нормальная форма слова. В словаре около 400тыс. лексем и 5млн отдельных слов.

Примечание

С сайта OpenCorpora для скачивания доступны plaintext- и XML-версии словаря. В pymorphy2 используется XML-версия, но (для простоты) тут и далее в примерах показан plaintext-формат. Сами данные в XML-версии те же.

Если просто загрузить все слова и их грамматическую информацию в питоний list, то это займет примерно 2Гб оперативной памяти. Кроме того, эта форма неудобна для быстрого выполнения операций по анализу и склонению слов.

Упаковка грамматической информации

Каждым тегом (например, NOUN,anim,masc sing,nomn) обычно помечено более одного слова (часто - очень много слов). Хранить строку целиком для всех 5млн слов накладно по 2 причинам:

  • в питоне не гарантировано, что id(string1) == id(string2), если string1 == string2 (хотя функция intern может помочь);
  • строки нельзя хранить в array.array, а у list накладные расходы выше, т.к. он в питоне реализован как массив указателей на объекты, поэтому в случае с тегами важно, чтоб каждому слову была сопоставлена цифра, а не строка.

В pymorphy2 все возможные теги хранятся в массиве (в list); для каждого слова указывается только номер тега.

Пример:

1
ёж      1
ежа     2
ежу     3
ежа     4
ежом    5
еже     6
ежи     7
ежей    8
ежам    9
ежей    10
ежами   11
ежах    12

набор тегов:

['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',
 # ...
 ]

Парадигмы

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

Примечание

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

Пример исходной лексемы:

тихий   100
тихого  102
тихому  105
...
тише    124
потише  148

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

стем: ти
таблица для склонения ("окончание", номер тега, "префикс"):

    "хий"      100  ""
    "хого"     102  ""
    "хому"     105  ""
    ...
    "ше"       124  ""
    "ше"       125  "по"

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

“Окончания” и “префиксы” в парадигмах повторяются, и хорошо бы их не хранить по многу раз (а еще лучше - создавать поменьше питоньих объектов для них), поэтому все возможные “окончания” хранятся в отдельном массиве, а в парадигме указывается только номер “окончания”; с “префиксами” - то же самое.

В итоге получается примерно так:

55      100     0
56      102     0
57      105     0
...
73      124     0
73      125     1

Примечание

Сейчас все возможные окончания парадигм хранятся в list; возможно, было бы более эффективно хранить их в DAWG или Trie и использовать perfect hash для сопоставления индекс <-> слово, но сейчас это не реализовано.

Линеаризация парадигм

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

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

Поэтому каждая парадигма упаковывается в одномерный массив: сначала идут все номера окончаний, потом все номера тегов, потом все номера префиксов:

55 56 57 ... 73 73 | 100 102 105 ... 124 125 | 0 0 0 ... 0 1

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

Хранить числа в питоньем list накладно, т.к. числа типа int - это тоже объекты и требуют памяти:

>>> import sys
>>> sys.getsizeof(1001)
24

Память под числа [-5...256] в CPython выделена заранее, но

  • это деталь реализации CPython;
  • в парадигмах много чисел не из этого интервала;
  • list в питоне реализован через массив указателей, а значит требует дополнительные 4 или 8 байт на элемент (на 32- и 64-битных системах).

Поэтому данные хранятся в array.array из стандартной библиотеки.

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

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

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

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

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

Для хранения данных о словах используется граф (Directed Acyclic Word Graph, wiki) с использованием библиотек DAWG (это обертка над C++ библиотекой dawgdic) или DAWG-Python (это написанная на питоне реализация DAWG, которая не требует компилятора для установки и работает быстрее DAWG под PyPy).

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

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

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

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

двор    (3, 1)
ёж      (4, 1)
дворник (1, 2) и (2, 2)
ёжик    (1, 2) и (2, 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=PARA_1];
9 -> 15 [label=PARA_2];
12 -> 10 [label=IND_2];
13 -> 14 [label=IND_1];
15 -> 10 [label=IND_2];
16 -> 32 [label=И];
16 -> 54 [label=sep];
17 -> 14 [label=IND_1];
22 -> 13 [label=PARA_3];
32 -> 8 [label=К];
54 -> 17 [label=PARA_4];
}

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

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

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

Примечание

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

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

Примечание

Подход похож на тот, что описан на 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]

Примечание

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

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

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

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

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

Примечание

Если вы вдруг пишете морфологический анализатор не на питоне (и формат хранения данных устраивает), то вполне возможно, что будет проще использовать эти подготовленные словари, а не конвертировать словари из 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 тыс. слов/сек - это не очень важно для многих задач, т.к. накладные расходы на обработку и применение результатов разбора все равно, скорее всего, “съедят” эту разницу (особенно при использовании из питоньего кода).