Кузявые ли бутявки, т.е. пишем морфологический анализатор на Python

Морфологический анализатор для русского языка - это что-то заумное? Программа, которая приводит слово к начальной форме, определяет падеж, находит словоформы - непонятно, как и подступиться? А на самом деле все не так и сложно. В статье - как я писал аналог mystem, lemmatizer и phpmorphy на Python, и что из этого получилось.

А получилась библиотека для морфологического анализа на Python, которую Вы можете использовать и дорабатывать согласно лицензии MIT.

Первый вопрос - зачем все это?

Потихоньку делаю один хобби-проект, назрело решение писать его на Python. А для проекта был жизненно необходим более-менее качественный морфологический анализатор. Вариант с mystem не подошел из-за лицензии и отсутствием возможности поковыряться, lemmatizer и phpmorphy меня слегка напрягали своими словарями не в юникоде, а приличного аналога на python я почему-то не нашел. Вообщем причин много, все, если честно, не очень серьезные, на самом деле просто захотелось. Решил я, в итоге, изобрести велосипед и написать свою реализацию.

За основу взял наработки с сайта aot.ru. Словари (LGPL) для русского и английского, а также идеи - оттуда. Там были описаны и конкретные алгоритмы реализации, но в терминах теории автоматов. Я знаком с теорией автоматов (даже диплом по формальным грамматикам защитил), но мне показалось, что тут можно прекрасно обойтись без нее. Поэтому реализация - независимая, что имеет как плюсы, так и минусы.

Для начала, библиотека должна, как минимум, уметь:

  1. Приводить слово к нормальной форме (например, в ед.ч., И.п. для существительных) - для слова "ЛЮДЕЙ" она должна вернуть "ЧЕЛОВЕК".
  2. Определять форму слова (или формы). Например, для слова "ЛЮДЕЙ" она должна как-то дать знать, что это существительное, во множественном числе, может оказаться в родительном или винительном падежах.

Разбираемся со словарями

Словари с сайта aot.ru содержат следующую информацию:

  1. парадигмы слов и конкретные правила образования;
  2. ударения;
  3. пользовательские сессии;
  4. набор префиксов (продуктивных приставок);
  5. леммы (незменяемые части слова, основы);
  6. и еще есть грамматическая информация - в отдельном файле.

Из этого всего нам интересны правила образования слов, префиксы, леммы и грамматическая информация.

Все слова образуются по одному принципу: [префикс] + [приставка] + [основа] + [окончание]

Префиксы - это всякие "мега", "супер" и т.д. Набор префиксов хранится просто списком.

Приставки - имеются в виду приставки, присущие грамматической форме, но не присущие неизменяемой части слова ("по","наи"). Например, "наи" в слове "наикрасивейший", т.к. без превосходной степени будет "красивый".

Правила образования слов - это то, что надо приписать спереди и сзади основы, чтобы получить какую-то форму. В словаре хранятся пары "приставка - окончание", + "номер" записи о грамматической информации (которая хранится отдельно).

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

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

Грамматическая информация - просто пары ("номер" записи, грам. информация). "Номер" в кавычках, т.к. это 2 буквы, просто от балды, но все разные.

Файл со словарем - обычный текстовый, для каждого раздела сначала указано число строк в нем, а потом идут строки, формат их описан, так что написать парсер труда не составило.

Поняв структуру словаря, уже несложно написать первую версию морфологического анализатора.

Пишем морфологический анализатор

По сути, нам дано слово, и его надо найти среди всех разумных комбинаций вида <префикс> + <приставка> + <лемма> + <окончание> и <приставка> + <лемма> + <окончание>

Дело упрощает то, что оказалось (как показала пара строчек на питоне), что "приставок" у нас в языке (да и в английском вроде тоже) всего 2. А префиксов в словаре - порядка 20 для русского языка. Поэтому искать можно среди комбинаций <префикс> + <лемма> + <окончание>, объединив в уме список приставок и префиксов, а затем выполнив небольшую проверочку.

С префиксом разберемся по-свойски: если слово начинается с одного из возможных префиксов, то мы его (префикс) отбрасываем и пытаемся морфологически анализировать остаток (рекурсивно), а потом просто припишем отброшенный префикс к полученным формам.

В итоге получается, что задача сводится к поиску среди комбинаций <лемма>+<окончание>, что еще лучше. Ищем подходящие леммы, потом смотрим, есть ли для них подходящие окончания [1].

Тут я решил сильно упростить себе жизнь, и задействовать стандартный питоновский ассоциативный массив, в который поместил все леммы. Получился словарь вида lemmas: {base -> [rule_id]}, т.е. ключ - это лемма, а значение - список номеров допустимых парадигм. А дальше поехали - сначала считаем, что лемма - это первая буква слова, потом, что это 2 первых буквы и т.д. По лемме пытаемся получить список парадигм. Если получили, то в каждой допустимой парадигме пробегаем по всем правилам и смотрим, получится ли наше слово, если правило применить. Получается - добавляем его в список найденных форм.

[1]Еще был вариант - составить сразу словарь всех возможных слов вида <лемма>+<окончание>, получалось в итоге где-то миллионов 5 слов, не так и много, но вариант, вообщем, мне не очень понравился.

Дописываем морфологический анализатор

По сути - все готово, мы написали морфологический анализатор, за исключением некоторых деталей, которые заняли у меня 90% времени)

Деталь первая

Если вспомнить пример, который был в начале, про "ЛЮДЕЙ" - "ЧЕЛОВЕК", то станет понятно, что есть слова, у которых неизменяемая часть отсутствует. И где тогда искать формы этих слов - непонятно. Пробовал искать среди всех окончаний (точно так же, как и среди лемм), ведь для таких слов и "ЛЮДЕЙ", и "ЧЕЛОВЕКУ" в словаре будут храниться как окончания. Для некоторых слов работало, для некоторых выдавало, кроме правильного результата, еще и кучу мусора. В итоге, после долгих экспериментов выяснилось, что есть в словаре такая хитрая магическая лемма "#", которая и соответствует всем пустым леммам. Ура, задача решена, ищем каждый раз еще и там.

Деталь вторая

Хорошо бы иметь "предсказатель", который смог бы работать и со словами, которых нет в словаре. Это не только неизвестные науке редкие слова, но и просто описки, например.

Тут есть 2 несложных, но вполне работающих подхода:

  1. Если слова отличаются только тем, что к одному из них приписано что-то спереди, то, скорее всего, склоняться они будут однаково.
  2. Если 2 слова оканчиваются одинаково, то и склоняться они, скорее всего, будут одинаково.

Первый подход - это угадывание префикса. Реализуется очень просто: пробуем считать сначала одну первую букву слова префиксом, потом 2 первых буквы и т.д. А то, что осталось, передаем морфологическому анализатору. Ну и делаем это только для не очень длинных префиксов и не очень коротких остатков.

Второй (предсказание по концу слова) подход чуть сложнее в реализации (так-то сильно сложнее, если нужна хорошая реализация)) и "поумнее" в плане предсказаний.

Первая сложность связана с тем, что конец слова может состоять не только из окончания, но и из части леммы. Тут я тоже решил "срезать углы" и задействовал опять ассоциативный массив с предварительно подготовленными всеми возмоными окончаниями слов (до 5 букв). Не так и много их получилось, несколько сот тысяч. Ключ массива - конец слова, значение - список возможных правил. Дальше - все как при поиске подходящей леммы, только у слова берем не начало, а 1, 2, 3, 4, 5-буквенные концы, а вместо лемм у нас теперь новый монстромассив.

Вторая сложность - получается много заведомого мусора. Мусор этот отсекается, если учесть, что полученные слова могут быть только существительными, прилагательными, наречиями или глаголами. Даже после этого у нас остается слишком много не-мусорных правил. Для определенности, для каждой части речи оставляем только самое распространенное правило.

По идее, если слово не было предсказано как существительное, хорошо бы добавить вариант с неизменяемым существительным в ед.ч. и.п., но это в TODO.

Идеальный текст для проверки работы предсказателя - конечно же, "Сяпала Калуша по напушке", про то, как она там увазила бутявку и что из этого вышло:

Сяпала Калуша по напушке и увазила бутявку. И волит:
— Калушата, калушаточки! Бутявка!
Калушата присяпали и бутявку стрямкали. И подудонились.
А Калуша волит:
— Оее, оее! Бутявка-то некузявая!
Калушата бутявку вычучили.
Бутявка вздребезнулась, сопритюкнулась и усяпала с напушки.
А Калуша волит:
— Бутявок не трямкают. Бутявки дюбые и зюмо-зюмо некузявые. От бутявок дудонятся.
А бутявка волит за напушкой:
— Калушата подудонились! Калушата подудонились! Зюмо некузявые! Пуськи бятые!

Из текста предсказатель не справился с именем собственным Калуша, с "Калушата"(они стали мужиками "Калуш" и "Калушат"), с междометием "Оее", загадочным "зюмо-зюмо", и вместо "Пуська" опять выдал мужика "Пусек", остальное все, на мой взгляд, определил правильно. Вообщем есть куда стремиться, но уже неплохо.

О ужас, "хабрахабр" предсказывается тоже никак. А вот "хабрахабра" - уже понимает, что "хабрахабр".

Тут можно было бы, в принципе, подвести итог, если бы компьютеры работали мгновенно. Но это не так, поэтому есть

Деталь №3: ресурсы процессора и оперативной памяти

Скорость работы первого варианта меня вполне устроила. Получалось, по прикидкам, тыщ до 10 слов в секунду для простых русских слов, около тыщи для навороченных. Для английского - еще быстрее. Но было 2 очевидных (еще до начала разработки) "но", связанных с тем, что все данные грузились в оперативную память (через pickle/cPickle).

  1. первоначальная загрузка занимала 3-4 секунды;
  2. кушалось порядка 150 мегабайт оперативной памяти с psyco и порядка 100 без ( +удалось немного сократить, когда привел всякие там питоновские set и list к tulpe, где возможно).

Не долго думая, провел небольшой рефакторинг и вынес все данные в отдельную сущность. А дальше мне на помощь пришла магия Python и duck typing. Вкратце - в алгоритмах использовались данные в виде ассоциативных и простых массивов. И все будет работать без переписывания алгоритмов, если вместо "настоящих" массивов подсунуть что-нибудь, что ведет себя как массив, а конкретнее, для нашей задачи, - поддерживает [] и in. Все) В стандартной поставке питона обнаружились такие "массивные" интерфейсы к нескольким нереляционным базам данных. Эти базы (bsddb, ndbm, gdbm), по сути, и есть ассоциативные массивы на диске. Как раз то, что нужно. Еще там обнаружилась пара высокоуровневых надстроек над этим хозяйством (anydbm и shelve). Остановился на том, что унаследовался от DbfilenameShelf и добавил поддержку ключей в юникоде и ключей-целых чисел. А, еще добавил кеширование результата, которое почему-то есть в Shelf, но убито в DbfilenameShelf.

Данные по скорости на тестовых текстах (995 слов, русский словарь, macbook):

get_pickle_morph('ru', predict_by_prefix = False): 0.214 CPU seconds
get_pickle_morph('ru'): 0.262 CPU seconds
get_shelve_morph('ru', predict_by_prefix = False): 0.726 CPU seconds
get_shelve_morph('ru'): 0.874 CPU seconds

Памяти вариант shelve, можно сказать, не кушал совсем.

Варианты shelve похоже, работали, когда словари уже сидели в дисковом кеше. Без этого время может быть и 20 секунд с включенным предсказателем. Еще замечал, что медленнее всего работает предсказание по префиксу: до того, как прикрутил кеширование к своим наследникам от DbfilenameShelf, тормозило это предсказание раз в 5 больше, чем все остальное вместе взятое. А в этих тестах вроде не сильно уже.

Кстати, пользуясь случаем, хочу спросить, вдруг кто-то знает, как в питоне можно узнать количество занятой текущим процессом памяти. По возможности кроссплатформенно как-нибудь. А то ставил в конец скрипта задержку и мерил по списку процессов.

Пример использования

import pymorphy
morph = pymorphy.get_morph('ru')

#слова должны быть в юникоде и ЗАГЛАВНЫМИ
info = morph.get_graminfo(u'Вася'.upper())

Так все-таки, зачем?

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

Напоследок

ссылка: https://bitbucket.org/kmike/pymorphy/

Лицензия - MIT.

Замечания, предложения, вопросы по делу - приветствуются. Если интересно - подключайтесь к разработке.

Warning

Сведения в этой статье могли устареть. Если планируете что-то использовать на практике, всегда используйте актуальную документацию по pymorphy.

Note

Статью сначала написал на хабр, там есть интересные комментарии: http://habrahabr.ru/blogs/python/49421/