Кузяві чи бутявки, т
Морфологічний аналізатор для української мови – це щось химерне? Програма, яка наводить слово до початкової форми, визначає відмінок, знаходить словоформи - незрозуміло, як і підступитися? А насправді все не так і складно. У статті — як писав аналог 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: [rule_id]>, тобто. ключ – це лема, а значення – список номерів допустимих парадигм. А далі поїхали – спочатку вважаємо, що лема – цеперша буква слова, потім, що це 2 перші букви і т.д. По лемі намагаємось отримати список парадигм. Якщо отримали, то в кожній допустимій парадигмі пробігаємо за всіма правилами і дивимося, чи вийде наше слово, якщо правило застосувати. Виходить - додаємо його до списку знайдених форм.
* Ще був варіант - скласти одночасно словник всіх можливих слів виду +, виходило в результаті десь мільйонів 5 слів, не так і багато, але варіант, втім, мені не дуже сподобався.
Дописуємо морфологічний аналізатор
По суті все готово, ми написали морфологічний аналізатор, за винятком деяких деталей, які зайняли у мене 90% часу)
Деталь перша
Якщо згадати приклад, який був на початку, про «ЛЮДЕЙ» — «ЛЮДИНА», то стане зрозуміло, що є слова, у яких незмінна частина відсутня. І де тоді шукати форми цих слів – незрозуміло. Пробував шукати серед усіх закінчень (так само, як і серед лем), адже для таких слів і «ЛЮДЕЙ», і «ЛЮДИНУ» у словнику зберігатимуться як закінчення. Для деяких слів працювало, для деяких видавало крім правильного результату ще й купу сміття. У результаті після довгих експериментів з'ясувалося, що є в словнику така хитра магічна лема "#", яка і відповідає всім порожнім лемам. Ура, завдання вирішене, шукаємо щоразу ще й там.
Деталь друга
Добре було б мати «провісник», який зміг би працювати і зі словами, яких немає у словнику. Це не лише невідомі науці рідкісні слова, а й просто описки, наприклад.
Тут є 2 нескладні, але цілком працюючі підходи: 1. Якщо слова відрізняються лише тим, що до одного з них приписано щось попереду, то, швидше за все, вони будуть схилятися однаково 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): ('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 складатиме конвертовані словники
Насамкінець
перевіряв лише під Python 2.5.
Зауваження, пропозиції, питання у справі вітаються. Якщо цікаво, підключайтеся до розробки.
А у нас тут можна отримати грант на тестовий період Яндекс.Хмари. Варто лише у полі «секретний пароль» запровадити «Хабр»