Сте́мминг ( — находить происхождение) — это процесс нахождения основы слова для заданного исходного слова. Основа слова не обязательно совпадает с морфологическим корнем слова.
Задача нахождения основы слова представляет собой давнюю проблему в области компьютерных наук. Первая публикация по данному вопросу датируется 1968 годом. Стемминг применяется в поисковых системах для расширения поискового запроса пользователя, является частью процесса нормализации текста.
Конкретный способ решения задачи поиска основы слов называется алгоритм стемминга, а конкретная реализация — стеммер.
История Первый опубликованный стеммер был написан Джули Бет Ловинс в 1968 году. Эта статья значима ранней датой публикации и оказала большое влияние на более поздние работы в данной области.
Позже стеммер был написан Мартином Портером и опубликован в 1980 году. Этот стеммер очень широко использовался и стал де-факто стандартным алгоритмом для текстов на английском языке. Доктор Портер получил премию Стрикса в 2000 году за работы по стеммингу и поиску информации.
Многие реализации алгоритма стемминга Портера были написаны и свободно распространялись; однако, многие из этих реализаций содержат труднонаходимые недостатки. В результате, данные алгоритмы не работали в полную силу. Для устранения такого типа ошибок Мартин Портер выпустил официальную свободную реализацию алгоритма около 2000 года. Он продолжал эту работу в течение нескольких следующих лет, разработав Snowball, фреймворк для создания алгоритмов стемминга, и улучшенных стеммеров английского языка, а также стеммеров для некоторых других языков.
Алгоритмы Существует несколько типов алгоритмов стемминга, которые различаются по отношению производительности, точности, а также как преодолеваются определённые проблемы стемминга.
Алгоритмы поиска Простой стеммер ищет флективную форму в таблице поиска. Преимущества этого подхода заключается в его простоте, скорости, а также лёгкости обработки исключений. К недостаткам можно отнести то, что все флективные формы должны быть явно перечислены в таблице: новые или незнакомые слова не будут обрабатываться, даже если они являются правильными (например, iPads ~ iPad), а также проблемой является то, что таблица поиска может быть очень большой. Для языков с простой морфологией наподобие английского размеры таблиц небольшие, но для сильно флективных языков (например, турецкого) таблица может иметь сотни возможных флективных форм для каждого корня.
Таблицы поиска, используемые в стеммерах, как правило, генерируются в полуавтоматическом режиме. Например, для английского слова «run» автоматически будут сгенерированы формы «running», «runs», «runned» и «runly». Последние две формы являются допустимыми конструкциями, но они вряд ли появятся в обычном тексте на английском языке.
Алгоритм поиска может использовать предварительную частеречную разметку, чтобы избежать такой разновидности ошибки лемматизации, когда разные слова относят к одной лемме (overstemming).
Алгоритмы усечения окончаний Алгоритмы усечения окончаний не используют справочной таблицы, которая состоит из флективных форм и отношений корня и формы. Вместо этого, как правило, хранится меньший список «правил», который используется алгоритмами, учитывая форму слова, чтобы найти его основу. Некоторые примеры правил выглядят следующим образом: если слово оканчивается на '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», стоящая в начале слова, является префиксом и может быть удалена для получения основы слова. Многие из методов, упомянутых выше, также используют данный подход. Например, алгоритм усечения окончаний может обрабатывать как суффиксы и окончания, так и префиксы, тогда он будет носить другое название и следовать данному подходу. Исследования аффикс-стеммеров для нескольких европейских языков можно найти в публикации .
Алгоритмы лемматизации Более сложным подходом к решению проблемы определения основы слова является лемматизация. Чтобы понять, как работает лемматизация, нужно знать, как создаются различные формы слова. Большинство слов изменяется, когда они используются в различных грамматических формах. Конец слова заменяется на грамматическое окончание, и это приводит к новой форме исходного слова. Лемматизация выполняет обратное преобразование: заменяет грамматическое окончание суффиксом или окончанием начальной формы.
Также лемматизация включает определение части речи слова и применение различных правил нормализации для каждой части речи. Определение части речи происходит до попытки найти основу, поскольку для некоторых языков правила стемминга зависят от части речи данного слова.
Этот подход крайне зависим от точного определения лексической категории (часть речи). Хотя и существует частичное совпадение между правилами нормализации для некоторых лексических категорий, указание неверной категории или неспособность определить правильную категорию сводит на нет преимущество этого подхода над алгоритмом усечения окончаний. Основная идея заключается в том, что если стеммер имеет возможность получить больше информации об обрабатываемом слове, то он может применять более точные правила нормализации.
Подход Ripple-down rules Первоначально Ripple-down rules был разработан для приобретения знаний и обслуживания систем, основанных на правилах. В данном подходе знания приобретаются на основе текущего контекста и постепенно добавляются. Правила создаются для классификации случаев, соответствующих определённому контексту.
В отличие от стандартных правил классификации, Ripple-down Rules использует исключения из существующих правил, поэтому изменения связаны только с контекстом правила и не влияют на другие. Инструменты приобретения знаний помогают найти и изменить конфликтующие правила. Приведём простой пример правила Ripple-down: if a ^ b then c except if d then e else if f ^ g then h
Данное правило можно проинтерпретировать так: «если a и b истина, то мы принимаем решение c, за исключением случая, когда d не истина. Если d истина (исключение), то принимаем решение e. Если a и b не истина, то мы переходим к другому правилу и принимаем решение h, если f и g истина». Эта форма правил очень хорошо решает задачу лемматизации.
Чтобы создать исключение из правила, алгоритм должен сначала определить слово, которое индуцировало данное исключение. После этого определяются различия между двумя словами. Условие исключения правила будет соответствовать этим различиям.
Стохастические алгоритмы Стохастические алгоритмы связаны с вероятностным определением корневой формы слова. Данные алгоритмы строят вероятностную модель и обучаются с помощью таблицы соответствия корневых и флективных форм. Эта модель обычно представлена в виде сложных лингвистических правил, аналогичных по своему характеру правилам, использующимся в алгоритмах усечения окончаний и лемматизации. Стемминг выполняется посредством ввода изменённых форм для обучения модели и генерацией корневой формы в соответствии с внутренним набором правил модели, за исключением того, что решения, связанные с применением наиболее соответствующего правила или последовательности правил, а также выбором основы слова, применяются на основании того, что результирующее верное слово будет иметь самую высокую вероятность (неверные слова имеют наименьшую вероятность).
Некоторые алгоритмы лемматизации имеют стохастический характер в том смысле, что слово может принадлежать нескольким частям речи с разной вероятностью. Эти алгоритмы также могут учитывать окружающие слова, называемые контекстом. Контекстно-свободные грамматики не учитывают какую-либо дополнительную информацию. В любом случае, после присвоения вероятности каждой возможной части речи, выбирается часть речи с большей вероятностью, а также соответствующие ей правила для получения нормализованной формы.
Статистические алгоритмы
Анализ N-грамм Некоторые алгоритмы стемминга используют анализ N-грамм, для того чтобы выбрать подходящую основу для слова.
Стемминг на основе корпуса текстов