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