.. _dictionary: Словари ======= В pymorphy2 используются словари из проекта OpenCorpora_, специальным образом обработанные для быстрых выборок. .. _OpenCorpora: http://opencorpora.org Упаковка словаря ---------------- Исходный словарь из OpenCorpora_ представляет собой файл, в котором слова объединены в :term:`лексемы <лексема>` следующим образом:: 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 Сначала указывается номер лексемы, затем перечисляются формы слова и соответствующая им грамматическая информация (:term:`тег`). Первой формой в списке идет :term:`нормальная форма слова`. В словаре около 400тыс. лексем и 5млн отдельных слов. .. note:: С сайта OpenCorpora_ для скачивания доступны plaintext- и XML-версии словаря. В pymorphy2 используется XML-версия, но (для простоты) тут и далее в примерах показан plaintext-формат. Сами данные в XML-версии те же. Если просто загрузить все слова и их грамматическую информацию в питоний list, то это займет примерно 2Гб оперативной памяти. Кроме того, эта форма неудобна для быстрого выполнения операций по анализу и склонению слов. Упаковка грамматической информации ---------------------------------- Каждым :term:`тегом <тег>` (например, ``NOUN,anim,masc sing,nomn``) обычно помечено более одного слова (часто - очень много слов). Хранить строку целиком для всех 5млн слов накладно по 2 причинам: - в питоне не гарантировано, что ``id(string1) == id(string2)``, если ``string1 == string2`` (хотя функция ``intern`` может помочь); - строки нельзя хранить в `array.array`_, а у list накладные расходы выше, т.к. он в питоне реализован как массив указателей на объекты, поэтому в случае с тегами важно, чтоб каждому слову была сопоставлена цифра, а строка. .. _array.array: http://docs.python.org/3/library/array.html В 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', # ... ] .. _paradigms: Парадигмы --------- Изначально в словаре из OpenCorpora_ нет понятия :term:`парадигмы <парадигма>` слова (парадигма - это образец для склонени или спряжения слов). В pymorphy2 выделенные явным образом словоизменительные парадигмы необходимы для того, чтоб склонять неизвестные слова (т.к. при этом нужны образцы для склонения). .. note:: Для других операций явно выделенные парадигмы тоже могут быть удобными, хотя все, кроме склонения неизвестных слов, можно было бы выполнять достаточно быстро и без явно выделенных парадигм. Пример исходной лексемы:: тихий 100 тихого 102 тихому 105 ... тише 124 потише 148 У слов в этой лексеме есть неизменяемая часть (:term:`стем` "ти"), изменяемое "окончание" и необязательный "префикс" ("по"). Выделив у каждой формы "окончание" и "префикс", можно разделить лексему на стем и таблицу для склонения:: стем: ти таблица для склонения ("окончание", номер тега, "префикс"): "хий" 100 "" "хого" 102 "" "хому" 105 "" ... "ше" 124 "" "ше" 125 "по" Для многих :term:`лексем <лексема>` таблицы для склонения получаются одинаковыми. В pymorphy2 выделенные таким образом таблицы для склонения принимаются за парадигмы. "Окончания" и "префиксы" в парадигмах повторяются, и хорошо бы их не хранить по многу раз (а еще лучше - создавать поменьше питоньих объектов для них), поэтому все возможные "окончания" хранятся в отдельном массиве, а в парадигме указывается только номер "окончания"; с "префиксами" - то же самое. В итоге получается примерно так:: 55 100 0 56 102 0 57 105 0 ... 73 124 0 73 125 1 .. note:: Сейчас все возможные окончания парадигм хранятся в 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 все связанные лексемы просто объединяются в одну большую лексему на этапе подготовки (компиляции) исходного словаря; в скомпилированном словаре информация о связях между лексемами в явном виде недоступна. .. _word-packing: Упаковка слов ------------- Для хранения данных о словах используется граф (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 позволяет также быстро и правильно :ref:`обрабатывать букву "ё" `. .. note:: На самом деле граф будет немного не такой, т.к. текст кодируется в utf-8, а значения в base64, и поэтому узлов будет больше; для получения одной буквы или цифры может требоваться совершить несколько переходов. Кодировка utf-8 используется из-за того, что кодек utf-8 в питоне в несколько раз быстрее однобайтового cp1251. Кодировка цифр в base64 - тоже деталь реализации: C++ библиотека, на которой основан DAWG_, поддерживает только нуль-терминированные строки. Байт 0 считается завершением строки и не может присутствовать в ключе, а для двухбайтовых целых числел сложно гарантировать, что оба байта ненулевые. .. note:: Подход похож на тот, что описан на `aot.ru `_. .. _DAWG: https://github.com/kmike/DAWG .. _DAWG-Python: https://github.com/kmike/DAWG-Python .. _dawgdic: https://code.google.com/p/dawgdic/ Итоговый формат данных ---------------------- Таблица с грамматической информацией ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ :: ['tag1', 'tag2', ...] ``tag`` - :term:`тег` (грамматическая информация, набор граммем): например, ``NOUN,anim,masc sing,nomn``. Этот массив занимает где-то 0.5M памяти. Парадигмы ^^^^^^^^^ :: paradigms = [ array.array("``, ``tag_id`` и ``pref_id`` - это индексы в таблицах с возможными "окончаниями" ``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 со словами все ключи, которые начинаются # с <СЛОВО> (обходом по графу); из этих ключей (из того, что за ) # получаем список кортежей [(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 есть :ref:`предсказатель `. Формат хранения словаря ----------------------- Итоговый словарь представляет собой папку с файлами:: 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 - это массив чисел в двоичном виде. .. note:: Если вы вдруг пишете морфологический анализатор не на питоне (и формат хранения данных устраивает), то вполне возможно, что будет проще использовать эти подготовленные словари, а не конвертировать словари из OpenCorpora еще раз; ничего специфичного для питона в сконвертированных словарях нет. Характеристики -------------- После применения описанных выше методов в pymorphy2 словарь со всеми сопутствующими данными занимает около 15Мб оперативной памяти; скорость разбора - порядка 50..150 тыс слов/сек. Для сравнения: * в 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Мб; * в :ref:`первом варианте <2trie>` формата словарей pymorphy2 (от которого я отказался) получалась скорость 20-60тыс слов/сек при 30M памяти или 2-5 тыс слов/сек при 5Мб памяти (предсказатель там не был реализован). Цели обогнать C/C++ реализации у pymorphy2 нет; цель - скорость базового разбора должна быть достаточной для того, чтоб "продвинутые" операции работали быстро. Мне кажется, 100 тыс. слов/сек или 300 тыс. слов/сек - это не очень важно для многих задач, т.к. накладные расходы на обработку и применение результатов разбора все равно, скорее всего, "съедят" эту разницу (особенно при использовании из питоньего кода). .. _mystem: http://company.yandex.ru/technologies/mystem/ .. _pymorphy 0.5.6: http://pymorphy.readthedocs.org/en/v0.5.6/index.html .. _MAnalyzer: https://github.com/Melkogotto/MAnalyzer