Приложение в твоем смартфоне
Приложение в твоем смартфоне
Приложение в твоем смартфоне
Приложение в твоем смартфоне
18 января 2009 в 07:21

Кузявые ли бутявки, т.е. пишем морфологический анализатор на 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 для русского языка. Поэтому искать можно среди комбинаций
<префикс>+<лемма>+<окончание>, объединив в уме список приставок и префиксов, а затем выполнив небольшую проверочку.

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

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

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

*Еще был вариант — составить сразу словарь всех возможных слов вида <лемма>+<окончание>, получалось в итоге где-то миллионов 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_shelve_morph('ru')
#слова должны быть в юникоде и ЗАГЛАВНЫМИ
info = morph.get_graminfo(unicode('Вася').upper())


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


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

В поставке


pymorphy.py — сама библиотека
shelve_addons.py — наследники от shelf, может кому пригодится
encode_dicts.py — утилита, которая преобразовывает словари из формата AOT в форматы pymorphy. Без параметров, работает долго, ест метров 200 памяти, запускается 1 раз. Сконвертированные словари не распространяю из-за возможной бинарной несовместимости и большого объема.
test.py — юнит-тесты для pymorphy
example.py — небольшой пример и тексты с теми 995 словами
dicts/src — папка с исходными словарями, скачанными с aot.ru
dicts/converted — папка, куда encode_dicts.py будет складывать сконвертированные словари

Напоследок


ссылка:

bitbucket.org/kmike/pymorphy/

Лицензия — MIT.

проверял только под Python 2.5.

Замечания, предложения, вопросы по делу — приветствуются. Если интересно — подключайтесь к разработке.
+103
9920
240
kmike 156,5 G+

комментарии (41)

+5
Alaunquirie, #
Интересная статья, спасибо. Порадовал простой и логичный подход, с которым отнеслись к делу, и получили простую функциональность, в принципе, простыми методами.

It's just simple working )
0
Kron0S, #
а что за проект, если не секрет?
0
kmike, #
tr-tr.ru/
но там только экспортированный из fireworks набросок дизайна)
надеюсь, что подробнее расскажу попозже, когда придет время.
0
drJonnie, #
как в питоне можно узнать количество занятой текущим процессом памяти. По возможности кроссплатформенно как-нибудь.

Кросплатформенно никак. Пример кода под unix можно посмотреть в Measurement techniques в Efficient String Concatenation in Python.
0
kmike, #
Спасибо, примерно то, что надо.
+2
Irokez, #
делал аналогичное, даже послал в проект, они его загрузили к себе: www.aot.ru/download.php (в конце страницы: Alexander Pak's Morphology)
для питона есть очень мощная библиотека для обработки естественного языка: NLTK — www.nltk.org/
0
kmike, #
Ваш пример меня вдохновил, Вы, можно сказать, первопроходец в этом деле) Однозначно в карму +.
Но писал с нуля, т.к. мне так было проще.
А NLTK — это, насколько мне известно, только английский язык, был интересен именно русский.

0
Irokez, #
спасибо :)
По поводу NTLK — по-моему, если в него загрузить грамматику и словари для русского языка, то можно работать и с русским. Другое дело, что для русского нет нормальных словарей, и АОТ — действительно, наиболее развитый открытый источник.
0
kmike, #
Насчет NTLK мне показалось, что там не совсем так. В ней куча примочек для синтаксиса, статистики и анализа текста, но, что касается именно морфологии, максимум, что я увидел — стеммер Портера, с некими планами добавления Snowball. Думаю, просто для английского языка это не самая актуальная задача, у них и стеммеры работают более-менее нормально для большого круга задач.
0
Irokez, #
Лемматизацию, к примеру, можно выполнить через интерфейс к WordNet базе, там для каждой словоформы хранится лемма. Проблема опять таки в словаре, проект русского ворднета — project.phil.pu.ru/RussNet/ либо умер либо очень медленно развивается.
0
kmike, #
Спасибо, познавательно.
+1
Iskin, #
Отличная статья — куча важной информации.
+4
Smerig, #
Бутявки не кузявые, от бутявок дудонятся
+2
kzn, #
Спасибо, очень интересная статья!

С морфологическим анализом есть несколько тонкостей:
1. Неявно присутствует шаг нормализации текста. — Что считать словом и т.д.
2. У Вас м.а. основан на словарях (и в общем-то это правильно), и следовательно, качество м.а. зависит от словаря.
3. Сам по себе анализ слова — не такая сложная вещь. Гораздо сложнее тонкости вида анализа аббревиатур, сложных слов вроде автошкола или бетономешалка(в зависимости от словарей это одно или два слова), а так же проверка корректности вариантов разборов.

Ну и для хранения словарей намного эффективнее использовать DAWG(directed acyclic word graph), ну или если лень писать, то trie. 150M для морфологии — это черезчур :)
0
kmike, #
Ага, тут неявно подразумевается еще какой-то код, который разберет текст на слова. И что при разборе он вполне может выудить еще часть информации, например, из того, где стоит это слово (например, сразу после точки) и какие в нем буквы — первая заглавная, все заглавные или все строчные.
Тоже думал, что вместо хэшей деревья/графы какого-то рода будут лучше (за наводку на DAWG и trie спасибо, даже, скорее всего, постараюсь прикрутить, как время будет). Просто изначально была позиция делать все максимально просто и «тупо», если результат не будет устраивать, включать голову. Поэтому и на словообразование «забил», оставив такие слова на растерзание предсказателю по префиксу (авто-школа, хотя тут пример не совсем правильный, слово в словаре). Тем более что словообразования ни в lemmatizer, ни в phpmorphy тоже нет, выезжают на словаре (насколько я знаю).

А вот с проверкой корректности и правда что-нибудь придумать бы, «глазами» можно многого не увидеть. Пока вот решил просто попробовать увеличить число «глаз», выложив тут это все хозяйство.
+2
AChaplygin, #
Респект. Ход мыслей отличный. Красиво :) И «Пуськи бятые» очень порадовали. :)
НЛО прилетело и опубликовало эту надпись здесь
+2
Chikiro, #
>Из текста предсказатель не справился с именем собственным Калуша, с «Калушата»(они стали мужиками «Калуш» и «Калушат»)
«калушата» — это не имя собственное, это «калушонок» во множественном числе, слово образовано от «Калуша», с помощью "-онок" (не помню точно, вся ли эта часть суффикс), во множественном числе превращается в «калушата». (можно сравнить: «зайчонок — зайчата»). А имена собственные всегда с большой буквы пишутся.

«зюмо» — это наречие (сравните с «далеко», «высоко», «хорошо»), а удвоение для усиления используется.

Спасибо за интересную статью, хочу заниматься чем-нибудь на стыке программирования и лингвистики, но пока серьезных знаний ни в первом, ни во втором не хватает.
0
vinni, #
А какое количество слов можно разобрать с помощью словаря?
0
kmike, #
Там около 140тыс. лемм, 2700 парадигм слов, 170тыс. (насколько я помню) правил образования слов.
В итоге выходит около 5 миллионов уникальных слов в словаре.
0
DaHacka, #
очень интересная и сложная предметная область, учитывая многообразие русского языка :)
0
niksite, #
О, спасибо. А то я планировал lemmatizer`ом пользоваться из питоньих программ. А тут, оказывается, уже нативная реализация готова.
0
kmike, #
у lemmatizer'а свои плюсы: скорость, надежность.
у pymorphy — простота, расширяемость
Если для Ваших нужд подойдет pymorphy, то это здорово.
0
niksite, #
По hg.assembla.com/pymorphy отдаётся HTML`ка с Content-Type: text/plain. Это не хорошо.
На главной странице (http://www.assembla.com/wiki/show/pymorphy ?) прошу указать команду для установки последней версии (hg fetch… ?).
+1
kmike, #
hg clone http://hg.assembla.com/pymorphy

Написал там в вики про установку.
0
kmike, #
с text/plain — какой-то баг ассемблы.
По идее, у hg веб-интерфейс с html-страничкой, на которой можно посмотреть историю, отдельные изменения — и скачать все целиком в архиве.
0
michurin, #
Спасибо, очень интересно.
Я знал ребят, которые знаимались такими вещами, они широко использовали словарь Лебедева scon155.phys.msu.su/eng/lebedev.html, там есть файл с правилами образования совоформ russian.aff, может быть он и вам пригодится.
+1
Lesanol, #
Может-быть кому-то пригодится содранный с интернета ботом словарик для имён.
Старался, вроде там довольно много понабралось.
Кому понравится — отпишитесь. :)
(UTF-8)
slil.ru/26554601
0
peterdemin, #
Смешной. Нашел Петруслава, а Петр не нашел…
0
Lesanol, #
Баги. Баги, баги, баги… Спасибо, будет исправлено!
+1
peterdemin, #
В encode_dicts.py пришлось заменить одну функию:

def convert_file(in_file, out_file, in_charset, out_charset):
text = codecs.open(in_file, «r», in_charset).read()
codecs.open(out_file, «w», out_charset ).write(text)
0
kmike, #
Cпасибо, так и правда лучше, закоммитил.
P.S. репозиторий открыт на запись для всех, кто зарегистрирован на assembla.
+1
peterdemin, #
Постараюсь помочь с развитием проекта. Но как мне видится, это скорее будет форк, заточенный под мои нужды.
0
joedm, #
Забыли сказать, что Бутявку придумала Людмила Петрушевская, в далёком 1984-м году.
0
VlK, #
Вот мне интересно… А в каких-нибудь больших опенсорсных проектах использовались серьезные анализаторы грамматики?

Скажем в OO.Org? Я не влезал никогда глубоко в эту тему; но вроде там только чисто орфографическая проверка слов по словарю в наличии, а более глубокой проверки как в Ms Office — нетуть. Или это я от жизни отстал?
0
Error_403_Forbidden, #
А здесь поддерживается буква Ё?
0
kmike, #
здесь не очень (просто заменяется на е), в github.com/kmike/pymorphy2 — полностью
0
javascript, #
mystem предлагает следующую тестовую строку:
«В мурелки шлепают пельсиски. В стакелках светится мычай.»
пельсиски — наречие

А я взял в качестве тест-кейсов русские скороговорки:
  • Карл у Клары украл кораллы, а Клара у Карла украла кларнет.
    кларнет — глагол
  • Курил турка трубку, клевала курка крупку: не кури, турка, трубки, не клюй, курка, крупки!
    клевала — существительное
    кури — существительное
    клюй — существительное
  • Наши поезда — самые поездатые поезда в мире, и никакие другие поезда не перепоездадят наши поезда по поездатости.
    поездатые — глагол

Почти круто, всегда можно немножко доработать :-)
+1
samodum, #
Кстати, наш морфологический анализатор данные тесты хорошо проходит:
samodum.ru/Morpho/Demo
+1
kmike, #
Не очень интересно: снятия неоднозначности нет; слова, записанные через дефис — не разбираете правильно («человек-акула», «скажи-ка»); не open-source; словари такие же неполные, как и везде («алешенька» — женский род), склонятора нет (видимо, временно?). Не представляю, кому может понадобиться «голый» морфологический разбор в виде сервиса.

Я, понятно, лицо заинтересованное, но в github.com/kmike/pymorphy2 и словари лучше, и предсказатель умнее, и open-source все.
0
samodum, #
Это первый уровень, морфологический. Неоднозначность здесь и не должна сниматься.
Она снимается на последующих уровнях — на синтаксическом и семантическом.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.