В далеком 2009 году на хабре уже была статья "Кузявые ли бутявки.." про pymorphy — морфологический анализатор для русского языка на Python (штуковину, которая умеет склонять слова, сообщать информацию о части речи, падеже и т.д.)
В 2012м я начал потихоньку делать pymorphy2 (github, bitbucket) — думаю, самое время представить эту библиотеку тут: pymorphy2 может работать в сотни раз быстрее, чем pymorphy (втч без использования C/C++ расширений) и при этом требовать меньше памяти; там лучше словари, лучше качество разбора, лучше поддержка буквы ё, проще установка и более «честный» API. Из негатива — не все возможности pymorphy сейчас реализованы в pymorphy2.
Эта статья о том, как pymorphy2 создавался (иногда с довольно скучными техническими подробностями), и сколько глупостей я при этом наделал; если хочется просто все попробовать, то можно почитать документацию.
Какие были проблемы у pymorphy:
До того, как сделать 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 пишут много хорошего, поэтому сперва я попробовал реализовать в pymorphy2 примерно то, что описано в публикации.
В методе используются префиксные деревья (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Мб — это еще хорошо).
Плюс как-то сложно все получалось, с точки зрения алгоритмов; было видно, что если дальше доделывать (предсказатель, эвристики), то все будет сильно медленнее и еще сложнее. Непорядок.
Но я решил не сдаваться и не отказываться от подхода «a la mystem», а попробовать заменить datrie на что-то еще (что было довольно глупо, но имело хорошие последствия). Выбор пал на C++ библиотеку marisa-trie, которую написал гуру структур данных Susumu Yata. Для нее я тоже сделал python-обертку примерно с тем же интерфейсом, что и у datrie.
Когда я начал тестировать marisa-trie, у меня сперва глаза на лоб полезли. Смотрите:
Как так получается? Дело в том, что 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).
Итак, новый план был такой: по проторенной дорожке
Морфологический разбор словарных слов при этом сводится просто к тому, чтоб достать информацию о слове из 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):
Забавным тут я нахожу то, что (а) цифры очень похожие, несмотря на то, что «внутри» действия очень разные (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 как-то глупо :) поэтому там все болтается в подвешенном состоянии. У меня рук на все категорически не хватает.
В разработке pymorphy принимало участие большое число людей, многие из которых внесли на самом деле серьезный вклад, и далеко не все из этого перенесено в pymorphy2; не хотелось бы, чтоб труд пропал (думаю, что и не пропадет). Без этой помощи у меня никогда не хватило бы ни мотивации поддерживать pymorphy, ни мотивации переписать все как pymorphy2.
Да и в 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) для всех перевернутых «окончаний» слов. За «окончание» берется примерно то же, что и у aot.ru — часть слова справа, которая изменяется при склонении. Ну, например, у слова «хомяками» это может быть «ами» — в trie добавляем «има».
в) строится префиксное дерево (trie) для всех перевернутых «основ» слова. Например, для слова «хомяками» это «кямох». Кроме того, в конец «основы» приписываются (через разделитель) возможные индексы моделей склонения (парадигм) для этой основы. Например, если «хомяк» можно склонять по парадигмам А и B, а разделитель выбран $, то в trie добавим значения «кямох$A» и «кямох$B». В статье по mystem использовалось не одно дерево для основ, а много (мое мнение — в качестве меры оптимизации) — но на алгоритм это влияет не сильно, будем считать, что дерево тут одно.
г) собственно анализ слова: идем по слову с конца, собираем из первого trie все возможные «окончания» (в префиксном дереве эта операция выполняется за O(1) от числа слов в trie и за O(N) от длины слова). Предположим, для «хомяками» мы могли найти, что есть слова, которые имеют словоизменительное окончание "" (пустое), «и», «ами» или «ками». Этим «окончаниям» соответствуют «основы»: хомяками, хомякам, хомяк и хомя.
д) берем самую короткую найденную основу и ищем ее во втором trie (идем до разделителя $). Если нашли, то кроме самой основы мы сразу получаем все возможные индексы моделей склонения слова (они за разделителем). Для каждой из моделей склонения теперь можно проверить, есть ли там форма с нужным нам окончанием (найденным на шаге (г)) — если есть, то мы разобрали слово.
е) если ничего не нашли, то значит словарного слова с самой короткой основой нет — можно перейти к более длинной основе; можно также проверить похожие основы (из бумаги я не понял, что именно делается, но это не суть — можно, например, попробовать следующую, более длинную основу; после того, как все возможные основы опробованы, начать уже искать схожие слова — вполне работает).
В бумаге еще описаны различные эвристики, которые позволяют сократить размер словаря и убрать маловероятные варианты предсказаний.
Я мог что-то переврать или понять неправильно; если для дела нужно, то лучше оригинальную статью читать, понятное дело.
б) Строится префиксное дерево (trie) для всех перевернутых «окончаний» слов. За «окончание» берется примерно то же, что и у aot.ru — часть слова справа, которая изменяется при склонении. Ну, например, у слова «хомяками» это может быть «ами» — в trie добавляем «има».
в) строится префиксное дерево (trie) для всех перевернутых «основ» слова. Например, для слова «хомяками» это «кямох». Кроме того, в конец «основы» приписываются (через разделитель) возможные индексы моделей склонения (парадигм) для этой основы. Например, если «хомяк» можно склонять по парадигмам А и B, а разделитель выбран $, то в trie добавим значения «кямох$A» и «кямох$B». В статье по mystem использовалось не одно дерево для основ, а много (мое мнение — в качестве меры оптимизации) — но на алгоритм это влияет не сильно, будем считать, что дерево тут одно.
г) собственно анализ слова: идем по слову с конца, собираем из первого trie все возможные «окончания» (в префиксном дереве эта операция выполняется за O(1) от числа слов в trie и за O(N) от длины слова). Предположим, для «хомяками» мы могли найти, что есть слова, которые имеют словоизменительное окончание "" (пустое), «и», «ами» или «ками». Этим «окончаниям» соответствуют «основы»: хомяками, хомякам, хомяк и хомя.
д) берем самую короткую найденную основу и ищем ее во втором trie (идем до разделителя $). Если нашли, то кроме самой основы мы сразу получаем все возможные индексы моделей склонения слова (они за разделителем). Для каждой из моделей склонения теперь можно проверить, есть ли там форма с нужным нам окончанием (найденным на шаге (г)) — если есть, то мы разобрали слово.
е) если ничего не нашли, то значит словарного слова с самой короткой основой нет — можно перейти к более длинной основе; можно также проверить похожие основы (из бумаги я не понял, что именно делается, но это не суть — можно, например, попробовать следующую, более длинную основу; после того, как все возможные основы опробованы, начать уже искать схожие слова — вполне работает).
В бумаге еще описаны различные эвристики, которые позволяют сократить размер словаря и убрать маловероятные варианты предсказаний.
Я мог что-то переврать или понять неправильно; если для дела нужно, то лучше оригинальную статью читать, понятное дело.
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).
Итак, новый план был такой: по проторенной дорожке
- найти реализацию DAWG на С/С++;
- сделать для неё обертку с тем же API, что у datrie и marisa-trie;
- записать в DAWG все слова (сразу с информацией об их грамматических формах)
- бонус — сделать исключительно питонью библиотечку для чтения 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
