Для представления автоматических правил усечения слов была выбрана модель хранения возможного окончания с двумя предшествующими буквами неизменяемой части слова. Так, например, словоформа
словарями порождает правило, разрешающее отщепление окончания
-ями при условии, что ему предшествует последовательность
-ар-. Аналогично, встретив словоформу
морями, мы породим правило о возможном
отщеплении того же окончания (
-ями) при условии, что оно встретилось после фрагмента
-ор-. Далее была изготовлена программа обработки массивов полнотекстовой информации, которая, разбив текст на слова, выполняла обработку очередной потенциальной словоформы точным морфологическим анализатором; при этом неизвестные словарному анализатору строки игнорировались, что является допустимой погрешностью, поскольку, имея базу более 150,000 основ и распознавая более четырех миллионов различных форм русских слов, анализатор игнорирует менее одного процента встретившихся строк, которые по большей части оказываются либо орфографическими ошибками, либо аббревиатурами, либо экзотическими названиями или именами собственными. Для опознанных же словоформ выделялась их точная основа, то есть часть слова, остающаяся неизменной при склонении или спряжении; выделенное таким способом окончание вкупе с последними двумя символами формальной основы поступало в накопитель, который либо регистрировал новое правило, либо увеличивал вес уже существующего правила отщепления окончания.
По завершении работы сканера текстов получившийся массив данных был отранжирован в соответствии с убыванием вероятности встретить каждую из присутствующих моделей словоизменения, после чего модели, вероятность реализации которых составляла менее одной десятитысячной, были отброшены как редкие и потенциально опасные, т. е. способные породить избыточный шум.
Результат - набор потенциальных окончаний с условиями на предшествующие символы - был инвертирован для удобства сканирования словоформ "справа налево" и представлен в виде таблицы переходов конечного автомата. Подробнее устройство таких таблиц описано в статье о
словарном морфологическом анализаторе. Далее был разработан переносимый программный код на языке C, обеспечивающий сканирование подаваемых на вход форм слов на полученных таблицах переходов. Особо следует отметить, что код этот не берет на себя ответственность за выбор конкретного способа усечения, но лишь строит все допустимые варианты выделения формальной основы. Так, для словоформы
начинающихся анализатор выделит формальные основы длиной 6, 8 и 10 символов, что соответствует глаголу
начина-ть, причастию
начинающ-ий и возвратной форме -
начанающий-ся, то есть выделит псевдоморфемы, участвующие в образовании этого слова. Программа-клиент, например поисковая машина, вправе либо самостоятельно принять решение о выборе того или иного варианта усечения, либо запомнить все построенные варианты, что обеспечит максимальную полноту поиска. С другой стороны, для многострадального слова
кровать обученный таким образом алгоритм выделит лишь одну формальную основу - шестибуквенную последовательность
кроват-ь, что полностью соответствует истине. В ряде ситуаций анализатор принимает решение о невозможности какого-либо усечения по данной последовательности, как, например, в случае слова
компьютер, что также полностью соответствует действительности.
По ходу тестирования и отладки построенной технологии было введено дополнительное правило, ограничивающее свободу алгоритма. Суть правила состоит в том, что формальная основа слова должна содержать хотя бы одну гласную, иначе возможно построение весьма некорректных основ, как, например, усечение слова
спам до основы
сп, что, как известно, является распространенной аббревиатурой словосочетания "совместное предприятие".
Интересно, что большинство стеммеров, в том числе и используемый в поисковой системе
Яndex для обработки неизвестных слов, грешат в подобных ситуациях, в чем несложно убедиться, дав соответствующий запрос.
Для обеспечения должной производительности анализатор не строит строк, а лишь возвращает набор возможных длин формальных основ, которые можно выделить из строки. Инициализация модуля также не требуется, так как все таблицы переходов представлены статическими данными.
Особое внимание пришлось уделить поддержке различных кодовых страниц и возможной капитализации - начертанию слов в верхнем регистре. Действительно, при всей привлекательности кодировки 1251 Windows Cyrillic и удобстве работы с ней, она не является ни единственной, ни даже самой популярной. Преобразовывать же строку из иных кодировок в желаемую перед анализом весьма и весьма дорого по меркам "скорострельных" алгоритмов. Для обеспечения совместимости анализатора с текстами в различных кодировках предусмотрена возможность его настройки передачей дополнительного параметра - таблицы преобразования кодов символов из произвольной кодировки в нижний регистр кодировки 1251 размерностью 256 байт. Если этот параметр не задан, то по умолчанию используется встроенная таблица преобразования символов верхнего регистра кодовой страницы Windows Cyrillic в символы нижнего регистра.
Хочется отметить, что весной 2002 года в лаборатории общей и компьютерной лексикографии кафедры русского языка Московского Государственного университета было проведено сравнительное тестирование трех программ русского стемминга: Snowball, описываемого алгоритма и стеммера, разработанного там же под руководством докторов филологических наук А. А. Поликарпова и О. В. Кукушкиной. По результатам тестирования описываемый стеммер показал наиболее корректные в лингвистическом отношении результаты при максимальной полноте и минимальном шуме, то есть количестве неверно выделенных основ.
Позже описанным способом был разработан также словарь стемминга украинского языка, который вместе с русским успешно применяется для анализа неизвестных слов в украинской поисковой системе
www.meta-ukraine.com, а также изготовлена программа, позволяющая автоматически строить таблицы стемминга для других языков из словарей ISpell, доступных в сети Интернет. Однако следует оговориться, что в последнем случае качество получаемого словаря напрямую зависит от качества используемых материалов, которое чаще всего весьма низко.
Представленный продукт доступен в исходных текстах и может использоваться в свободной форме с условием ссылки на источник. Архив можно загрузить
здесь.