Гибридная реализация русской морфологии.

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

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

comments -> comment
using -> use
stemming -> stem
received -> receiv
develops -> develop.

Хотя Snawball и поддерживает русский язык, но его применение не дает достаточно качественных результатов. Вот пример двух словоформы одного и того же слова для которых усечение происходить по разному:

отзыв -> отз
отзывы -> отзыв

Другой подход - хранить все пары (слово, нормальная форма). Минусы этого здесь очевидны. Если встречается не знакомое слово, то алгоритм для него не сработает. Другой минус вытекает из того, что современный словарь русского языка содержит больше полуторамиллиона словоформ. Все их нужно хранить и быстро осуществлять поиск среди них. Можно построить конечный автомат, для сокращения объема требуемой памяти и повышения скорости работы. Алгоритм для построения такого автомата приведен в статье [1]. Реализация на С++ доступна на сайте aot.ru. Данный алгоритм довольно сложный в реализации.

Можно использовать гибридный вариант стемминга и словарного подхода. В большинстве случаях нам будет достаточно знания нескольких последних букв слова для правильного определения его нормальной формы. Таким образом мы заменим пары (слово, нормальная форма) на (окончание слова, окончание нормально формы). В качестве окончания слова будем брать 7 последних букв слова. Тем самым решилась проблема отсутствия незнакомых слов в словаре. Ясно, что данный результат будет хуже чем словарный, но гораздо лучше чем результат стеммера. Для слова не более 7 букв слов алгоритм даст точный ответ. Он так же применяется в реализации морфологии от aot.ru в качестве эвристики для незнакомых слов. Отличие реализации в том, так же строиться конечный автомат как и для слов из словаря.

Рассмотрим вопрос о его сложности и требуемого объема памяти. В русском алфавите 33 буквы плюс в нужно еще учитывать, что в словах может встречаться дефис. Таким образом одна буква в слове кодируется числом от 0 до 33 и 64-битный тип данных (например long в java) может содержать в себе информацию об 7-12 буках. Этого вполне достаточно для наших целей. Для эксперимента возьмем словарь с сайта проекта aot.ru, распространяемый по лицензии LGPL 2.0. Он нам даст 750 тысяч уникальных пар (окончание слова, окончание нормально формы). Некоторые из пар будут иметь одинаковые окончания слов для которых требуется определить нормальную форму. Будем оставлять только одну — которая чаще встречается и подходит для более распространенных слов в русском языке. Так им образом у нас останется около 690 тысяч пар. В частности для более чем 600 тысячах случаях нормальная форма будет определять однозначно.

Нетрудно подсчитать, что данные необходимы для работы алгоритма будут занимать около 10.6 мегабайт. Нужного окончания можно будет найти с помощью бинарного поиска. (нужно около найти 20 сравнений). Длясравнения в алгоритме от aot.ru размер автомата без морфологической информации около 5 мегабайт. Для реализации эвристики по концу слова нужен еще один автомат, к сожалению его размер не приведен. Таким образом размер памяти сопоставим, а данная реализация дает не значительно худший результат при меньших затратах.

Реализация данного подхода была воплощена на java, так же был сделан Analayzer русского языка
для поискового фрейморка lucene. Она распространяется под apache 2.0 лицензии.

[1] Jan Daciuk, Bruce Watson, and Richard Watson, Incremental Construction of Minimal Acyclic Finite State Automata and Transducers, proceedings of Finite State Methods in Natural Language Processing, pp. 48-56, Bilkent University, Ankara, Turkey, June 29 - July 1, 1998.