pymorphy2

В 2012м я начал потихоньку делать pymorphy2 (github, bitbucket) — думаю, самое время представить эту библиотеку тут: pymorphy2 может работать в сотни раз быстрее, чем pymorphy (втч без использования C/C++ расширений) и при этом требовать меньше памяти; там лучше словари, лучше качество разбора, лучше поддержка буквы ё, проще установка и более «честный» API. Из негатива — не все возможности pymorphy сейчас реализованы в pymorphy2.

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

Какие были проблемы у pymorphy:

• достаточно медленная скорость работы (несколько сотен слов/сек при установке по умолчанию);
• зависимость от словарей с aot.ru, которые непонятно как пополнять / исправлять;
• некоторые проблемы с API — например, по API для склонятора могло показаться, что библиотека сама снимает неоднозначность разбора, хотя это и не так;
• буква ё поддерживалась способом «везде заменить все ё на е»;
• достаточно сложная установка — нужно качать словари, какие-то разные форматы и т.д. (даже на японском кто-то серию видеоуроков сделал);
• Python 3.x поддерживался только в версии с bitbucket, которая так и не была выпущена в свет;
• невозможно склонять инфинитив: глагол было можно поставить в форму инфинитива, а обратно — уже нет;
• слова, записанные через дефис, склонялись не всегда правильно;
• ну и т.д.

До того, как сделать pymorphy, я ни на Python не писал никогда, ни обработкой текстов на естественном языке не занимался (pymorphy был способом поразбираться и в том, и в другом) — вполне понятно, что там многое можно было сделать лучше.

Но многое в pymorphy1 было все-таки сделано правильно. Например, документация на русском и установка без особых зависимостей (главное — без необходимости в компиляторе); более-менее нормальный процесс разработки с тестами; само качество разбора и предсказания было достаточно высоким. Интеграция с django была тоже хорошим «маркетинговым» ходом — с ней, правда, были некоторые концептуальные проблемы (нельзя правильно просклонять слово прямо в шаблоне, не разрешив неоднозначность разбора — а это в API никак предусмотрено не было).

Несмотря на все свои недостатки, библиотека (неожиданно) оказалась довольно востребованной — например, нагуглил, что pymorphy был слегка использован при разработке системы Speech-to-Text для русского языка в рамках французского проекта Quaero, и рекомендуется в качестве учебного материала в некоторых ВУЗах. Не думаю, что тут какая-то большая моя заслуга, скорее просто оказался в нужном месте в нужное время.

Я долго не хотел ломать обратную совместимость и пытался развивать то, что есть (хотя buriy, например, даже форк сделал, который ломал обратную совместимость, но работал быстрее). Решающим толчком к написанию pymorphy2 послужил проект OpenCorpora — ребята оттуда, кроме всего прочего (а там много «всего прочего»), взяли словарь из aot.ru, полностью переделали его структуру и занялись пополнением и прочими улучшениями.

Итак, появилась идея использовать словарь из OpenCorpora.

В pymorphy использовались словари из aot.ru, почти никак не обработанные (они переводились в формат sqlite, но по сути структура оставалась та же). Отдельно хранились «основы» слов, отдельно «приставки», отдельно «окончания», и отдельно — правила образования слов из этих частей. Этот способ был хорош тем, что на его основе удалось реализовать морфологический анализатор за пару «уикендов» без особых усилий и исследований.

Но все это — доступ к данным через множество оберток и (особенно) сбор слов из частей питоньим кодом — негативно сказывалось на скорости работы; как-то радикально улучшить скорость у меня при таком подходе не получалось, решения были сложные и не особо помогали (примечание: вариант «переписать все как есть, но на C++» работает быстро, но требует больше памяти, чем в pymorphy2 в итоге получилось).

Короче говоря, в pymorphy2 я захотел попробовать какой-то другой подход, раз уж словари новые, и все равно многое, связанное со словарями, переписывать. При этом хотелось, чтоб pymorphy2 остался питоньей библиотекой, а не просто оберткой к куче С/С++ кода — хотелось, чтоб логика разбора так и осталась на питоне. Было несколько вариантов, что делать.

Автоматы-автоматы

Первый вариант, который приходил на ум — переформулировать задачу в терминах конечных автоматов. lightcaster хорошо описал подход тут: habrahabr.ru/post/109736/. Подход красивый, что есть то есть.

Что меня тут смутило:

а) в статье ипользовалась C++ библиотека OpenFST (вроде самый популярный способ реализации конечных автоматов), но заставлять пользователей ставить ее вручную — не вариант;
б) даже с использованием C++ библиотеки результаты, судя по статье, были достаточно скромные (2 тыс слов/сек против 100+ тыс слов/сек у mystem или lemmatizer); понятное дело, что эту цифру можно было бы, скорее всего, значительно улучшить (да и lightcaster пишет, что ничего не оптимизировал) — но все же;
в) это один из тех подходов, который (по моему мнению) повышает порог вхождения — я считаю, что это скорее минус.

В итоге получалось, что мне нужно было бы: разобраться, как оптимизировать код и почему даже с C++ библиотекой получается так медленно; написать более простую в установке обертку для OpenFST (или использовать другую реализацию FST — например, сделать свою) + сделать реализацию небольшой части OpenFST (или просто реализацию FST) на Python (чтоб pymorphy можно было использовать без компилятора), ну и формулировать все алгоритмы в терминах конечных автоматов.

Несколько лет назад lightcaster присылал мне еще набросок реализации pymorphy на конечных автоматах (питоний, без C расширений, я в нем ничерта тогда не понял 🙂 — набросок в итоге работал со скоростью тоже около 2тыс слов/сек и требовал около 300Мб памяти. Все это, с одной стороны, неплохо, но с другой — не очень вдохновляло все-таки; было ясно, что если решать этим методом «в лоб», то будет работать не очень-то и быстро, и что нужно писать сильно лучше, чем человек, в теме разбирающийся. Короче, показалось, что это много работы и негарантированный результат (+ еще другие соображения архитектурного характера, ближе к концу статьи будут). Возможно, и неправильно показалось, кто знает — я ж не пробовал, отговорки только.

Этим путем (рассматривать задачу исключительно как задачу об автоматах) я не пошел. Хотя — как сказать, все зависит от точки зрения 🙂

Скопируем-ка mystem

Второй вариант был — реализовать примерно то, что описано в публикации по mystem. Я не знаю, использует ли сейчас mystem те же алгоритмы, но метод, описанный в статье — вполне разумный. Про mystem пишут много хорошего, поэтому сперва я попробовал реализовать в pymorphy2 примерно то, что описано в публикации.

Trie

В методе используются префиксные деревья (Trie) — чтоб реализовать метод, нужна реализация Trie для Python. Мне не хотелось использовать питонью реализацию (я опасался за скорость и прожорливость по памяти), а готовых python-оберток к какой-нибудь хорошей C/C++ реализации Trie я, к удивлению, не нашел.

Писать свою C/C++ реализацию структур данных смысл бывает редко: на C/C++ очень много чего уже есть, и многие из библиотек реализуют state-of-art алгоритмы. Почему? Вот придумал человек хитрую структуру данных, написал об этом статью в научный журнал. Чтоб результаты можно было повторить, автор нередко выкладывает реализацию, и чаще всего — именно на C или C++. Если и не выкладывает, то кто-нибудь другой бумагу читает и пишет реализацию — тоже именно на C/C++ (ok, иногда еще на Java пишут такое).

Да и все-таки pymorphy2 — это хобби-проект, и тратить на него очень много времени не получилось бы; лучше было постараться расходовать время эффективно и изобретать поменьше велосипедов. Короче говоря, решил я взять готовую реализацию Trie и сделать для нее обертку на Cython (отдельным пакетом, никак не связанным с pymorphy2).

В этом подходе есть 2 больших плюса:

1) Структуру данных можно будет использовать и для других целей; даже если бы подход себя не оправдал (спойлер: так и вышло, он себя не оправдал), то усилия бы не были потрачены зря;
2) сложность, связанная со структурами данных, «утаскивается» из самого морфологического анализатора; анализатор общается с Trie через простой API, а сам занимается только собственно разбором слов. Чтоб понять алгоритм работы, не нужно детально разбираться в том, как устроено префиксное дерево. Кроме того, замена реализации базовых структур данных (например, на питонью) — задача простая; у нас есть четко выраженная граница (=интерфейс) между морф. анализатором и хранилищем для слов.

Сперва мне приглянулась библиотека libdatrie, про обертку для нее писал тут: habrahabr.ru/post/147963/. Некоторые вещи в библиотеке пришлось поправить (обычно выходило так — я писал рабочую реализацию на C, автор библиотеки все выкидывал и писал более идиоматичный C код для того же самого — и правильно делал, т.к. C-код у него и правда был лучше :); в итоге получилась вполне себе юзабельная обертка.

С datrie и подходом «укради все у mystem!» получалось 20-60тыс слов/сек (без предсказателя и с минимумом питоньей обвязки; почему такой разброс — не помню уже, погода, наверное), и занимало это все около 30Мб памяти.

Со скоростью затык был в неожиданном (для меня) месте: больше всего тормозило сопоставление допустимых разборов для «окончаний» слова и допустимых разборов для «начал» слов (это часть алгоритма). В моей реализации это сводилось к нахождению пересечения 2 отсортированных списков цифр. Очевидный способ («параллельно пройтись по обоим спискам») оказался в этой задаче гораздо медленней, чем подход «идти по короткому списку, а в длинном искать цифры сужающимся двоичным поиском». Но и этот второй вариант оставался узким местом, даже переписанный на Cython — что с ним делать, я не знал. Наверное, можно было этот код написать получше, но сразу не получилось.

Кроме того, 30Мб — это, с одной стороны, хорошо, а с другой — у aot.ru ведь меньше (то пишут, что 9Мб, то 19Мб — будем считать, что 9, у меня руки не дошли проверить). Потребление памяти — это важно, т.к. pymorphy используется еще и для стрельбы из пушки по воробьям (склонения слов на сайте), а это требует загружать его в каждый веб-процесс. Ну или если не загружать (из-за того, что памяти жалко), то городить огород с отдельным сервисом (на zeromq каком-нибудь, или с общением по http) — чего тоже не хочется.

Реализация datrie — это не «наивное» trie на указателях, datrie и так раза в 2 памяти меньше должен требовать, чем обычное префиксное дерево (так что 30Мб — это еще хорошо).

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

marisa-trie

Но я решил не сдаваться и не отказываться от подхода «a la mystem», а попробовать заменить datrie на что-то еще (что было довольно глупо, но имело хорошие последствия). Выбор пал на C++ библиотеку marisa-trie, которую написал гуру структур данных Susumu Yata. Для нее я тоже сделал python-обертку примерно с тем же интерфейсом, что и у datrie.

Когда я начал тестировать marisa-trie, у меня сперва глаза на лоб полезли. Смотрите:

• если взять и загрузить все 3 миллиона русских слов в питоний словарь, это займет около 600Мб оперативной памяти (в list — около 300Мб);
• если загрузить эти же данные в datrie, то это займет 70Мб RAM — что уже достаточно круто;
• а если загрузить эти же данные в MARISA-Trie, то это займет еще в 10 раз меньше — 7Мб памяти.

Как так получается? Дело в том, что MARISA-Trie — это на самом деле вовсе не Trie 🙂 Что это такое — я так по-нормальному и не разобрался; папка с «мясом» в исходниках называется grimoire; описание алгоритма — исключительно на японском.

Судя по всему, MARISA-Trie — это «succinct» реализация Patricia-Trie (wiki), в которой каждому узлу может сопоставляться не только текстовая информация, но и MARISA-Trie следующего уровня. «Succinct» означает, что структура дерева закодирована битовым массивом, что позволяет тратить на нее очень мало памяти. Ну и там есть интересная особенность: MARISA Trie выступает сразу еще и в роли «perfect hash». Каждому ключу присваивается уникальный номер из диапазона 0 до len(trie)-1, и каждому числу от 0 до len(trie)-1 соответствует единственный ключ; можно как по номеру получить ключ, так и по ключу получить номер.

По скорости — datrie быстрее, чем marisa-trie, раз в 10.

Вернемся к pymorphy. После простой замены datrie на marisa-trie у меня получилось, что все хозяйство занимает 5Мб памяти, а работает со скоростью 2-5 тыс слов/сек (без предсказателя).

С одной стороны — 5Мб — это круто (хотя пока и без предсказателя). Но с другой — 2-5 тыс слов/сек — медленно после 20-60 тыс слов/сек, + жестко завязываться на marisa-trie не очень хотелось, т.к. это бы привело к требованию компилятора для установки pymorphy2. Я вполне понимал, как работает datrie, и написать совместимую питонью реализацию проблемой бы не стало, но marisa-trie… В случае с marisa-trie портировать было бы можно, но это бы потребовало больше усилий, и работало бы, скорее всего, мееедленно — этот вопрос бы, вероятно, «отложился», и pymorphy2 требовал бы компилятор для установки.

Сама по себе попытка была тупиковой, но выявила одну интересную вещь: 5Мб (алгоритм «почти mystem» + marisa-trie) и 7Мб («все слова целиком поместим в marisa-trie») — цифры очень даже сопоставимые. Эти цифры открыли мне наконец глаза на тот факт, что не стоит отбрасывать подходы, при которых все слова будут загружаться в память сразу и целиком (без разбиения на начала и концы).

Интуитивно: если все слова держать в памяти «как есть», то нужно будет делать меньше вычислений, слова не нужно будет собирать из кусочков — все должно работать быстрее, и код должен получиться проще.

На этом месте идеей «скопировать mystem» я заниматься прекратил; недоделанные варианты с datrie и marisa-trie доступны в ранних коммитах pymorphy2.

У меня есть подозрение, что в mystem используется (ну согласно публикации, я не могу знать, что там сейчас используется) несколько trie с частями слов не из-за того, что они позволяют как-то удобнее описывать алгоритмы для предсказателя, а просто для того, чтоб не хранить все слова в памяти в полном виде. По моим тестам, с обычным trie это бы заняло (слова + данные о их парадигмах) мегабайт 300-400, с datrie — мегабайт 200, но с MARISA-Trie все можно было бы вместить мегабайт в 20. Использовать несколько «обычных» trie, как в бумаге по mystem — хороший трюк, но этот способ, как мне думается (могу быть не прав, до конца подход «хочу свой mystem» не довел), принципиально работает медленнее, чем «все слова храним как есть».

Назад в будущее

Само по себе MARISA-Trie для того, чтоб держать все слова в памяти, не подходило (т.к. было небыстрым — что нивелировало выигрыш в скорости; + в API отсутствовала возможность «пошагово» перемещаться по дереву произвольным образом, что было нужно я-уже-не-помню-для-чего, вероятно — для правильной поддержки буквы ё). Дальше было смутное воспоминание о том, что в aot.ru все слова как-то в памяти держали сразу.

Итак, я стал перечитывать описание морфологического анализатора с aot.ru, а в частности — параграф «Бинарное представление словаря». Вернулся, так сказать, к тому, с чего все началось.

В статье на aot.ru все называется «автомат».

Вариант с «отчуждаемой» структурой данных (которую можно использовать для чего-то еще — ну как datrie или marisa-trie) мне архитектурно нравился (и нравится) гораздо больше специализированного автомата со словарем. Специализированный автомат был бы «похоронен» в pymorphy2 — оттуда ничего нельзя было бы использовать повторно, отлаживать его можно было бы только в рамках pymorphy, и сложность накапливалась бы именно в рамках pymorphy. Я обычно пробегал глазами тот параграф, думал «хм-хм, нехорошо» и выдумывал способ, как бы сделать по-другому.

Но на вещи можно смотреть под разными углами. Наверное, это должно было бы быть очевидным с самого начала, но до меня только после того, как попробовал сделать «клон mystem», дошло, что автомат, используемый в aot, на самом деле ровно то же самое, что структура данных DAWG, в которую в качестве ключей записываются слова (с приписанными в конец аннотациями). И что все операции, описанные там, прекрасно ложатся на тот же самый API, который был в datrie и marisa-trie.

Вот уж правду говорят, что «There are only two hard problems in Computer Science: cache invalidation and naming things.» Не знаю насчет «cache invalidation», но вот «naming things» тут прочувствовал в полной мере.

Кажешься себе полным идиотом в такие моменты; все было просто, все было перед глазами с самого начала, и мне об этом много раз говорили (и про автоматы, и про DAWG).

Итак, новый план был такой: по проторенной дорожке

1. найти реализацию DAWG на С/С++;
2. сделать для неё обертку с тем же API, что у datrie и marisa-trie;
3. записать в DAWG все слова (сразу с информацией об их грамматических формах)
4. бонус — сделать исключительно питонью библиотечку для чтения DAWG-ов, чтоб упростить установку.

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

Хорошая библиотека для DAWG (dawgdic) нашлась у того же Susumu Yata, который написал marisa-trie; я сделал для нее питонью обертку: github.com/kmike/DAWG и питонью «читалку» этого формата: github.com/kmike/DAWG-Python (для установки которой не нужен компилятор).

Весь словарь целиком без аннотаций занял в DAWG около 3Мб, а с аннотациями (= с информацией о том, как каждое слово разбирать) — около 7Мб. Для сравнения — если загрузить все эти данные в питоний словарь «как есть», то это занимает несколько гигабайт памяти.

Дальше оставалось только написать pymorphy2 🙂

Статья и так получается какая-то бесконечная, а про то, как pymorphy2 внутри устроен сейчас — пока почти ничего и не было. Чтоб не раздувать текст еще больше, ничего и не будет; о том, как внутри устроен pymorphy2, довольно (излишне?) подробно рассказано в документации, даже с картинками. Я бы все-таки отметил, что pymorphy2 — это не клон lemmatizer на Python, там все устроено по-другому, но информация с aot.ru, конечно, помогла сильно.

Приведу тут два забавных бенчмарка (процессор ноутбучный 1.8 Ghz, под Python 3.3 с использованием DAWG и под PyPy 1.9 с использованием DAWG-Python):

Memory usage: 13.8M dictionary, 25.4M total (load time 0.14s) py33 runtests: commands[1]  benchmarking MorphAnalyzer():     morph.parse(w)                                     29950 words/sec      morph.parse(w)                                     47474 words/sec (considering word frequencies)     morph.word_is_known(w)                             244816 words/sec      [p.normal_form for p in morph.parse(w)]            27807 words/sec      [p.normalized for p in morph.parse(w)]             18231 words/sec      [p.lexeme for p in morph.parse(w)]                 3421 words/sec      [{'NOUN'} in p.tag for p in morph.parse(w)]        23862 words/sec      [p.tag.POS == 'NOUN' for p in morph.parse(w)]      22157 words/sec       morph.tag(w): 96342 words/sec (considering word frequencies)     morph.tag(w): 46767 words/sec     morph.tag(w): 46935 words/sec (umlauts removed from input)     morph.tag(w): 36331 words/sec (str(tag) called)  benchmarking MorphAnalyzer(result_type=None):     morph.parse(w)                                     35088 words/sec      morph.parse(w)                                     62431 words/sec (considering word frequencies) 

Memory usage: 40.5M dictionary, 84.8M total (load time 0.39s) pypy runtests: commands[1]  benchmarking MorphAnalyzer():     morph.parse(w)                                     41360 words/sec      morph.parse(w)                                     108858 words/sec (considering word frequencies)     morph.word_is_known(w)                             243742 words/sec      [p.normal_form for p in morph.parse(w)]            51728 words/sec      [p.normalized for p in morph.parse(w)]             37551 words/sec      [p.lexeme for p in morph.parse(w)]                 14612 words/sec      [{'NOUN'} in p.tag for p in morph.parse(w)]        44878 words/sec      [p.tag.POS == 'NOUN' for p in morph.parse(w)]      45129 words/sec       morph.tag(w): 133086 words/sec (considering word frequencies)     morph.tag(w): 60049 words/sec     morph.tag(w): 62567 words/sec (umlauts removed from input)     morph.tag(w): 52632 words/sec (str(tag) called)  benchmarking MorphAnalyzer(result_type=None):     morph.parse(w)                                     60777 words/sec      morph.parse(w)                                     124226 words/sec (considering word frequencies) 

Забавным тут я нахожу то, что (а) цифры очень похожие, несмотря на то, что «внутри» действия очень разные (C++ обертка + интерпретатор vs jit-компилятор), и (б) что PyPy быстрее.

Сама по себе реализация DAWG на C++ (если ее использовать из питона, с учетом Cython-обертки) в несколько раз быстрее, чем DAWG-Python под PyPy, и ранние версии pymorphy2 (которые делали всего меньше) были быстрее под CPython. С течением времени фич становилось больше, код сложнее, pymorphy2 тормознее (ранние версии и 200+тыс слов/сек разбирать могли — правда, не очень хорошо и не очень удобно); более быстрая базовая структура данных «перевешивать» перестала — и под PyPy pymorphy2 теперь работает быстрее. С другой стороны, ускорить версию под CPython понятно как — переписать еще что-нибудь на Cython (к слову: делать я этого не планирую); с PyPy это не так очевидно.

Можно заметить, что разбор 100 тыс слов/сек в реальном тексте вполне можно получить как с Python 3.3 (получение грамматической информации), так и с PyPy (полный разбор, с начальной формой и удобным API). Для сравнения: «настоящий» mystem (написанный, видимо, на C++) работал (по моим тестам когда-то на ранних этапах) всего раза в полтора-два быстрее, и требовал столько же памяти; из этого я для себя сделал вывод — возможно, неправильный, — что в mystem используется все-таки подход с несколькими trie; если бы слова хранились целиком, С++ реализация отрываться должны была бы сильнее, даже если mystem и что-то еще вдобавок делает хитрое. Ну это так, опять ничем не подкрепленная болтовня.

Если не использовать ни PyPy, ни C++ реализацию DAWG, pymorphy2 все равно будет работать во много раз быстрее (по прикидкам — в пару десятков раз), чем pymorphy1 cо всеми включенными ускорениями — ну и разбирать лучше.

Как можно помочь

Интересный вопрос остается — что делать с pymorphy1. Там сейчас есть фичи, которых нет в pymorphy2 (например, интеграция с django, согласование слов с цифрами и склонение фамилий), но в версии на битбакете я поломал обратную совместимость. Выпускать еще одну обратно несовместимую версию pymorphy как-то глупо 🙂 поэтому там все болтается в подвешенном состоянии. У меня рук на все категорически не хватает.

• Было бы здорово, если б кто-то помог с портированием недостающих фич из pymorphy1;
• любая помощь OpenCorpora — это помощь и pymorphy2 тоже;
• в трекере есть немало открытых багов (разной степени хардкорности);
• в pymorphy2 сейчас встроен очень примитивный токенизатор — можно повыдумывать токенизатор получше; там еще хорошо бы понять, как соотносятся классы из pymorphy2.units.by_shape.py с токенизацией;
• можно улучшить CLI, чтоб pymorphy2 можно было использовать как полноценную утилиту командной строки;
• можно попробовать написать еще предсказатели для pymorphy2 (см. как сделаны нынешние в pymorphy2.units) — нужно больше глаз, чтоб понять, хороший ли интерфейс для расширения (+ возможно, получится улучшить разбор и добавить что-то новое в стандартную поставку);
• ну и можно просто начать использовать pymorphy2.

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

Да и в pymorphy2 уже несколько людей серьезный вклад внесли, кстати 🙂

Ссылки

• Исходный код: github, bitbucket
• Документация: pymorphy2.rtfd.org
• Баг-трекер: github.com/kmike/pymorphy2/issues
• Обсуждение/поддержка: гугл-группа
• Структуры данных для Python, возникшие в процессе: DAWG, DAWG-Python, marisa-trie, datrie, hat-trie