«Стеммер». Морфологический анализ для небольших поисковых систем

АНДРЕЙ КОВАЛЕНКО

«Стеммер»

Морфологический анализ для небольших поисковых систем

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

Поисковые и не только поисковые системы Интернет столь популярны сегодня, что люди проводят часы, обсуждая достоинства и недостатки той или иной, алгоритмы и программы для поиска полнотекстовой информации на тех или иных носителях. И все это время не утихают горячие споры «профи» поиска и «ленивых пользователей». Первые – сторонники чисто «механических» машин, поисковых систем, которые вычисляют строгие логические запросы и поддерживают усечение слова справа «звёздочкой»; они убеждены, что лучше всяких алгоритмов сформулируют, что же им нужно найти. Другие – наоборот, стараются отдать на откуп алгоритмам поисковика все магические преобразования исходного запроса и не задумываться о том, что же там происходит внутри.

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

Один достаточно иллюстративный диалог произошел на выставке SofTool в 1995 году. Компания «Агама», где я в тот момент работал, представляла одноименную систему поиска информации, размещенной на локальных дисках компьютера. Надо сказать, эта поисковая система уже тогда, несмотря на убогость DOS, под управлением коего она работала, уже делала полноценный словарный морфологический анализ обрабатываемых текстов и поисковых запросов, то есть умела искать с учетом всех форм русских слов. И вот одна дама, протестировав систему и побеседовав о морфологической обработке текстов с господином Пархоменко, идеологом и руководителем проекта, воскликнула на весь зал: «Да ведь это никому не нужно! Я сама прекрасно все найду, дайте мне только оператор усечения!». На беду, оператор усечения, как и весь традиционный набор логических операторов, в языке запросов присутствовал. После получаса стучания по клавишам дама со словами: «Вы меня не убедили!», – покинула стенд.

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

Что же делать в такой ситуации? Есть два решения. Первое – не использовать лингвистических алгоритмов вообще, если это возможно. Второе – остановиться на стемминге, то есть на формальном выделении основы – стабильной, графически неизменной при склонении или спряжении, части слова.

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

Хуже обстоит дело со славянскими языками. Выделить правила, по которым можно отсечь часть слова справа, да так, чтобы не породить сильного шума, очень сложно, и построение такого набора правил сравнимо по трудоемкости с построением полноценного словарного морфологического анализатора, чем обычно и заканчиваются доведенные до логического завершения разработки в этой области. Приведем простой пример – слово кровать. До сих пор все программы стемминга для русского языка успешно и совершенно логично признавали это слово изменяющимся по модели глагола, выделяя или формальную основу «кр» или в лучше случае, «кров». Уважаемый читатель, мне кажется, по достоинству оценит такой глагол – «я крую/кроваю, он кровает/круёт».

Однако за истекший год в этом направлении были сделаны серьезные шаги. Мартин Портер (Martin Porter) сделал доступными свои наработки в области стемминга, наборы правил и инструменты для работы с ними, для открытого сетевого сообщества, опубликовав проект на SourceForge(http://snowball.sourceforge.net/).Проект представляет собой специализированный язык обработки строк, предназначенный для изготовления алгоритмов стемминга в информационном поиске. Довольно быстро проект стал расширяться, и сейчас доступны в исходных текстах стеммеры для английского, французского, испанского, португальского, итальянского, немецкого, датского, шведского и норвежского языков. Русский поначалу остался в стороне, однако недавно появилась поддержка и для него (http://snowball.sourceforge.net/russian/stemmer.html).

Тем не менее, по ряду причин, часть из которых обсуждалась выше, стеммер Snowball все равно далек от идеала. И основная причина заключается в том, что он базируется на обобщенных правилах, составленных людьми, в лучшем случае – лингвистами. А как известно, любое общее правило имеет исключения, приводящие в данном случае к неправильному выделению основы. Еще одно нарекание – это «убежденность алгоритма в собственной непогрешимости»: алгоритм всегда дает один-единственный вариант формальной основы слова, игнорируя все остальные по внутренним соображениям. Именно в силу указанных недостатков и было принято решение о разработке своего алгоритма и правил стемминга.

Отмечу сразу, что мыслей разрабатывать вручную правила усечения русских слов не было даже изначально, но было большое желание изготовить алгоритм, который учитывал бы и сочетаемость букв в слове на границе возможного усечения, и частотность такой модели словоизменения. Поэтому было принято решение строить правила стемминга автоматически, обрабатывая большие массивы русских текстов. Задача сильно облегчалась наличием русского морфологического анализатора, разработанного еще в 1994 году во время работы над проектом «Пропись 4.0». Анализатор этот работает и поныне в поисковых системах Апорт! (www.aport.ru),Рамблер (www.rambler.ru), (www.meta-ukraine.com), хотя и пережил несколько преобразований, в результате чего словарь уже придирчиво выверен, а код позволяет обрабатывать до 20 – 30 тысяч слов в секунду. Подробнее с этим анализатором и условиями его распространения можно ознакомиться на странице автора (linguist.nm.ru).

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

Далее была изготовлена программа обработки массивов полнотекстовой информации, которая, разбив текст на слова, выполняла обработку очередной потенциальной словоформы точным морфологическим анализатором; при этом неизвестные словарному анализатору строки игнорировались, что является допустимой погрешностью, поскольку, имея базу более 150,000 основ и распознавая более четырех миллионов различных форм русских слов, анализатор игнорирует менее одного процента встретившихся строк, которые по большей части оказываются либо орфографическими ошибками, либо аббревиатурами, либо экзотическими названиями или именами собственными. Для опознанных же словоформ выделялась их точная основа, то есть часть слова, остающаяся неизменной при склонении или спряжении; выделенное таким способом окончание вкупе с последними двумя символами формальной основы поступало в накопитель, который либо регистрировал новое правило, либо увеличивал вес уже существующего правила отщепления окончания.

По завершении работы сканера текстов получившийся массив данных был отранжирован в соответствии с убыванием вероятности встретить каждую из присутствующих моделей словоизменения, после чего модели, вероятность реализации которых составляла менее 10^-4, были отброшены как редкие и потенциально опасные, т. е. способные породить избыточный шум.

Результат – набор потенциальных окончаний с условиями на предшествующие символы – был инвертирован для удобства сканирования словоформ «справа налево» и представлен в виде таблицы переходов конечного автомата. Подробнее устройство таких таблиц описано в статье о словарном морфологическом анализаторе, доступной по адресу http://linguist.nm.ru/ling/rus/help.htm. Мы же лишь покажем на рисунке фрагмент такой таблицы, построенный для небольшого набора окончаний и условий на предшествующие символы основы. В качестве примера выберем уже упоминавшиеся формально построенные правила: (-ар-)-ями, (-ор-)-ями, добавив к ним для наглядности еще два – (-ск-)-и и (-сн-)-а, построенные, например, по словоформам диски и весна.

Далее был разработан переносимый программный код на языке C, обеспечивающий сканирование подаваемых на вход форм слов на полученных таблицах переходов. Особо следует отметить, что код этот не берет на себя ответственность за выбор конкретного способа усечения, но лишь строит все допустимые варианты выделения формальной основы. Так, для словоформы начинающихся анализатор выделит формальные основы длиной 6, 8 и 10 символов, что соответствует глаголу начина-ть, причастию начинающ-ий и возвратной форме – начанающий-ся, то есть выделит псевдоморфемы, участвующие в образовании этого слова. Программа-клиент, например поисковая машина, вправе либо самостоятельно принять решение о выборе того или иного варианта усечения, либо запомнить все построенные варианты, что обеспечит максимальную полноту поиска. С другой стороны, для многострадального слова кровать обученный таким образом алгоритм выделит лишь одну формальную основу – шестибуквенную последовательность кроват-ь, что полностью соответствует истине. В ряде ситуаций анализатор принимает решение о невозможности какого-либо усечения по данной последовательности, как, например, в случае слова компьютер, что также полностью соответствует действительности.

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

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

Особое внимание пришлось уделить поддержке различных кодовых страниц и возможной капитализации – начертанию слов в верхнем регистре. Действительно, при всей привлекательности кодировки 1251 Windows Cyrillic и удобстве работы с ней, она не является ни единственной, ни даже самой популярной. Преобразовывать же строку из иных кодировок в желаемую перед анализом весьма и весьма дорого по меркам «скорострельных» алгоритмов. Для обеспечения совместимости анализатора с текстами в различных кодировках предусмотрена возможность его настройки передачей дополнительного параметра – таблицы преобразования кодов символов из произвольной кодировки в нижний регистр кодировки 1251 размерностью 256 байт. Если этот параметр не задан, то по умолчанию используется встроенная таблица преобразования символов верхнего регистра кодовой страницы Windows Cyrillic в символы нижнего регистра.

Хочется отметить, что весной 2002 года в лаборатории общей и компьютерной лексикографии кафедры русского языка Московского Государственного университета было проведено сравнительное тестирование трех программ русского стемминга: Snowball, описываемого алгоритма и стеммера, разработанного там же под руководством докторов филологических наук А. А. Поликарпова и О. В. Кукушкиной. По результатам тестирования описываемый стеммер показал наиболее корректные в лингвистическом отношении результаты при максимальной полноте и минимальном шуме, то есть количестве неверно выделенных основ.

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

Представленный продукт доступен в исходных текстах и может использоваться в свободной форме с условием ссылки на источник. Архив можно загрузить по адресу http://linguist.nm.ru/stemka/stemka.tar.gz.