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

Английский, с его весьма условным делением на части речи и практически отсутствующим склонением/спряжением, вполне прилично описывается простыми моделями выделения неизменяемой основы слова (стеммерами) с небольшим словариком исключений буквально на сотню слов. Слова немецкого прекрасно бьются на части по формальным признакам, словарю корней и принципу «максимума суммы квадратов длин». Системы окончаний других европейских языков также достаточно просты.

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

Для решения задачи отождествления разных форм существует некоторое количество реализаций морфологических анализаторов русского. Но почти все они — во всяком случае, заслуживающие внимания — растут из одного корня...

(По материалам внутреннего семинара компании МойОфис)

Привет, Хабр! Я Андрей Коваленко (Keva), в МойОфис возглавляю группу прикладной лингвистики и поисковых решений. Мы создаем корпоративную поисковую систему, извлекаем информацию, обобщаем, конкретизируем, анализируем и синтезируем тексты.

Но сегодня хочу поговорить не про сам поиск, а про его, без преувеличения, самый важный компонент — морфологический анализатор. Их существует много, реализованных на разных языках, в разные годы и разными авторами. Даже промышленного качества их как минимум штук пять, с теми или иными достоинствами, в зависимости от задачи, для которой разрабатывались.

В общем случае морфологический анализатор умеет:

• отождествлять разные грамматические формы слов с некоторой лексической единицей, то есть сводить воедино причастие <вобравшими> и личную форму глагола <вберём> (вобрать) — этого достаточно для простейшего поиска на обратном индексе;

• сообщать грамматические характеристики, часто множественные, той формы слова, что подали ему на анализ;

• синтезировать нужную форму слова по лексеме и грамматической характеристике.

Промышленные анализаторы ещё и умеют делать это на минимальных вычислительных ресурсах и с приличной производительностью — сотни тысяч слов в секунду здесь оказываются нижней границей приемлемости.

Но все существующие анализаторы объединяет одно: источник данных, он же — корень, из которого они выросли. И это — Великий Словарь Зализняка.

В начале 70-х годов прошлого столетия — я тогда только родился, большинства читателей этого текста не было на свете, до появления «персоналок» было ещё лет двадцать, Томпсон и Ритчи только-только разработали ОС Unix и язык C, а «мейнфреймы» — большие вычислительные машины — стояли в машинных залах. Доступ к ним был через администратора, не для всех. А способом общения были колоды перфокарт, листинги трансляции и распечатанные рулоны выдачи.

И вот тогда Андрей Анатольевич Зализняк, выдающийся русский лингвист и признанный гений столетия, человек, выучивший за две недели венгерский просто для выступления на конференции, придумал и реализовал с помощью и участием своих студентов подход, позволивший формализовать всю изменчивость слов русского языка и отнести все слова к детально описанным классам словоизменения. Все четыре с лишним миллиона словоформ на тот момент он свёл к ста тысячам строчек словаря.

Суть метода состоит в том, что слова были упорядочены в обратном лексикографическом порядке — то есть с прочтением не слева направо, а справа налево. Вот так:

В результате слова, заканчивающиеся одинаково, оказались рядом и образовали, за редким исключением, гнёзда или, как сейчас принято говорить, кластеры слов, склоняющихся/спрягающихся одинаково. Действительно, если сравнить наборы форм двух ближайших соседей, мы обнаружим совершенно явное сходство:

После каждого слова следует словарная статья со следующими обозначениями:

Для их понимания обратимся к первому разделу словаря — «Грамматическим сведениям». Здесь <м> — «неодушевлённое существительное мужского рода», <1> — первый из семи, по классификации словаря, тип субстантивного склонения, а «a» — схема ударения: оно всегда падает на основу слова.

Всего рассматривается для существительных шесть схем ударения — на основу (a), на окончание (b) и четыре схемы плавающего, когда в одних формах оно падает на основу, а в других — на окончание. Например, у слова <час м 1c> в единственном числе ударение падает всегда на основу (ча́с, ча́са, ча́су, ча́сом, о ча́се), а во множественном — на окончание (часы́, часо́в, часа́м, часа́ми, о часа́х). Схема ударения также влияет на правописание форм слова.

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

Иногда в индексах также встречаются пометы. Рассматривать их все мы не будем — для интересующихся они подробно описаны в «Грамматических сведениях». Остановимся подробнее только на <*>. Она означает, что в основе слова происходит чередование или присутствует беглая гласная. Например, слова <пиксел м 1a> и <вымысел м 1a> имеют одинаковые наборы окончаний, однако у второго из них в косвенных формах гласная <е> в графической основе слова исчезает (пиксел — пиксела, вымысел — вымысла).

Морфологические анализаторы

Первые были сделаны ещё на мейнфреймах. Например, в «ИнформЭлектро» этим занималась группа Пархоменко (Травкина, Назарова, Лахути).

Много сил тратилось даже не на описание модели словоизменения, а на технологическую обвязку, позволяющую работать с достаточно объёмным по тем временам словарём в ограниченной оперативной памяти. Налёт компактности был и на самих моделях — например, для слов с чередованием в графической основе генерировалось несколько основ формальных, а к таблицам окончаний применялись разрешающие (или запрещающие) битовые маски, «включая» только допустимые для такой основы окончания. Это позволяло работать быстрее при анализе, притормаживало при синтезе, однако давало возможность сегментировать словарь на куски допустимого размера.

Видимо, первым коммерческим продуктом нарождающейся эпохи частного предпринимательства, построенным на модели Зализняка, был ОРФО Игоря Ашманова (@Ashmanov) — работавший ещё под DOS орфографический корректор, висевший в памяти резидентно и позволявший интегрироваться с популярными текстовыми процессорами, в том числе Microsoft Word. Модель словоизменения использовалась подобная описанной выше, но изюминками были сильно пополненный современной лексикой словарь — он и по сей день остаётся наиболее вычитанным при хорошей полноте и продолжает использоваться, но уже в Microsoft Word и иных продуктах, — и линкер Саши Михайлова. Дело в том, что на всё про всё на персоналках того времени было 640К памяти, и резидентная программа могла занимать только небольшой её кусочек, оставляя остальное для пользовательских приложений. Вот в этот-то кусочек и загружались попеременно разные сегменты кода системы и фрагменты морфологического словаря!

Были и другие системы контроля орфографии: Presto!, так и оставшийся под DOS; интегрированный с «Лексиконом» «Ортодок» (надеюсь, я правильно написал его название).

Свой libmorph/rus я тоже изначально сделал как систему контроля орфографии. Тогда я работал в фирме Агама, и мы обошли всех на повороте, выпустив «Пропись», первый русский спелл-чекер для Windows, интегрировавшийся со многими популярными офисными приложениями того времени. Но в голове уже бродили мысли о поисковых системах, а доступных ресурсов стало заметно больше. Так что я заложил в архитектуру модуля всю доступную грамматическую информацию и перенумеровал лексемы, что оказалось очень удачной идеей: при индексировании можно было запоминать не строку, а её номер, число. Например, «ягодица» раз и навсегда получила номер 71997 :)

В версии для Win16, получившей название linguist.dll, словарь был разбит на страницы, представленные ресурсами Windows, и это был самый быстрый на тот момент морфологический анализатор. Более поздняя версия, уже тридцатидвухбитная, ling32bi.dll, использовала словарь-монолит и стала, в силу организации словаря в виде базисного дерева, ещё быстрее, показывая на 386-х машинах вплоть до тридцати тысяч слов в секунду в режиме лемматизации. Дальнейшее развитие было лишь в сторону пополнения словаря и оптимизации работы с ним, так что ко временам Рамблера — я туда пришёл в 2000 году — уже был libmorphrus со своей скорострельностью в сотню тысяч в секунду и выше, перечислением лексем, алгоритмами приложения шаблонов (*, ?) и выборками по ним. Собственно, таким он и остаётся сегодня, разве что я периодически подбрасываю туда сотню-другую новых лексем, да сделал вероятностный анализатор для неизвестных слов. Скоро опубликую там же, как чуток свободного времени появится — у меня сейчас очень важный проект по имени Мичко Андреевич в работе :)

Примерно тогда же, когда я взялся строить поисковик Апорт!, блистательный Илья Сегалович уже выпустил «Цифровую Библию», а спустя пару лет вместе с Аркадием Воложем и Еленой Колмановской запустил Яndex. Интересно, что для организации двоичного словаря там использовался диаметрально противоположный подход: вместо сопоставления слова со словарём слева направо, с максимальным усечением возможных гипотез и проверками только отдельных таблиц окончаний, слова проверялись справа налево, отщеплялись окончания, после чего гипотеза об основе слова выбрасывалась в разреженную хэш-таблицу.

Ещё про Зализняка

Татьяна Михайловна Николаева, доктор филологических наук и однокурсница Андрея Анатольевича, вспоминала, как он в самолёте открыл учебник венгерского языка, через пару дней уже освоил на бытовом уровне, а к концу поездки, в Будапеште, уже без проблем общался с коллегами.

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

Но сам придавал наибольшее значение другой своей работе и увлечению одновременно — поиску, расшифровке и переводу берестяных грамот, найденных на археологических раскопках в Новгородской губернии.

Заключительное слово

На этом можно было бы и завершить, но хочется рассказать ещё об одной книге, где концентрация и качество подаваемого материала настолько высоки, что это точно круче даже двухтомника Фихтенгольца по матанализу. Но только в другой предметной области. Существуют такие выдающиеся методические пособия, что любые попытки их «исправить и улучшить» приводят только к заметной порче материала.

Кто заканчивал естественно-научные факультеты Московского Университета, наверняка помнят выпущенную Издательством Физфака и отпечатанную на ротапринте тоненькую методичку на желтоватой бумаге — «Механика и электричество» Склянкина и Муриной, где были изложены все темы двухлетнего курса физики настолько доходчиво, что книжку доставали через знакомых студенты других учебных заведений, и настолько компактно, что она умещалась чуть согнутой во внутреннем кармане куртки.

Подобный учебник есть и по русскому языку. Того же формата и толщины, но только в жёсткой обложке. Это книга Дитмара Эльяшевича Розенталя «Русский язык. Орфография и пунктуация». Исчерпывающий материал, компактно изложенный и по прочтении автоматически снижающий количество ошибок в текстах в разы. А при вдумчивом — делающий пишущего человека практически абсолютно грамотным, с точностью до очепяток.

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