Warning
Этот формат словарей в pymorphy2 не используется; описание - документация по менее удачной попытке организовать словари.
Первоначальная реализация доступна в одном из первых коммитов. Рассматривайте описанное ниже как бесполезный на практике "исторический" документ.
В публикации по mystem был описан способ упаковки словарей с использованием 2 trie для "стемов" и "окончаний". В первом прототипе pymorphy2 был реализован схожий способ; впоследствие я заменил его на другой.
Этот первоначальный формат словарей в моей реализации обеспечивал скорость разбора порядка 20-60тыс слов/сек (без предсказателя) при потреблении памяти 30М (с использованием datrie), или порядка 2-5 тыс слов/сек при потреблении памяти 5M (с использованием marisa-trie).
Идея была в том, что слово просматривается с конца, при этом в первом trie ищутся возможные варианты разбора для данных окончаний; затем для всех найденных вариантов окончаний "начала" слов ищутся во втором trie; в результате возвращаются те варианты, где для "начала" и "конца" есть общие способы разбора.
Основной "затык" в производительности был в том, что для каждого слова требовалось искать общие для начала и конца номера парадигм. Это задача о пересечении 2 множеств, для которой мне не удалось найти красивого решения. Питоний set использовать было нельзя, т.к. это требовало очень много памяти.
Лучшее, что получалось - id парадигм хранились в 2 отсортированных массивах, а их пересечение находилось итерацией по более короткому массиву и "сужающимся" двоичным поиском по более длинному (параллельная итерация по обоим массивам на конкретных данных оказывалась всегда медленнее).
В pymorphy2 я в итоге решил использовать другой :ref:`формат словарей <dictionary>`, т.к.
- другой формат проще;
- алгоритмы работы получаются проще;
- скорость разбора получается больше (порядка 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 являются стемы (перевернутые), значениями - список с номерами допустимых парадигм.
Для каждого стема требуется хранить множество 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 раза. Может, это можно как-то улучшить?