Стебель - Stemming

Чтобы узнать о технике катания на лыжах, см. Ствол (катание на лыжах) . Информацию о технике лазания см. В Глоссарии терминов по лазанию § ствол .

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

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

Примеры

Стеммер для английского языка, работающий со стеблем cat, должен определять такие строки, как cats , catlike и catty . Алгоритм может также вытекающий уменьшить слова рыбалки , ловила рыбу , и рыболов к стеблевой рыбе . Ствол не должно быть слово, например, Porter алгоритм сводится, утверждают , утверждал , утверждает , споря , и Аргус к стеблевой argu .

История

Первый опубликованный стеммер был написан Джули Бет Ловинс в 1968 году. Эта статья была примечательна своей ранней датой и оказала большое влияние на более поздние работы в этой области. Ее статья относится к трем ранее крупных попыток , обусловленных алгоритмов, профессор Джон У. Тьюки из Принстонского университета , алгоритм , разработанный в Гарвардском университете по Майкл Lesk , под руководством профессора Жерара Salton , а третий алгоритм , разработанный Джеймсом Л. Dolby консультантов по исследованиям и разработкам, Лос-Альтос, Калифорния.

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

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

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

Алгоритмы

Нерешенная проблема в информатике :

Есть ли какой-нибудь идеальный алгоритм стемминга на английском языке?

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

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

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

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

Техника производства

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Прикрепить стеммеры

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

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

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

Языковые проблемы

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

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

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

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

Показатели ошибок

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

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

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

Приложения

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

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

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

Анализ предметной области

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

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

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

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

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

Смотрите также

использованная литература

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

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

Эта статья основана на материалах, взятых из Free On-line Dictionary of Computing до 1 ноября 2008 г. и включенных в соответствии с условиями «перелицензирования» GFDL версии 1.3 или новее.