Первоначальный формат словарей (отброшенный)¶
Warning
Этот формат словарей в pymorphy2 не используется; описание - документация по менее удачной попытке организовать словари.
Первоначальная реализация доступна в одном из первых коммитов. Рассматривайте описанное ниже как бесполезный на практике “исторический” документ.
В публикации по mystem был описан способ упаковки словарей с использованием 2 trie для “стемов” и “окончаний”. В первом прототипе pymorphy2 был реализован схожий способ; впоследствие я заменил его на другой.
Этот первоначальный формат словарей в моей реализации обеспечивал скорость разбора порядка 20-60тыс слов/сек (без предсказателя) при потреблении памяти 30М (с использованием datrie), или порядка 2-5 тыс слов/сек при потреблении памяти 5M (с использованием marisa-trie).
Идея была в том, что слово просматривается с конца, при этом в первом trie ищутся возможные варианты разбора для данных окончаний; затем для всех найденных вариантов окончаний “начала” слов ищутся во втором trie; в результате возвращаются те варианты, где для “начала” и “конца” есть общие способы разбора.
Основной “затык” в производительности был в том, что для каждого слова требовалось искать общие для начала и конца номера парадигм. Это задача о пересечении 2 множеств, для которой мне не удалось найти красивого решения. Питоний set использовать было нельзя, т.к. это требовало очень много памяти.
Лучшее, что получалось - id парадигм хранились в 2 отсортированных массивах, а их пересечение находилось итерацией по более короткому массиву и “сужающимся” двоичным поиском по более длинному (параллельная итерация по обоим массивам на конкретных данных оказывалась всегда медленнее).
В pymorphy2 я в итоге решил использовать другой формат словарей, т.к.
- другой формат проще;
- алгоритмы работы получаются проще;
- скорость разбора получается больше (порядка 100-200 тыс слов/сек без предсказателя) при меньшем потреблении памяти (порядка 15M).
Но при этом первоначальный формат потенциально позволяет тратить еще меньше памяти; некоторые способы ускорения работы с ним еще не были опробованы.
Уменьшение размера массивов, как мне кажется - наиболее перспективный тут способ ускорения. Для уменьшения размеров сравниваемых массивов требуется уменьшить количество парадигм (например, “вырожденных” с пустым стемом).
Выделение парадигм¶
Изначально в словаре из OpenCorpora нет понятия “парадигмы” слова. Парадигма - это таблица форм какого-либо слова, образец для склонения или спряжения.
В pymorphy2 выделенные явным образом парадигмы слов необходимы для того, чтоб склонять неизвестные слова - т.к. при этом нужны образцы для склонения.
Пример исходной леммы:
375080
ЧЕЛОВЕКОЛЮБИВ 100
ЧЕЛОВЕКОЛЮБИВА 102
ЧЕЛОВЕКОЛЮБИВО 105
ЧЕЛОВЕКОЛЮБИВЫ 110
Парадигма (пусть будет номер 12345):
"" 100
"А" 102
"О" 105
"Ы" 110
Вся лемма при этом “сворачивается” в “стем” и номер парадигмы:
"ЧЕЛОВЕКОЛЮБИ" 12345
Note
Для одного “стема” может быть несколько допустимых парадигм.
Прилагательные на ПО-¶
В словарях у большинства сравнительных прилагательных есть формы на ПО-:
375081
ЧЕЛОВЕКОЛЮБИВЕЕ COMP,Qual V-ej
ПОЧЕЛОВЕКОЛЮБИВЕЕ COMP,Qual Cmp2
ПОЧЕЛОВЕКОЛЮБИВЕЙ COMP,Qual Cmp2,V-ej
Можно заметить, что в этом случае форма слова определяется не только тем, как слово заканчивается, но и тем, как слово начинается. Алгоритм с разбиением на “стем” и “окончание” приведет к тому, что все слово целиком будет считаться окончанием, а => каждое сравнительное прилагательное породит еще одну парадигму. Это увеличивает общее количество парадигм в несколько раз и делает невозможным склонение несловарных сравнительных прилагательных, поэтому в pymorphy2 парадигма определяется как “окончание”, “номер грам. информации” и “префикс”.
Пример парадигмы для “ЧЕЛОВЕКОЛЮБИВ”:
"" 100 ""
"А" 102 ""
"О" 105 ""
"Ы" 110 ""
Пример парадигмы для “ЧЕЛОВЕКОЛЮБИВЕЕ”:
"" 555 ""
"" 556 "ПО"
"" 557 "ПО"
Note
Сейчас обрабатывается единственный префикс - “ПО”. В словарях, похоже, нет других префиксов, присущих только отдельным формам слова в пределах одной леммы.
Упаковка “стемо┶
“Стемы” - строки, основы лемм. Для их хранения используется структура данных trie (с использованием библиотеки datrie), что позволяет снизить потребление оперативной памяти (т.к. некоторые общие части слов не дублируются) и повысить скорость работы (т.к. в trie можно некоторые операции - например, поиск всех префиксов данной строки - можно выполнять значительно быстрее, чем в хэш-таблице).
Ключами в trie являются стемы (перевернутые), значениями - список с номерами допустимых парадигм.
Упаковка tuple/list/set¶
Для каждого стема требуется хранить множество id парадигм; обычно это множества из небольшого числа int-элементов. В питоне накладные расходы на set() довольно велики:
>>> import sys
>>> sys.getsizeof({})
280
Если для каждого стема создать даже по одному пустому экземпляру set, это уже займет порядка 80М памяти. Поэтому set() не используется; сначала я заменил их на tuple с отсортированными элементами. В таких tuple можно искать пересечения за O(N+M) через однопроходный алгоритм, аналогичный сортировке слиянием, или за O(N*log(M)) через двоичный поиск.
Но накладные расходы на создание сотен тысяч tuple с числами тоже велики, поэтому в pymorphy 2 они упаковываются в одномерный массив чисел (array.array).
Пусть у нас есть такая структура:
(
(10, 20, 30), # 0й элемент
(20, 40), # 1й элемент
)
Она упакуется в такой массив:
array.array([3, 10, 20, 30, 2, 20, 40])
Сначала указывается длина данных, затем идет сами данные, потом опять длина и опять данные, и т.д. Для доступа везде вместо старых индексов (0й элемент, 1й элемент) используются новые: 0й элемент, 4й элемент. Чтоб получить исходные цифры, нужно залезть в массив по новому индексу, получить длину N, и взять следующие N элементов.
Итоговый формат данных¶
Таблица с грам. информацией¶
['tag1', 'tag2', ...]
tag<N> - набор грам. тегов, например NOUN,anim,masc sing,nomn.
Этот массив занимает где-то 0.5M памяти.
Парадигмы¶
[
(
(suffix1, tag_index1, prefix1),
(suffix2, tag_index2, prefix2),
...
),
(
...
]
suffix<N> и prefix<N> - это строки с окончанием и префиксом (например, "ЫЙ" и ""); tag_index<N> - индекс в таблице с грам. информацией.
Парадигмы занимают примерно 7-8M памяти.
Note
tuple в парадигмах сейчас не упакованы в линейные структуры; упаковка должна уменьшить потребление памяти примерно на 3M.
Стемы¶
Стемы хранятся в 2 структурах:
array.array с упакованными множествами номеров возможных парадигм для данного стема:
[length0, para_id0, para_id1, ..., length1, para_id0, para_id1, ...]
и trie с ключами-строками и значениями-индексами в массиве значений:
datrie.BaseTrie( 'stem1': index1, 'stem2': index2, ... )
“Окончания”¶
Для каждого “окончания” хранится, в каких парадигмах на каких позициях оно встречается. Эта информация требуется для быстрого поиска нужного слова “с конца”. Для этого используются 3 структуры:
array.array с упакованными множествами номеров возможных парадигм для данного окончания:
[length0, para_id0, para_id1, ..., length1, para_id0, para_id1, ...]
В отличие от аналогичного множества для стемов, номера парадигм могут повторяться в пределах окончания.
array.array с упакованными множествами индексов в пределах парадигмы:
[length0, index0, index1, ..., length1, index0, index1, ...]
Этот массив работает “вместе” с предыдущим, каждому элементу отсюда соответствует элемент оттуда - совместно они предоставляют информацию о возможных номерах форм в парадигме для всех окончаний.
trie с ключами-строками и значениями-индексами:
datrie.BaseTrie( 'suff1': index1, 'suff2': index2, ... )
По индексу index<N> можно из предудыщих 2х массивов получить наборы форм для данного окончания.
Note
Длины хранятся 2 раза. Может, это можно как-то улучшить?