В лингвистической морфологии и информационном поиске стемминг — это процесс приведения склоняемых (или иногда производных) слов к их основе слова , базовой или корневой форме — как правило, письменной форме слова. Основа не обязательно должна быть идентична морфологическому корню слова; обычно достаточно, чтобы связанные слова отображались на ту же основу, даже если эта основа сама по себе не является допустимым корнем. Алгоритмы стемминга изучались в информатике с 1960-х годов. Многие поисковые системы рассматривают слова с той же основой как синонимы , что является своего рода расширением запроса , процессом, называемым конфляцией.
Компьютерная программа или подпрограмма, которая определяет основу слова, может называться программой стемминга , алгоритмом стемминга или стеммером .
Стеммер для английского языка, работающий с основой cat, должен определять такие строки , как cats , catlike и catty . Стемминговый алгоритм может также сводить слова fishing , fished и fisher к основе fish . Основа не обязательно должна быть словом, например, алгоритм Портера сводит argument , argumentd , arguments , arguing и argus к основе argu .
Первый опубликованный стеммер был написан Джули Бет Ловинс в 1968 году. [1] Эта статья примечательна своей ранней датой и оказала большое влияние на последующие работы в этой области. [ требуется ссылка ] Ее статья ссылается на три более ранние крупные попытки создания алгоритмов стемминга: профессора Джона В. Тьюки из Принстонского университета , алгоритма, разработанного в Гарвардском университете Майклом Леском под руководством профессора Джерарда Солтона , и третьего алгоритма, разработанного Джеймсом Л. Долби из R and D Consultants, Лос-Альтос, Калифорния.
Более поздний стеммер был написан Мартином Портером и опубликован в июльском выпуске журнала Program 1980 года . Этот стеммер использовался очень широко и стал фактическим стандартным алгоритмом, используемым для стемминга английского языка. Доктор Портер получил премию Тони Кента Стрикса в 2000 году за свою работу по стеммингу и информационному поиску.
Было написано и свободно распространялось множество реализаций алгоритма стемминга Портера; однако многие из этих реализаций содержали тонкие недостатки. В результате эти стеммеры не соответствовали своему потенциалу. Чтобы устранить этот источник ошибок, Мартин Портер выпустил официальную реализацию алгоритма в виде свободного программного обеспечения (в основном под лицензией BSD ) [2] примерно в 2000 году. Он расширил эту работу в течение следующих нескольких лет, создав Snowball , фреймворк для написания алгоритмов стемминга, и реализовал улучшенный английский стеммер вместе со стеммерами для нескольких других языков.
Стеммер Paice-Husk был разработан Крисом Д. Пейсом в Ланкастерском университете в конце 1980-х годов. Это итеративный стеммер, который имеет внешне сохраненный набор правил стемминга. Стандартный набор правил обеспечивает «сильный» стеммер и может указывать удаление или замену окончания. Метод замены позволяет избежать необходимости в отдельном этапе в процессе перекодирования или предоставления частичного соответствия. Пейс также разработал прямое измерение для сравнения стеммеров на основе подсчета ошибок избыточного и недостаточного стемминга.
Существует несколько типов алгоритмов стемминга, которые различаются по производительности и точности, а также по способу преодоления определенных препятствий при стемминге.
Простой стеммер ищет флективную форму в таблице поиска . Преимущества этого подхода в том, что он прост, быстр и легко обрабатывает исключения. Недостатки в том, что все флективные формы должны быть явно перечислены в таблице: новые или незнакомые слова не обрабатываются, даже если они совершенно правильные (например, cats ~ cat), и таблица может быть большой. Для языков с простой морфологией, таких как английский, размеры таблиц скромны, но в сильно флективных языках, таких как турецкий, могут быть сотни потенциальных флективных форм для каждого корня.
Подход к поиску может использовать предварительную маркировку частей речи , чтобы избежать избыточного стемминга. [3]
Таблица поиска, используемая стеммером, обычно создается полуавтоматически. Например, если слово "run", то инвертированный алгоритм может автоматически генерировать формы "running", "runs", "runned" и "runly". Последние две формы являются допустимыми конструкциями, но они маловероятны. [ необходима цитата ] .
Алгоритмы удаления суффиксов не полагаются на таблицу поиска, которая состоит из флективных форм и отношений корневой формы. Вместо этого обычно хранится меньший список «правил», который предоставляет алгоритму путь для поиска корневой формы при заданной входной форме слова. Вот некоторые примеры правил:
Подходы к удалению суффиксов имеют преимущество в том, что их гораздо проще поддерживать, чем алгоритмы грубой силы, предполагая, что сопровождающий достаточно осведомлен в проблемах лингвистики и морфологии и кодирования правил удаления суффиксов. Алгоритмы удаления суффиксов иногда считаются грубыми из-за плохой производительности при работе с исключительными отношениями (например, 'ran' и 'run'). Решения, полученные с помощью алгоритмов удаления суффиксов, ограничены теми лексическими категориями , которые имеют хорошо известные суффиксы с немногими исключениями. Это, однако, является проблемой, поскольку не все части речи имеют такой хорошо сформулированный набор правил. Лемматизация пытается улучшить эту проблему.
Также может быть реализовано удаление префиксов. Конечно, не все языки используют префиксы или суффиксы.
Алгоритмы удаления суффиксов могут различаться по результатам по разным причинам. Одной из таких причин является то, ограничивает ли алгоритм то, должно ли выходное слово быть реальным словом в данном языке. Некоторые подходы не требуют, чтобы слово действительно существовало в лексиконе языка (множестве всех слов в языке). В качестве альтернативы некоторые подходы удаления суффиксов поддерживают базу данных (большой список) всех известных морфологических корней слов, которые существуют как реальные слова. Эти подходы проверяют список на наличие термина перед принятием решения. Обычно, если термин не существует, выполняется альтернативное действие. Это альтернативное действие может включать несколько других критериев. Отсутствие выходного термина может послужить причиной того, что алгоритм попробует альтернативные правила удаления суффиксов.
Может быть так, что два или более правил удаления суффиксов применяются к одному и тому же входному термину, что создает неоднозначность относительно того, какое правило применять. Алгоритм может назначить (человеческим путем или стохастически) приоритет одному или другому правилу. Или алгоритм может отклонить одно применение правила, поскольку оно приводит к несуществующему термину, тогда как другое перекрывающееся правило не приводит. Например, учитывая английский термин friendlyies , алгоритм может определить суффикс ies и применить соответствующее правило, достигнув результата friendlyl . Friendl , скорее всего, не найден в лексиконе, и поэтому правило отклоняется.
Одним из усовершенствований по сравнению с базовым удалением суффиксов является использование замены суффикса. Подобно правилу удаления, правило замены заменяет суффикс альтернативным суффиксом. Например, может существовать правило, которое заменяет ies на y . То, как это влияет на алгоритм, зависит от конструкции алгоритма. Для иллюстрации алгоритм может определить, что применяются как правило удаления суффикса ies , так и правило замены суффикса. Поскольку правило удаления приводит к несуществующему термину в лексиконе, а правило замены — нет, вместо этого применяется правило замены. В этом примере friendlyies становится friendly вместо friendlyl' .
Если углубляться в детали, то распространенной методикой является применение правил циклическим образом (рекурсивно, как сказали бы специалисты по информатике). После применения правила замены суффикса в этом примере сценария выполняется второй проход для определения правил соответствия для термина friendly , где правило удаления ly , скорее всего, будет идентифицировано и принято. Подводя итог, friendly становится (через замену) friendly , который становится (через удаление) friend .
Этот пример также помогает проиллюстрировать разницу между подходом на основе правил и подходом грубой силы. В подходе грубой силы алгоритм будет искать дружественные слова в наборе из сотен тысяч флективных словоформ и в идеале находить соответствующую корневую форму friend . В подходе на основе правил три правила, упомянутые выше, будут применяться последовательно, чтобы сойтись на одном и том же решении. Есть вероятность, что подход грубой силы будет медленнее, поскольку алгоритмы поиска имеют прямой доступ к решению, в то время как подход на основе правил должен пробовать несколько вариантов и их комбинаций, а затем выбирать, какой результат кажется лучшим.
Более сложный подход к проблеме определения основы слова — лемматизация . Этот процесс включает в себя сначала определение части речи слова и применение различных правил нормализации для каждой части речи. Часть речи сначала определяется до попытки найти корень, поскольку для некоторых языков правила определения основы меняются в зависимости от части речи слова.
Этот подход в значительной степени зависит от получения правильной лексической категории (части речи). Хотя правила нормализации для определенных категорий пересекаются, определение неправильной категории или невозможность создания правильной категории ограничивают дополнительное преимущество этого подхода по сравнению с алгоритмами удаления суффиксов. Основная идея заключается в том, что если стеммер способен уловить больше информации о слове, к которому применяется стеммер, то он может применять более точные правила нормализации (которые, в отличие от правил удаления суффиксов, также могут изменять основу).
Стохастические алгоритмы подразумевают использование вероятности для определения корневой формы слова. Стохастические алгоритмы обучаются (они «учатся») на таблице отношений корневой формы к склоняемой форме для разработки вероятностной модели. Эта модель обычно выражается в форме сложных лингвистических правил, похожих по своей природе на правила удаления суффиксов или лемматизации. Стемминг выполняется путем ввода склоняемой формы в обученную модель и получения моделью корневой формы в соответствии с ее внутренним набором правил, что снова похоже на удаление суффиксов и лемматизацию, за исключением того, что решения, связанные с применением наиболее подходящего правила, или с тем, следует ли удалять семпл слова и просто возвращать то же самое слово, или следует ли последовательно применять два разных правила, применяются на том основании, что выходное слово будет иметь наибольшую вероятность быть правильным (то есть наименьшую вероятность быть неправильным, что обычно и измеряется).
Некоторые алгоритмы лемматизации являются стохастическими в том смысле, что, если дано слово, которое может принадлежать нескольким частям речи, каждой возможной части присваивается вероятность. Это может учитывать окружающие слова, называемые контекстом, или нет. Контекстно-свободные грамматики не учитывают никакой дополнительной информации. В любом случае после назначения вероятностей каждой возможной части речи выбирается наиболее вероятная часть речи, и оттуда к входному слову применяются соответствующие правила нормализации для получения нормализованной (корневой) формы.
Некоторые методы стемминга используют n-граммный контекст слова для выбора правильной основы слова. [4]
Гибридные подходы используют два или более подходов, описанных выше, в унисон. Простым примером является алгоритм дерева суффиксов, который сначала обращается к таблице поиска с использованием грубой силы. Однако вместо того, чтобы пытаться сохранить весь набор связей между словами в данном языке, таблица поиска остается небольшой и используется только для хранения небольшого количества «частых исключений», таких как «ran => run». Если слово не находится в списке исключений, примените удаление суффиксов или лемматизацию и выведите результат.
В лингвистике термин аффикс относится либо к префиксу , либо к суффиксу . Помимо работы с суффиксами, несколько подходов также пытаются удалить общие префиксы. Например, учитывая слово indefinitely , определите, что начальный «in» является префиксом, который можно удалить. Применяются многие из тех же подходов, упомянутых ранее, но называются affix stripping . Исследование affix stemming для нескольких европейских языков можно найти здесь. [5]
Такие алгоритмы используют базу данных основ (например, набор документов, содержащих основы слов). Эти основы, как упоминалось выше, не обязательно являются сами по себе допустимыми словами (а скорее общими подстроками, как "brows" в "browse" и в "browsing"). Чтобы выделить основу слова, алгоритм пытается сопоставить его с основами из базы данных, применяя различные ограничения, такие как относительная длина основы-кандидата в слове (так, например, короткий префикс "be", который является основой таких слов, как "be", "been" и "being", не будет считаться основой слова "beside"). [ необходима цитата ] .
Хотя большая часть ранних академических работ в этой области была сосредоточена на английском языке (со значительным использованием алгоритма Портера-Стеммера), были исследованы и многие другие языки. [6] [7] [8] [9] [10]
Иврит и арабский языки по-прежнему считаются сложными для исследования языками стемминга. Английские стеммеры довольно тривиальны (только с редкими проблемами, такими как "dries" - это форма третьего лица единственного числа настоящего времени глагола "dry", "axes" - это множественное число от "axe", а также "axis"); но стеммеры становится сложнее разрабатывать, поскольку морфология, орфография и кодировка символов целевого языка становятся более сложными. Например, итальянский стеммер сложнее английского (из-за большего количества глагольных флексий), русский - сложнее (больше склонений существительных ), еврейский - еще сложнее (из-за неконкатенативной морфологии , системы письма без гласных и требования удаления префиксов: еврейские основы могут состоять из двух, трех или четырех символов, но не больше) и т. д.
Многоязычный стемминг применяет морфологические правила двух или более языков одновременно вместо правил только для одного языка при интерпретации поискового запроса. Существуют коммерческие системы, использующие многоязычный стемминг. [ необходима цитата ]
В алгоритмах стемминга есть два измерения ошибок: перестемминг и недостемминг. Перестемминг — это ошибка, при которой два отдельных склоняемых слова имеют один и тот же корень, но не должны были быть — ложноположительный результат . Недостемминг — это ошибка, при которой два отдельных склоняемых слова должны иметь один и тот же корень, но не должны были быть — ложноотрицательный результат . Алгоритмы стемминга пытаются минимизировать каждый тип ошибок, хотя уменьшение одного типа может привести к увеличению другого.
Например, широко используемый стеммер Портера образует основы "universal", "university" и "universe" в "univers". Это случай избыточного стемминга: хотя эти три слова этимологически связаны, их современные значения находятся в совершенно разных областях, поэтому обращение с ними как синонимами в поисковой системе, скорее всего, снизит релевантность результатов поиска.
Примером подстрочника в стеммере Портера является "alumnus" → "alumnu", "alumni" → "alumni", "alumna"/"alumnae" → "alumna". Это английское слово сохраняет латинскую морфологию, и поэтому эти почти синонимы не смешиваются.
Стемминг используется как приблизительный метод группировки слов со схожим базовым значением. Например, текст, в котором упоминается «нарциссы», вероятно, тесно связан с текстом, в котором упоминается «нарцисс» (без s). Но в некоторых случаях слова с той же морфологической основой имеют идиоматические значения, которые не являются тесно связанными: пользователь, ищущий «маркетинг», не будет удовлетворен большинством документов, в которых упоминаются «рынки», но не «маркетинг».
Стеммеры могут использоваться как элементы в системах запросов, таких как поисковые системы в Интернете . Однако эффективность стемминга для систем запросов на английском языке вскоре оказалась довольно ограниченной, и это привело к тому, что ранние исследователи информационного поиска посчитали стемминг неактуальным в целом. [11] Вместо этого можно использовать альтернативный подход, основанный на поиске n-грамм , а не основ. Кроме того, стеммеры могут обеспечить большую выгоду в других языках, чем английский. [12] [13]
Стемминг используется для определения доменных словарей в доменном анализе . [14]
Многие коммерческие компании используют стемминг по крайней мере с 1980-х годов и создали алгоритмические и лексические стеммеры для многих языков. [15] [16]
Стиммеры Snowball сравнивались с коммерческими лексическими стеммерами с разными результатами. [17] [18]
Поиск Google принял морфологию слов в 2003 году. [19] Раньше поиск по слову «fish» не возвращал «fishing». Другие алгоритмы поиска программного обеспечения различаются в использовании морфологии слов. Программы, которые просто ищут подстроки, очевидно, найдут «fish» в «fishing», но при поиске «fishes» не найдут вхождений слова «fish».
Стемминг используется в качестве задачи предварительной обработки текстов перед выполнением их интеллектуального анализа.