Стемминг

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

или Компьютерная программа подпрограмма, которая определяет слово, может быть названа программой стеммирования , алгоритмом стемминга или стеммером .

Примеры

Стеммер английского языка, работающий с основой cat, должен идентифицировать такие строки как Cats , Catlike и Catty . Алгоритм стеммирования может также свести слова рыбалка , рыбалка и рыбак к стеблю рыба . Основа не обязательно должна быть словом, например, алгоритм Портера сводит аргумент , аргумент , аргументы , спор и argus к основе argu .

История

Первый опубликованный стеммер был написан Джули Бет Ловинс в 1968 году. Эта статья была примечательна своей ранней датой и оказала большое влияние на последующие работы в этой области. В ее статье упоминаются три более ранние крупные попытки создания алгоритмов: профессор Джон В. Тьюки из Принстонского университета , алгоритм, разработанный в Гарвардском университете Майклом Леском под руководством профессора Джерарда Солтона , и третий алгоритм, разработанный Джеймсом Л. Долби. консультантов по исследованиям и разработкам, Лос-Альтос, Калифорния.

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

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

Стеммер Paice-Husk был разработан Крисом Д. Пейсом из Ланкастерского университета в конце 1980-х годов. Это итеративный стеммер, в котором имеется набор правил стемминга, хранящийся извне. Стандартный набор правил обеспечивает «сильный» стеммер и может предусматривать удаление или замену окончания. Метод замены позволяет избежать необходимости в отдельном этапе процесса перекодирования или обеспечения частичного сопоставления. Пейс также разработал метод прямого измерения для сравнения стеммеров, основанный на подсчете ошибок чрезмерного и недостаточного стембинга.

Алгоритмы

Нерешенная задача в информатике :

Существует ли идеальный алгоритм стемминга в английском языке?

(еще нерешенные проблемы по информатике)

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

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

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

Технология производства

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

Алгоритмы удаления суффиксов

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

• если слово заканчивается на «ed», удалите «ed»
• если слово заканчивается на «ing», удалите «ing»
• если слово заканчивается на «ly», уберите «ly»

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

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

Дополнительные критерии алгоритма

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

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

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

Если углубляться в детали, общий метод заключается в циклическом применении правил (рекурсивно, как сказали бы специалисты по информатике). После применения правила замены суффикса в этом примерном сценарии выполняется второй проход для определения правил сопоставления для термина Friendly , где правило удаления ly , скорее всего, будет идентифицировано и принято. Таким образом, товарищеские матчи становятся (через замену) дружественными , которые становятся (через зачистку) друзьями .

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

Алгоритмы лемматизации

Более сложный подход к проблеме определения основы слова — лемматизация . Этот процесс включает в себя сначала определение части речи слова и применение различных правил нормализации для каждой части речи. Часть речи сначала определяется перед попыткой найти корень, поскольку для некоторых языков правила образования основы меняются в зависимости от части речи слова.

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

Стохастические алгоритмы

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

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

n- граммный анализ

Некоторые методы определения основы используют n-граммный контекст слова для выбора правильной основы слова.

Гибридные подходы

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

Аффикс тюнеров

В лингвистике термин «аффикс» относится либо к префиксу , либо к суффиксу . Помимо работы с суффиксами, некоторые подходы также пытаются удалить общие префиксы. Например, учитывая слово indefinitely , определите, что ведущая буква «in» — это префикс, который можно удалить. Применяются многие из тех же подходов, упомянутых ранее, но они называются удалением аффикса . Исследование происхождения аффиксов для нескольких европейских языков можно найти здесь.

Алгоритмы сопоставления

Такие алгоритмы используют базу данных основ (например, набор документов, содержащих основы слов). Эти основы, как упоминалось выше, не обязательно сами по себе являются допустимыми словами (а скорее обычными подстроками, такими как «брови» в «просмотр» и «просмотр»). Чтобы образовать основу слова, алгоритм пытается сопоставить его с основами из базы данных, применяя различные ограничения, например, на относительную длину основы-кандидата внутри слова (так, чтобы, например, короткий префикс «be», который является основой таких слов, как «быть», «был» и «бытие», не будет рассматриваться как основа слова «рядом»). .

Языковые

Хотя большая часть ранних академических работ в этой области была сосредоточена на английском языке (со значительным использованием алгоритма Портера Стеммера), были исследованы и многие другие языки.

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

Многоязычный стемминг

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

Метрики ошибок

В алгоритмах стемминга есть два измерения ошибок: завышение и недооценка. Overstemming — это ошибка, при которой два отдельных измененных слова имеют один и тот же корень, хотя этого не должно было быть — ложное срабатывание . Недооценка — это ошибка, при которой два отдельных склоняемых слова должны иметь один и тот же корень, но это не так — ложноотрицательный результат . Алгоритмы стемминга пытаются минимизировать каждый тип ошибок, хотя уменьшение одного типа может привести к увеличению другого.

Например, широко используемый стеммер Портера основан на словах «универсальный», «университет» и «вселенная» на «универсы». Это случай преувеличения: хотя эти три слова этимологически связаны, их современные значения находятся в самых разных областях, поэтому рассмотрение их как синонимов в поисковой системе, вероятно, снизит релевантность результатов поиска.

Примером недооценки в стеммере Портера является «выпускник» → «выпускник», «выпускник» → «выпускник», «выпускник»/«выпускник» → «выпускник». Это английское слово сохраняет латинскую морфологию, поэтому эти почти синонимы не смешиваются.

Приложения

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

Поиск информации

Стеммеры можно использовать в качестве элементов в системах запросов, таких как в Интернете поисковые системы . Однако вскоре выяснилось, что эффективность стемминга для английских поисковых систем довольно ограничена, и это привело к тому, что первые исследователи информационного поиска сочли стемминг неактуальным в целом. альтернативный подход, основанный на поиске n-грамм Вместо этого можно использовать , а не основ. Кроме того, стеммеры могут принести больше пользы на других языках, чем на английском.

Анализ домена

Стемминг используется для определения словарей предметной области при анализе предметной области .

Использование в коммерческих продуктах

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

Стеммеры Snowball сравнивали с коммерческими лексическими стеммерами с разными результатами.

В Google Search в 2003 году была введена система словообразования. Раньше поиск по слову «рыба» не возвращал слово «рыбалка». Другие алгоритмы поиска программного обеспечения различаются по использованию образования слов. Программы, которые просто ищут подстроки, очевидно, найдут слово «рыба» в слове «рыбалка», но при поиске «рыбы» не найдут вхождения слова «рыба».

Анализ текста

Стемминг используется как задача предварительной обработки текста перед выполнением анализа текста.

См. также

• Компьютерная лингвистика
• Деривация - стемминг - это форма обратной деривации.
• перегиб
• Лемма (морфология) — лингвистическое определение.
• Лемматизация
• Лексема
• Морфология (лингвистика)
• Обработка естественного языка — стемминг обычно рассматривается как форма НЛП.
• NLTK — реализует несколько алгоритмов стемминга в Python.
• Корень (лингвистика) — лингвистическое определение термина «корень».
• Snowball (язык программирования) — предназначен для создания алгоритмов стемминга.
• Основа (лингвистика) — лингвистическое определение термина «основа».
• Анализ текста — алгоритмы стемминга играют важную роль в коммерческом программном обеспечении НЛП.

Дальнейшее чтение

• Доусон, Дж. Л. (1974); Удаление суффикса для объединения слов , Бюллетень Ассоциации литературных и лингвистических вычислений, 2 (3): 33–46
• Фрейкс, ВБ (1984); Объединение терминов для поиска информации , Издательство Кембриджского университета
• Фрейкс, ВБ и Фокс, СиДжей (2003); Сила и сходство алгоритмов стемминга удаления аффиксов , Форум SIGIR, 37: 26–30
• Фрейкс, ВБ (1992); Алгоритмы стемминга, Информационный поиск: структуры данных и алгоритмы , Аппер-Сэддл-Ривер, Нью-Джерси: Prentice-Hall, Inc.
• Хафер, Массачусетс и Вайс, С.Ф. (1974); Сегментация слов по разновидностям буквопреемников , Information Processing & Management 10 (11/12), 371–386
• Харман, Д. (1991); Насколько эффективно суффиксирование? , Журнал Американского общества информатики 42 (1), 7–15.
• Халл, Д.А. (1996); Алгоритмы стемминга – практический пример для детальной оценки , JASIS, 47(1): 70–84
• Халл Д.А. и Грефенстетт Г. (1996); Подробный анализ английских алгоритмов стемминга , технический отчет Xerox
• Краай В. и Полманн Р. (1996); «Рассмотрение стемминга как улучшения запоминания» , во Фрее, Х.-П.; Харман, Д.; Шойбле, П.; и Уилкинсон Р. (ред.); Материалы 17-й конференции ACM SIGIR, состоявшейся в Цюрихе 18–22 августа , стр. 40–48.
• Кровец, Р. (1993); Просмотр морфологии как процесса вывода , в Proceedings of ACM-SIGIR93 , стр. 191–203.
• Леннон, М.; Пирс, Д.С.; Тарри, Б.Д.; и Уиллетт, П. (1981); Оценка некоторых алгоритмов объединения для поиска информации , Журнал информатики, 3: 177–183.
• Ловинс, Дж. (1971); Оценка ошибок для алгоритмов стемминга как алгоритмов кластеризации , JASIS, 22: 28–40
• Ловинс, Дж. Б. (1968); Разработка стемминг-алгоритма , Механический перевод и компьютерная лингвистика, 11, 22—31
• Дженкинс, Мари-Клер; и Смит, Дэн (2005); Консервативная стемминг для поиска и индексирования
• Пейс, компакт-диск (1990); Другой Стеммер. Архивировано 22 июля 2011 г. на Wayback Machine , SIGIR Forum, 24: 56–61.
• Пейс, CD (1996) Метод оценки алгоритмов стемминга на основе подсчета ошибок , JASIS, 47(8): 632–649
• Попович, Мирко; и Уиллетт, Питер (1992); Эффективность стемминга для доступа к словенским текстовым данным на естественном языке , Журнал Американского общества информатики , том 43, выпуск 5 (июнь), стр. 384–390
• Портер, Мартин Ф. (1980); Алгоритм удаления суффиксов , Программа, 14(3): 130–137.
• Савой, Дж. (1993); Определение основы французских слов на основе грамматических категорий Журнал Американского общества информатики, 44 (1), 1–9
• Ульмшнайдер, Джон Э.; и Дошкоч, Тамаш (1983); Практический алгоритм стемминга для помощи в онлайн-поиске , Интернет-обзор, 7(4), 301–318
• Сюй, Дж.; и Крофт, Всемирный банк (1998); Корпусная стемминг с использованием совпадения вариантов слов , Транзакции ACM в информационных системах, 16 (1), 61–81

Внешние ссылки

• Apache OpenNLP — включает стеммеры Porter и Snowball.
• SMILE Stemmer — бесплатный онлайн-сервис, включающий стеммеры Porter и Paice/Husk Lancaster (Java API).
• Themis — IR-фреймворк с открытым исходным кодом, включает реализацию стеммера Porter (PostgreSQL, Java API).
• Snowball — бесплатные алгоритмы стемминга для многих языков, включая исходный код, включая стеммеры для пяти романских языков.
• Snowball on C# — порт стеммеров Snowball для C# (14 языков).
• Привязки Python к Snowball API
• Ruby-Stemmer — расширение Ruby для Snowball API.
• PECL — PHP-расширение API Snowball.
• Алгоритм Олеандра Портера — библиотека стемминга на C++, выпущенная под BSD.
• Неофициальная домашняя страница алгоритма стемминга Ловинса с исходным кодом на нескольких языках.
• Официальная домашняя страница алгоритма стемминга Портера , включая исходный код на нескольких языках.
• Официальная домашняя страница алгоритма стемминга Ланкастера. Архивировано 22 июля 2011 г. в Wayback Machine — Ланкастерский университет, Великобритания.
• Официальная домашняя страница UEA-Lite Stemmer — Университета Восточной Англии, Великобритания.
• Обзор алгоритмов стемминга. Архивировано 2 июля 2011 г. на Wayback Machine.
• PTStemmer — набор инструментов для стемминга Java/Python/.Net для португальского языка.
• jsSnowball — реализация алгоритмов стемминга Snowball на JavaScript с открытым исходным кодом для многих языков.
• Snowball Voices — реализация для Java
• Hindi_voices — голоса с открытым исходным кодом для хинди.
• czech_votes — голоса с открытым исходным кодом за чешский язык
• Сравнительная оценка морфологических анализаторов и стеммеров арабского языка
• Тамильские голоса