Стемминг

Сте́мминг (англ. stemming — находить происхождение) — это процесс нахождения основы слова для заданного исходного слова. Основа слова не обязательно совпадает с морфологическим корнем слова.

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

Конкретный способ решения задачи поиска основы слов называется алгоритм стемминга, а конкретная реализация — стеммер➤.

Первый опубликованный стеммер был написан Джули Бет Ловинс в 1968 году^[1]. Эта статья значима ранней датой публикации и оказала большое влияние на более поздние работы в данной области.

Позже стеммер был написан Мартином Портером и опубликован в 1980 году. Этот стеммер очень широко использовался и стал де-факто стандартным алгоритмом для текстов на английском языке. Доктор Портер получил премию Стрикса в 2000 году за работы по стеммингу и поиску информации.

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

Существует несколько типов алгоритмов стемминга, которые различаются по отношению производительности, точности, а также как преодолеваются определённые проблемы стемминга.

Простой стеммер ищет флективную форму в таблице поиска. Преимущества этого подхода заключается в его простоте, скорости, а также лёгкости обработки исключений. К недостаткам можно отнести то, что все флективные формы должны быть явно перечислены в таблице: новые или незнакомые слова не будут обрабатываться, даже если они являются правильными (например, iPads ~ iPad), а также проблемой является то, что таблица поиска может быть очень большой. Для языков с простой морфологией наподобие английского размеры таблиц небольшие, но для сильно флективных языков (например, турецкого) таблица может иметь сотни возможных флективных форм для каждого корня.

Таблицы поиска, используемые в стеммерах, как правило, генерируются в полуавтоматическом режиме. Например, для английского слова «run» автоматически будут сгенерированы формы «running», «runs», «runned» и «runly». Последние две формы являются допустимыми конструкциями, но они вряд ли появятся в обычном тексте на английском языке.

Алгоритм поиска может использовать предварительную частеречную разметку, чтобы избежать такой разновидности ошибки лемматизации, когда разные слова относят к одной лемме (overstemming)^[2].

Алгоритмы усечения окончаний не используют справочной таблицы, которая состоит из флективных форм и отношений корня и формы. Вместо этого, как правило, хранится меньший список «правил», который используется алгоритмами, учитывая форму слова, чтобы найти его основу^[3]. Некоторые примеры правил выглядят следующим образом:

• если слово оканчивается на 'ed', удалить 'ed'
• если слово оканчивается на 'ing', удалить 'ing'
• если слово оканчивается на 'ly', удалить 'ly'

Алгоритмы усечения окончаний гораздо эффективнее, чем алгоритмы полного перебора. Для разработки таких алгоритмов нужен программист, который достаточно хорошо разбирается в лингвистике, в частности морфологии, а также умеет кодировать «правила усечения». Алгоритмы усечения окончаний неэффективны для исключительных ситуаций (например, 'ran' и 'run'). Решения, полученные алгоритмами усечения окончаний, ограничиваются теми частями речи, которые имеют хорошо известные окончания и суффиксы с некоторыми исключениями. Это является серьёзным ограничением, так как не все части речи имеют хорошо сформулированный набор правил. Лемматизация пытается снять это ограничение.

Алгоритмы усечения префикса также могут быть реализованы. Однако не во всех языках слова имеют приставки и суффиксы.

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

Может быть так, что два или более правила усечения применяются для одного и того же входного терма, что создаёт неопределённость относительно того, какое правило применить. Алгоритм может определить приоритет выполнения таких правил (с помощью человека или стохастическим способом). Или алгоритм может отклонить одно из правил, если оно приводит к несуществующему терму, тогда как другое — нет. Например, для английского терма «friendlies» алгоритм может определить суффикс «ies», применить соответствующее правило и получить результат «friendl». Терм «friendl», скорее всего, не будет найден в лексиконе и, следовательно, данное правило будет отвергнуто.

Одним из улучшений алгоритмов усечения окончаний является использование подстановки суффиксов и окончаний. Подобно правилу усечения, правило подстановки заменяет суффикс или окончание альтернативным. Например, может существовать правило, которое заменяет «ies» на «y». Поскольку правила усечения приводят к несуществующему терму в лексиконе, то правила подстановки решают эту проблему. В этом примере, «friendlies» преобразуется в «friendly» вместо «friendl».

Обычно применение данных правил носит циклический или рекурсивный характер. После первого применения правила подстановки для этого примера алгоритм производит выбор следующего правила для терма «friendly», в результате которого будет выявлено и признано правило усечения суффикса «ly». Таким образом, терм «friendlies» с помощью правила подстановки становится термом «friendly», который после применения правила усечения, становится термом «friend».

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

В лингвистике самыми распространёнными терминами для обозначения аффиксов являются суффикс и префикс. В дополнение к подходам, которые обрабатывают суффиксы или окончания, некоторые из них также обрабатывают префиксы. Например, для английского слова indefinitely данный метод определит, что конструкция «in», стоящая в начале слова, является префиксом и может быть удалена для получения основы слова. Многие из методов, упомянутых выше, также используют данный подход. Например, алгоритм усечения окончаний может обрабатывать как суффиксы и окончания, так и префиксы, тогда он будет носить другое название и следовать данному подходу. Исследования аффикс-стеммеров для нескольких европейских языков можно найти в публикации (Jongejan et al 2009).

Более сложным подходом к решению проблемы определения основы слова является лемматизация. Чтобы понять, как работает лемматизация, нужно знать, как создаются различные формы слова. Большинство слов изменяется, когда они используются в различных грамматических формах. Конец слова заменяется на грамматическое окончание, и это приводит к новой форме исходного слова. Лемматизация выполняет обратное преобразование: заменяет грамматическое окончание суффиксом или окончанием начальной формы^[4].

Также лемматизация включает определение части речи слова и применение различных правил нормализации для каждой части речи. Определение части речи происходит до попытки найти основу, поскольку для некоторых языков правила стемминга зависят от части речи данного слова.

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

Первоначально Ripple-down rules был разработан для приобретения знаний и обслуживания систем, основанных на правилах. В данном подходе знания приобретаются на основе текущего контекста и постепенно добавляются. Правила создаются для классификации случаев, соответствующих определённому контексту.

В отличие от стандартных правил классификации, Ripple-down Rules использует исключения из существующих правил, поэтому изменения связаны только с контекстом правила и не влияют на другие. Инструменты приобретения знаний помогают найти и изменить конфликтующие правила. Приведём простой пример правила Ripple-down:

Данное правило можно проинтерпретировать так: «если a и b истина, то мы принимаем решение c, за исключением случая, когда d не истина. Если d истина (исключение), то принимаем решение e. Если a и b не истина, то мы переходим к другому правилу и принимаем решение h, если f и g истина». Эта форма правил очень хорошо решает задачу лемматизации^[5].

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

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

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

Некоторые алгоритмы стемминга используют анализ N-грамм, для того чтобы выбрать подходящую основу для слова^[6].

Одним из главных недостатков классических стеммеров (например, стеммера Портера) является то, что они часто не различают слова со схожим синтаксисом, но совершенно с разными значениями. Например, «news» и «new» в результате стемминга сведутся к основе «new», хотя данные слова принадлежат к разным лексическим категориям. Другая проблема заключается в том, что некоторые алгоритмы стемминга могут быть пригодны для одного корпуса и вызывать слишком много ошибок в другом. Например, слова «stock», «stocks», «stocking» и т. д. будут иметь особое значение в текстах газеты The Wall Street Journal. Основная идея стемминга на основе корпуса текстов состоит в создании классов эквивалентности для слов классических стеммеров, а затем «разбить» некоторые слова, объединённые на основе их встречаемости в корпусе. Это также помогает предотвратить хорошо известные конфликтные ситуации алгоритма Портера, например, как «policy/police», так как шанс встретить данные слова вместе является довольно низким^[7].

Такие алгоритмы используют базу данных основ (например, набор документов, содержащие основы слов). Данные основы не обязательно соответствуют обычным словам, в большинстве случаев основа представляет собой подстроку (например, для английского языка «brows» является подстрокой в словах «browse» и «browsing»). Для того, чтобы определить основу слова, алгоритм пытается сопоставить его с основами из базы данных, применяя различные ограничения, например, на длину искомой основы в слове относительно длины самого слова (так например, короткий префикс «be», который является основой таких слов, как «be», «been» и «being», не будет являться основой слова «beside»).

Гибридные подходы используют два или более методов, описанных выше. Простым примером является алгоритм, использующий суффиксное дерево, который в начале своей работы использует таблицы поиска для получения первоначальных данных с помощью полного перебора. Тем не менее, вместо того, чтобы хранить весь комплекс отношений между словами для определённого языка, таблица поиска используется для хранения небольшого числа «частых исключений» (например, для английского языка «ran => run»). Если слово отсутствует в списке исключения, применяется алгоритмы усечения окончаний или лемматизации для получения результата.

В то время как большая часть ранней научной деятельности в данной области была сосредоточена на английском языке (в основном с использованием алгоритма стемминга Портера), последующие работы были посвящены и многим другим языкам^{[8][9][10][11][12]}.

Иврит и арабский по-прежнему считаются сложными для исследования языками в плане стемминга. Английские алгоритмы стемминга являются достаточно тривиальными (лишь иногда возникают проблемы, например, слово «dries» является формой третьего лица единственного числа настоящего времени глагола «dry», или слово «axes» является множественным числом от «axe» и «axis»); но стеммеры становится все сложнее проектировать в том случае, когда выбирается более сложный целевой язык, а именно, язык с более сложными морфологией и орфографией. Например, стеммеры для итальянского языка являются более сложными, чем стеммеры для английского (из-за большого числа флективных форм глаголов), для русского языка реализации ещё сложнее (большое число склонений существительных), для иврита — ещё более сложные (в связи с неконкатенативной морфологией, письменности без гласных и необходимости в алгоритмах усечения префиксов: основы слов иврита могут иметь длину в два, три или в четыре символа, но не больше), и так далее.

Многоязычные алгоритмы стемминга применяют морфологические правила двух или более языков одновременно.

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

Рассмотрим наиболее популярные реализации стеммеров, основывающиеся на различных принципах и допускающие обработку несуществующих слов для русского языка.

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

Алгоритм состоит из пяти шагов. На каждом шаге отсекается словообразующий суффикс и оставшаяся часть проверяется на соответствие правилам (например, для русских слов основа должна содержать не менее одной гласной). Если полученное слово удовлетворяет правилам, происходит переход на следующий шаг. Если нет — алгоритм выбирает другой суффикс для отсечения. На первом шаге отсекается максимальный формообразующий суффикс, на втором — буква «и», на третьем — словообразующий суффикс, на четвёртом — суффиксы превосходных форм, «ь» и одна из двух «н»^[13].

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

Данный алгоритм стемминга (анализатор) разработан Андреем Коваленко в 2002 году. Он основан на вероятностной модели: слова из обучающего текста разбираются анализатором на пары «последние две буквы основы» + «суффикс» и если такая пара уже присутствует в модели — увеличивается её вес, иначе она добавляется в модель. После чего полученный массив данных ранжируется по убыванию веса и модели, вероятность реализации которых составляет менее 1/10000, отсекаются. Результат — набор потенциальных окончаний с условиями на предшествующие символы — инвертируется для удобства сканирования словоформ «справа налево» и представляется в виде таблицы переходов конечного автомата. При разборе слово сканируется по построенным таблицам перехода. К алгоритму также было добавлено специальное правило, гласящее, что неизменяемая основа должна содержать как минимум одну гласную^[14].

Представленный анализатор доступен в исходных текстах и может использоваться в свободной форме с условием ссылки на источник^[15][16].

Стеммер MyStem разработан Ильёй Сегаловичем в 1998. Сейчас является собственностью компании Яндекс^[17]. На первом шаге при помощи дерева суффиксов во входном слове определяются возможные границы между основой и суффиксом, после чего для каждой потенциальной основы (начиная с самой длинной) бинарным поиском по дереву основ проверяется её наличие в словаре либо нахождение наиболее близких к ней основ (мерой близости является длина общего «хвоста»). Если слово словарное — алгоритм заканчивает работу, иначе — переходит к следующему разбиению.

Если вариант основы не совпадает ни с одной из «ближайших» словарных основ, то это означает, что анализируемое слово с данным вариантом основы в словаре отсутствует. Тогда по имеющейся основе, суффиксу и модели «ближайшей» словарной основы генерируется гипотетическая модель изменения данного слова. Гипотеза запоминается, а если она уже была построена ранее — увеличивает свой вес. Если слово так и не было найдено в словаре — длина требуемого общего окончания основ уменьшается на единицу, идёт просмотр дерева на предмет новых гипотез. Когда длина общего «хвоста» достигает 2, поиск останавливается и идёт ранжирование гипотез по продуктивности: если вес гипотезы в пять и более раз меньше самого большого веса — такая гипотеза отсеивается. Результатом работы стеммера является получившийся набор гипотез для несуществующего или одна гипотеза для словарного слова^[18].

Стеммер может быть использован для коммерческих целей; исключениями являются: создание и распространение спама, поисковая оптимизация сайтов и разработка продуктов и сервисов, аналогичных сервисам и продуктам компании Яндекс^[17]. Исходные коды не распространяются^[19]. Для установки достаточно скачать и распаковать архив^[20].

‌Изначально стеммер Snowforce разрабатывался с 2018 года Виталием Муравлевым под научным руководством Леонида Гращенко как модификация популярного алгоритма Snowball (стеммера Портера). Исследователями было замечено, что алгоритм Snowball избыточен, так как проверяет несвойственные русскому языку комбинации суффиксов и окончаний. Кроме того, он не в полной мере учитывает особенности морфологии русского языка. Разработанная первая версия алгоритма Snowforce исключила ряд недостатков алгоритма Snowball за счет использования остановов, оптимизации порядка и содержания проверки окончаний и суффиксов с учетом их встречаемости, а также замены списков окончаний совокупностью восьми бинарных деревьев. При сохранении полноты и точности оригинала, алгоритм Snowforce выполняется, по меньшей мере, в 3,75 раз быстрее алгоритма Snowball (его реализации на бинарных деревьях), который до этого являлся наиболее быстрым алгоритмом ^[21]. При этом, однако, точность стемминга сохранилась на уровне оригинального Snowball (около 0,82). Таки образом, оставались существенные резервы для повышения точности алгоритма.

В дальнейшем разработка была продолжена Максимом Арабским под научным руководством Леонида Гращенко. В результате в 2022 году авторами была выполнена государственная регистрация программы для ЭВМ Библиотека стемминга для русского языка «Snowforce» (номер регистрации: 2022661293) ^[22].

Выделяют два вида ошибок в алгоритмах стемминга: overstemming' и understemming. Overstemming — ошибка первого рода, когда флективные слова ошибочно относят к одной лемме. Understemming — ошибка второго рода, когда морфологические формы одного слова относят к разным леммам. Алгоритмы стемминга стараются свести к минимуму обе эти ошибки, хотя сокращение одного типа ошибок может привести к увеличению другого^[23].

Рассмотрим данные виды ошибок на работе алгоритма стемминга Портера. Случай ошибки overstemming: данный алгоритм сопоставит слова «universal», «university» и «universe» с основой «univers»; хотя эти слова этимологически разные, их современные значения относятся к различным областям, поэтому рассматривать их как синонимы неверно. Случай ошибки understemming: алгоритм Портера сопоставит словам, которые являются производными от одной леммы, разные основы, а, следовательно, отнесёт их к разным леммам — «alumnus» → «alumnu», «alumni» → «alumni», «alumna»/«alumnae» → «alumna» (данные слова сохранили в своей морфологии латинские особенности, но эти почти-синонимы не были объединены стеммером).

Стемминг используется в качестве приближённого метода для группировки слов с похожими основными значениями. Например текст, в котором упоминается «daffodils», вероятно, тесно связан с текстом, упоминающим о «daffodil» (без «s»). Но в некоторых случаях, слова с одной и той же основой имеют идиоматические значения, которые почти не связаны: при поиске пользователем документов, содержащих «marketing», будут также выданы документы, упоминающие «markets», но не содержащие «marketing» (что, скорее всего, не соответствует информационной потребности пользователя).

Стемминг достаточно распространён в поисковых системах. Однако сравнительно скоро эффективность стемминга в поисковых системах для английского языка была признана весьма ограниченной, и это привело начинающих исследователей в области информационного поиска к пониманию неприменимости стемминга в общем случае^[24][25]. В поисковых системах вместо стемминга может быть использован подход, основанный на поиске N-грамм, а не основ. Кроме того, последние исследования показали большие преимущества при поиске с помощью N-грамм для других языков, кроме английского^[26][27].

При анализе предметных областей с помощью стемминга строятся словари этих областей^[28].

Многие коммерческие компании уже используют стемминг, по крайней мере, с 1980-х годов и разработали алгоритмические и лексические стеммеры для многих языков^[29][30].

Было выполнено сравнение Snowball-стеммеров с коммерческими. Результаты были неоднозначными^[31][32].

Поисковая система Google стала использовать стемминг с 2003 года^[33]. Ранее поиск «fish» не вернул бы результатов, содержащих «fishing».

• Корень (лингвистика)
• Морфология (лингвистика)
• Основа слова
• Лемматизация
• Лексема (лингвистика)
• Словоизменение
• Словообразование
• Обработка естественного языка
• Анализ текста
• Компьютерная лингвистика

• NLPub: Stemka (Вероятностный морфологический анализатор русского языка, разработанный Андреем Коваленко)  (рус.). Дата обращения: 27 января 2014.
• Вероятностный морфологический анализатор русского и украинского языков  (рус.). Дата обращения: 27 января 2014.
• Snowforce: быстрый стеммер для русского языка  (неопр.) (23 марта 2017).
• NLPub: Mystem  (рус.). Дата обращения: 27 января 2014.
• О программе mystem  (рус.). Дата обращения: 27 января 2014.
• Лицензионное соглашение на использование программы «MyStem»  (рус.) (27 октября 2011). Дата обращения: 12 мая 2014.
• Apache OpenNLP использует стеммеры Портера и «Snowball»
• SMILE Stemmer — бесплатные онлайн сервис, использующий стеммеры Портера и Paice/Husk Lancaster (Java API)
• Themis — фреймворк с открытым исходным, использующий реализацию стеммера Портера (PostgreSQL, Java API)
• Snowball — бесплатные алгоритмы стемминга для множества языков, включают исходный код, а также стеммеры для пяти романских языков
• Snowball on C# — реализация стеммеров «Snowball» на C# (14 языков)
• Language wrappers — расширение Python для Snowball API
• Ruby-Stemmer — расширение Ruby для Snowball API
• PECL — расширение PHP для Snowball API
• Oleander Porter’s algorithm — библиотека стемминга для C++, распространяемая под лицензией BSD
• Unofficial home page of the Lovins stemming algorithm — стеммеры с открытым исходным кодом для нескольких языков
• Official home page of the Lancaster stemming algorithm — стеммеры Ланкастерского университета, UK
• Overview of stemming algorithms
• PTStemmer — Java/Python/.Net стеммеры для португальского языка
• jsSnowball — реализация с открытым исходным кодом на JavaScript алгоритмов стемминга «Snowball» для многих языков
• Snowball Stemmer — реализация на Java
• hindi_stemmer — реализация стеммера с открытым исходным кодом для языка хинди
• czech_stemmer — реализация стеммера с открытым исходным кодом для чешского языка

В сносках к статье найдены неработоспособные вики-ссылки. Исправьте короткие примечания, установленные через шаблон {{sfn}} или его аналоги, в соответствии с инструкцией к шаблону, или добавьте недостающие публикации в раздел источников. Список сносок: Y-stemmer, Viatcheslav Yatsko