Лекция
Привет, Вы узнаете о том , что такое стемминг, Разберем основные их виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое стемминг, стеммер портера , настоятельно рекомендую прочитать все из категории Автоматическое распознавание речи.
стемминг — это процесс нахождения основы слова для заданного исходного слова. Основа слова необязательно совпадает с морфологическим корнем слова.
Задача нахождения основы слова представляет собой давнюю проблему в области компьютерных наук. Первая публикация по данному вопросу датируется 1968 годом. Стемминг применяется в поисковых системах для расширения поискового запроса пользователя, является частью процесса нормализации текста.
Конкретный способ решения задачи поиска основы слов называется алгоритм стемминга, а конкретная реализация — стеммер.
Первый опубликованный стеммер был написан Джули Бет Ловинс в 1968 году . Эта статья значима ранней датой публикации и оказала большое влияние на более поздние работы в данной области.
Позже стеммер был написан Мартином Портером и опубликован в 1980 году. Этот стеммер очень широко использовался и стал де-факто стандартным алгоритмом для текстов на английском языке. Доктор Портер получил премию Стрикса в 2000 году за работы по стеммингу и поиску информации.
Многие реализации алгоритма стемминга Портера были написаны и свободно распространялись; однако, многие из этих реализаций содержат труднонаходимые недостатки. В результате, данные алгоритмы не работали в полную силу. Для устранения такого типа ошибок Мартин Портер выпустил официальную свободную реализацию алгоритма около 2000 года. Он продолжал эту работу в течение нескольких следующих лет, разработав Snowball, фреймворк для создания алгоритмов стемминга, и улучшенных стеммеров английского языка, а также стеммеров для некоторых других языков.
Существует несколько типов алгоритмов стемминга, которые различаются по отношению производительности, точности, а также как преодолеваются определенные проблемы стемминга.
Простой стеммер ищет флективную форму в таблице поиска. Преимущества этого подхода заключается в его простоте, скорости, а также легкости обработки исключений. К недостаткам можно отнести то, что все флективные формы должны быть явно перечислены в таблице: новые или незнакомые слова не будут обрабатываться, даже если они являются правильными (например, iPads ~ iPad), а также проблемой является то, что таблица поиска может быть очень большой. Для языков с простой морфологией наподобие английского размеры таблиц небольшие, но для сильно флективных языков (например, турецкий) таблица может иметь сотни возможных флективных форм для каждого корня.
Таблицы поиска, используемые в стеммерах, как правило, генерируются в полуавтоматическом режиме. Например, для английского слова «run» автоматически будут сгенерированы формы «running», «runs», «runned» и «runly». Последние две формы являются допустимыми конструкциями, но они вряд ли появятся в обычном тексте на английском языке.
Алгоритм поиска может использовать предварительную частеречную разметку, чтобы избежать такой разновидности ошибки лемматизации, когда разные слова относят к одной лемме (overstemming) .
Алгоритмы усечения окончаний не используют справочную таблицу, которая состоит из флективных форм и отношений корня и формы. Вместо этого, как правило, хранится меньший список «правил», который используется алгоритмами, учитывая форму слова, чтобы найти его основу . Некоторые примеры правил выглядят следующим образом:
Алгоритмы усечения окончаний гораздо эффективнее, чем алгоритмы полного перебора. Для разработки таких алгоритмов нужен программист, который достаточно хорошо разбирается в лингвистике, в частности морфологии, а также умеет кодировать «правила усечения». Алгоритмы усечения окончаний неэффективны для исключительных ситуаций (например, 'ran' и 'run')). Решения, полученные алгоритмами усечения окончаний, ограничиваются теми частями речи, которые имеют хорошо известные окончания и суффиксы с некоторыми исключениями. Это является серьезным ограничением, так как не все части речи имеют хорошо сформулированный набор правил. Лемматизация пытается снять это ограничение.
Алгоритмы усечения префикса также могут быть реализованы. Однако не во всех языках слова имеют приставки и суффиксы.
Алгоритмы усечения окончаний могут отличаться в результатах по целому ряду причин. Одной из таких причин является особенность алгоритма: должно ли быть слово на выходе алгоритма реальным словом в данном языке. Некоторые подходы не требуют наличия слова в соответствующей языковой лексики. Кроме того, некоторые алгоритмы ведут базу данных всех известных морфологических корней, которые существуют как реальные слова. Данные алгоритмы проверяют наличие терма в базе данных для принятия решения. Как правило, если терм не найден, выполняются альтернативные действия. Данные альтернативные действия могут использовать несколько другие критерии для принятия решения. Несуществующий терм может послужить применению альтернативных правил усечения.
Может быть так, что два или более правила усечения применяются для одного и того же входного терма, что создает неопределенность относительно того, какое правило применить. Алгоритм может определить приоритет выполнения таких правил (с помощью человека или стохастическим способом). Или алгоритм может отклонить одно из правил, если оно приводит к несуществующему терму, тогда как другое нет. Например, для английского терма «friendlies» алгоритм может определить суффикс «ies», применить соответствующее правило и получить результат «friendl». Терм «friendl», скорее всего, не будет найден в лексиконе и, следовательно, данное правило будет отвергнуто.
Одним из улучшений алгоритмов усечения окончаний является использование подстановки суффиксов и окончаний. Подобно правилу усечения, правило подстановки заменяет суффикс или окончание альтернативным. Например, может существовать правило, которое заменяет «ies» на «y». Поскольку правила усечения приводят к несуществующему терму в лексиконе, то правила подстановки решают эту проблему. В этом примере, «friendlies» преобразуется в «friendly» вместо «friendl».
Обычно применение данных правил носит циклический или рекурсивный характер. После первого применения правила подстановки для этого примера, алгоритм производит выбор следующего правила для терма «friendly», в результате которого будет выявлено и признано правило усечения суффикса «ly». Таким образом, терм «friendlies» с помощью правила подстановки становится термом «friendly», который после применения правила усечения, становится термом «friend».
Данный пример помогает продемонстрировать разницу между методом, основанным на правилах, и методом «грубой силы». С помощью полного перебора, алгоритм будет искать терм «friendlies» в наборе из сотни тысяч флективных словоформ и в идеале найдет соответствующую основу «friend». В методе, основанном на правилах, происходит последовательное выполнение правил, в результате чего получается тоже решение. Скорее всего, что метод на основе правил будет быстрее.
В лингвистике самыми распространенными терминами для обозначения аффиксов являются суффикс и префикс. В дополнение к подходам, которые обрабатывают суффиксы или окончания, некоторые из них также обрабатывают префиксы. Например, для английского слова indefinitely данный метод определит, что конструкция «in», стоящая в начале слова, является префиксом и может быть удалена для получения основы слова. Многие из методов, упомянутых выше, также используют данный подход. Об этом говорит сайт https://intellect.icu . Например, алгоритм усечения окончаний может обрабатывать как суффиксы и окончания, так и префиксы, тогда он будет носить другое название и следовать данному подходу. Исследования аффикс-стеммеров для нескольких европейских языков можно найти в публикации (Jongejan et al 2009).
Более сложным подходом к решению проблемы определения основы слова является лемматизация. Чтобы понять, как работает лемматизация, нужно знать, как создаются различные формы слова. Большинство слов изменяется, когда они используются в различных грамматических формах. Конец слова заменяется на грамматическое окончание, и это приводит к новой форме исходного слова. Лемматизация выполняет обратное преобразование: заменяет грамматическое окончание суффиксом или окончанием начальной формы .
Также лемматизация включает определение части речи слова и применение различных правил нормализации для каждой части речи. Определение части речи происходит до попытки найти основу, поскольку для некоторых языков правила стемминга зависят от части речи данного слова.
Этот подход крайне зависим от точного определения лексической категории (часть речи). Хотя и существует частичное совпадение между правилами нормализации для некоторых лексических категорий, указание неверной категории или неспособность определить правильную категорию сводит на нет преимущество этого подхода над алгоритмом усечения окончаний. Основная идея заключается в том, что если стеммер имеет возможность получить больше информации об обрабатываемом слове, то он может применять более точные правила нормализации.
Первоначально 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-грамм, для того чтобы выбрать подходящую основу для слова .
Одим из главных недостатков классических стеммеров (например, стеммер портера ) является то, что они часто не различают слова со схожим синтаксисом, но совершенно с разными значениями. Например, «news» и «new» в результате стемминга сведутся к основе «new», хотя данные слова принадлежат к разным лексическим категориям. Другая проблема заключается в том, что некоторые алгоритмы стемминга могут быть пригодны для одного корпуса и вызывать слишком много ошибок в другом. Например, слова «stock», «stocks», «stocking» и т. д. будут иметь особое значение в текстах газеты The Wall Street Journal. Основная идея стемминга на основе корпуса текстов состоит в создании классов эквивалентности для слов классических стеммеров, а затем «разбить» некоторые слова, объединенные на основе их встречаемости в корпусе. Это также помогает предотвратить хорошо известные конфликтные ситуации алгоритма Портера, например, как «policy/police», так как шанс встретить данные слова вместе является довольно низким .
Такие алгоритмы используют базу данных основ (например, набор документов, содержащие основы слов). Данные основы не обязательно соответствуют обычным словам, в большинстве случаев основа представляет собой подстроку (например, для английского языка «brows» является подстрокой в словах «browse» и «browsing»). Для того, что определить основу слова алгоритм пытается сопоставить его с основами из базы данных, применяя различные ограничения, например, на длину искомой основы в слове относительно длины самого слова (так например, короткий префикс «be», который является основой таких слов, как «be», «been» и «being», не будет являться основой слова «beside»).
Гибридные подходы используют два или более методов описанных выше. Простым примером является алгоритм, использующий суффиксное дерево, который в начале своей работы использует таблицы поиска для получения первоначальных данных с помощью полного перебора. Тем не менее, вместо того, чтобы хранить весь комплекс отношений между словами для определенного языка, таблица поиска используется для хранения небольшого числа «частых исключений» (например, для английского языка «ran => run»). Если слово отсутствует в списке исключения, применяется алгоритмы усечения окончаний или лемматизации для получения результата.
В то время как большая часть ранней научной деятельности в данной области была сосредоточена на английском языке (в основном с использованием алгоритма стемминга Портера), последующие работы были посвящены и многим другим языкам [10][11][12].
Иврит и арабский по-прежнему считаются сложными для исследования языками в плане стемминга. Английские алгоритмы стемминга являются достаточно тривиальными (лишь иногда возникают проблемы, например, слово «dries» является формой третьего лица единственного числа настоящего времени глагола «dry», или слово «axes» является множественным числом от «axe» и «axis»); но стеммеры становится все сложнее проектировать в том случае, когда выбирается более сложный целевой язык, а именно, язык с более сложными морфологией и орфографией. Например, стеммеры для итальянского языка являются более сложными, чем стеммеры для английского (из-за большого числа флективных форм глаголов), для русского языка реализации еще сложнее (большое число склонений существительных), для иврита — еще более сложные (в связи с неконкатенативной морфологией, письменности без гласных и необходимости в алгоритмах усечения префиксов: основы слов иврита могут иметь длину в два, три или в четыре символа, но не больше), и так далее.
Многоязычные алгоритмы стемминга применяют морфологические правила двух или более языков одновременно.
Русский язык относится к группе флективных синтетических языков, то есть языков, в которых преобладает словообразование с использованием аффиксов, сочетающих сразу несколько грамматических значений (например, добрый — окончание ый указывает одновременно на единственное число, мужской род и именительный падеж), поэтому данный язык допускает использование алгоритмов стемминга. Русский язык имеет сложную морфологическую изменяемость слов, которая является источником ошибок при использовании стемминга. В качестве решения данной проблемы можно использовать наряду с классическими алгоритмами стемминга алгоритмы лемматизации, которые приводят слова к начальной базовой форме.
Рассмотрим наиболее популярные реализации стеммеров, основывающиеся на различных принципах и допускающие обработку несуществующих слов для русского языка.
Основная идея стеммера Портера заключается в том, что существует ограниченное количество словообразующих суффиксов, и стемминг слова происходит без использования каких-либо баз основ: только множество существующих суффиксов и вручную заданные правила.
Алгоритм состоит из пяти шагов. На каждом шаге отсекается словообразующий суффикс и оставшаяся часть проверяется на соответствие правилам (например, для русских слов основа должна содержать не менее одной гласной). Если полученное слово удовлетворяет правилам, происходит переход на следующий шаг. Если нет — алгоритм выбирает другой суффикс для отсечения. На первом шаге отсекается максимальный формообразующий суффикс, на втором — буква «и», на третьем — словообразующий суффикс, на четвертом — суффиксы превосходных форм, «ь» и одна из двух «н»[13].
Данный алгоритм часто обрезает слово больше необходимого, что затрудняет получение правильной основы слова, например кровать->крова (при этом реально неизменяемая часть — кроват, но стеммер выбирает для удаления наиболее длинную морфему). Также стеммер Портера не справляется со всевозможными изменениями корня слова (например, выпадающие и беглые гласные).
Данный алгоритм стемминга (анализатор) разработан Андреем Коваленко в 2002 году. Он основан на вероятностной модели: слова из обучающего текста разбираются анализатором на пары «последние две буквы основы» + «суффикс» и если такая пара уже присутствует в модели — увеличивается ее вес, иначе она добавляется в модель. После чего полученный массив данных ранжируется по убыванию веса и модели, вероятность реализации которых составляет менее 1/10000, отсекаются. Результат — набор потенциальных окончаний с условиями на предшествующие символы — инвертируется для удобства сканирования словоформ «справа налево» и представляется в виде таблицы переходов конечного автомата. При разборе слово сканируется по построенным таблицам перехода. К алгоритму также было добавлено специальное правило, гласящее, что неизменяемая основа должна содержать как минимум одну гласную[14].
Представленный анализатор доступен в исходных текстах и может использоваться в свободной форме с условием ссылки на источник[15][16].
Стеммер MyStem разработан Ильей Сегаловичем в 1998. Сейчас является собственностью компании Яндекс[17]. На первом шаге при помощи дерева суффиксов во входном слове определяются возможные границы между основой и суффиксом, после чего для каждой потенциальной основы (начиная с самой длинной) бинарным поиском по дереву основ проверяется ее наличие в словаре либо нахождение наиболее близких к ней основ (мерой близости является длина общего «хвоста»). Если слово словарное — алгоритм заканчивает работу, иначе — переходит к следующему разбиению.
Если вариант основы не совпадает ни с одной из «ближайших» словарных основ, то это означает, что анализируемое слово с данным вариантом основы в словаре отсутствует. Тогда по имеющейся основе, суффиксу и модели «ближайшей» словарной основы генерируется гипотетическая модель изменения данного слова. Гипотеза запоминается, а если она уже была построена ранее — увеличивает свой вес. Если слово так и не было найдено в словаре — длина требуемого общего окончания основ уменьшается на единицу, идет просмотр дерева на предмет новых гипотез. Когда длина общего «хвоста» достигает 2, поиск останавливается и идет ранжирование гипотез по продуктивности: если вес гипотезы в пять и более раз меньше самого большого веса — такая гипотеза отсеивается. Результатом работы стеммера является получившийся набор гипотез для несуществующего или одна гипотеза для словарного слова[18].
Стеммер может быть использован для коммерческих целей; исключениями являются: создание и распространение спама, поисковая оптимизация сайтов и разработка продуктов и сервисов, аналогичных сервисам и продуктам компании Яндекс[17]. Исходные коды не распространяются[19]. Для установки достаточно скачать и распаковать архив[20].
Выделяют два вида ошибок в алгоритмах стемминга: overstemming' и understemming. Overstemming — ошибка первого рода, когда флективные слова ошибочно относят к одной лемме. Understemming — ошибка второго рода, когда морфологические формы одного слова относят к разным леммам. Алгоритмы стемминга стараются свести к минимуму обе эти ошибки, хотя сокращение одного типа ошибок может привести к увеличению другого[21].
Рассмотрим данные виды ошибок на работе алгоритма стемминга Портера. Случай ошибки overstemming: данный алгоритм сопоставит слова «universal», «university» и «universe» с основой «univers»; хотя эти слова этимологически разные, их современные значения относятся к различным областям, поэтому рассматривать их как синонимы неверно. Случай ошибки understemming: алгоритм Портера сопоставит словам, которые являются производными от одной леммы разные основы, а следовательно отнесет их к разным леммам — «alumnus» → «alumnu», «alumni» → «alumni», «alumna»/«alumnae» → «alumna» (данные слова сохранили в своей морфологии латинские особенности, но эти почти-синонимы не были объединены стеммером).
Стемминг используется в качестве приближенного метода для группировки слов с похожими основными значениями. Например текст, в котором упоминается «daffodils», вероятно, тесно связан с текстом, упоминающим о «daffodil» (без «s»). Но в некоторых случаях, слова с одной и той же основой имеют идиоматические значения, которые почти не связаны: при поиске пользователем документов, содержащих «marketing», будут также выданы документы упоминающие «markets», но не содержащие «marketing» (что, скорее всего, не соответствует информационной потребности пользователя).
Стемминг достаточно распространен в поисковых системах. Однако сравнительно скоро эффективность стемминга в поисковых системах для английского языка была признана весьма ограниченной, и это привело начинающих исследователей в области информационного поиска к пониманию неприменимости стемминга в общем случае[22][23]. В поисковых системах вместо стемминга может быть использован подход, основанный на поиске N-грамм, а не основ. Кроме того, последние исследования показали большие преимущества при поиске с помощью N-грамм для других языков, кроме английского[24][25].
При анализе предметных областей с помощью стемминга строятся словари этих областей[26].
Многие коммерческие компании уже используют стемминг, по крайней мере, с 1980-х годов и разработали алгоритмические и лексические стеммеры для многих языков[27][28].
Было выполнено сравнение Snowball-стеммеров с коммерческими. Результаты были неоднозначными[29][30].
Поисковая система Google стала использовать стемминг с 2003 года[31]. Ранее поиск «fish» не вернул бы результатов, содержащих «fishing».
Стеммер Портера
Стеммер Портера — алгоритм стемминга, опубликованный Мартином Портером в 1980 году. Оригинальная версия стеммера была предназначена для английского языка и была написана на языке BCPL. Впоследствии Мартин создал проект «Snowball» и, используя основную идею алгоритма, написал стеммеры для распространенных индоевропейских языков, в том числе для русского .
Алгоритм не использует баз основ слов, а лишь, применяя последовательно ряд правил, отсекает окончания и суффиксы, основываясь на особенностях языка, в связи с чем работает быстро, но не всегда безошибочно.
Алгоритм был очень популярен и тиражируем, в него часто вносились изменения разными разработчиками, причем не всегда удачные. Примерно в 2000 году Портер принял решение «заморозить» проект и впредь распространять одну-единственную реализацию алгоритма (на нескольких популярных языках программирования) со своего сайта.
Выводы из данной статьи про стемминг указывают на необходимость использования современных методов для оптимизации любых систем. Надеюсь, что теперь ты понял что такое стемминг, стеммер портера и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Автоматическое распознавание речи
Комментарии
Оставить комментарий
Автоматическое распознавание речи
Термины: Автоматическое распознавание речи