Войти
В лингвистической морфологии и поиске информации основание - это процесс преобразования словоизмененных (или иногда производных) слов до их основы, основной или корневой формы - обычно письменной словоформы. Основа не обязательно должна быть идентичной морфологическому корню слова; Обычно достаточно, чтобы родственные слова отображались на одной основе, даже если эта основа сама по себе не является действительным корнем. Алгоритмы для стемминга изучаются в информатике с 1960-х годов. Многие поисковые системы рассматривают слова с той же основой, что и синонимы, как своего рода расширение запроса, процесс, называемый слиянием.
A компьютерная программа или подпрограмма, которая определяет начало слова, может называться программой выделения корней, алгоритмом выделения корней или стеммером.
Стеммер для английского языка, работающий со стеблем cat, должен идентифицировать такие строки как cats, catlike и catty. Алгоритм стебля может также сократить слова рыболовство, рыбалка и рыбак до стволовой рыбы. Основа не обязательно должна быть словом, например, алгоритм Портера сводит, спорит, спорит, спорит, спорит и спорит до основы аргумента.
Первый опубликованный стеммер был написан Джули Бет Ловинс в 1968 году. Эта статья была примечательна своей ранней датой и оказала большое влияние на более поздние работы в этой области.. В ее статье упоминаются три более ранние попытки остановить алгоритмы, сделанные профессором Джоном В. Тьюки из Принстонского университета, алгоритм, разработанный в Гарвардском университете Майкл Леск под руководством профессора Джерарда Солтона и третий алгоритм, разработанный Джеймсом Л. Долби из RD Consultants, Лос-Альтос, Калифорния.
Более поздний стеммер был написан Мартином Портером и опубликован в июльском выпуске журнала Program за 1980 год. Этот стеммер получил очень широкое распространение и стал де-факто стандартным алгоритмом для английского стемминга. Доктор Портер получил премию Тони Кента Стрикса в 2000 году за свою работу по поиску информации и поиску информации.
Многие реализации алгоритма выделения портера были написаны и свободно распространялись; однако многие из этих реализаций содержали незначительные недостатки. В результате эти стеммеры не соответствовали своему потенциалу. Чтобы устранить этот источник ошибки, Мартин Портер выпустил официальную бесплатное программное обеспечение (в основном с лицензией на BSD ) примерно в 2000 году. Он расширил эту работу на следующие несколько лет. путем создания Snowball, фреймворка для написания алгоритмов стемминга, и реализовал улучшенный стеммер английского языка вместе со стеммерами для нескольких других языков.
Стеммер Paice-Husk был разработан Крисом Д. Пэйсом в Ланкастерском университете в конце 1980-х годов. Это итеративный стеммер, содержащий хранимый извне набор правил стемминга. Стандартный набор правил предусматривает «сильный» стеммер и может указывать удаление или замену концовки. Метод замены позволяет избежать необходимости в отдельном этапе процесса для перекодирования или обеспечения частичного сопоставления. Пэйс также разработал прямое измерение для сравнения стволовых машин, основанное на подсчете ошибок чрезмерного и недостаточного ствола.
Существует несколько типов алгоритмов устранения препятствий, которые различаются по производительности и точности, а также по способам преодоления определенных препятствий при задержке.
Простой стеммер ищет измененную форму в таблице поиска. Преимущества этого подхода в том, что он простой, быстрый и легко обрабатывает исключения. Недостатки в том, что все изменяемые формы должны быть явно перечислены в таблице: новые или незнакомые слова не обрабатываются, даже если они совершенно правильные (например, cats ~ cat), а таблица может быть большой. Для языков с простой морфологией, таких как английский, размеры таблиц невелики, но сильно изменяемые языки, такие как турецкий, могут иметь сотни потенциальных изменяемых форм для каждого корня.
Подход поиска может использовать предварительную маркировку части речи, чтобы избежать чрезмерного разбиения.
Таблица поиска, используемая стеммером обычно производится полуавтоматически. Например, если используется слово «запустить», то инвертированный алгоритм может автоматически генерировать формы «выполняется», «выполняется», «выполняется» и «выполняется». Последние две формы являются допустимыми конструкциями, но маловероятны.
Алгоритмы удаления суффиксов не полагаются на таблицу поиска, которая состоит из изменяемых форм и отношений корневых форм. Вместо этого обычно сохраняется меньший список «правил», который обеспечивает путь для алгоритма с учетом входной формы слова, чтобы найти его корневую форму. Некоторые примеры правил включают:
Подходы к удалению суффиксов имеют то преимущество, что их гораздо проще поддерживать, чем алгоритмы грубой силы, при условии, что сопровождающий достаточно хорошо осведомлен в проблемах лингвистики, морфологии и суффикса кодирования правила зачистки. Алгоритмы удаления суффиксов иногда рассматриваются как грубые из-за низкой производительности при работе с исключительными отношениями (например, «выполнено» и «выполнено»). Решения, получаемые с помощью алгоритмов удаления суффиксов, ограничиваются теми лексическими категориями, которые имеют хорошо известные суффиксы за некоторыми исключениями. Однако это является проблемой, поскольку не все части речи имеют такой хорошо сформулированный набор правил. Лемматизация пытается улучшить эту проблему.
Также может быть реализовано удаление префикса. Конечно, не во всех языках используются префиксы или суффиксы.
Алгоритмы удаления суффиксов могут отличаться в результатах по разным причинам. Одна из таких причин заключается в том, ограничивает ли алгоритм, должно ли выходное слово быть реальным словом на данном языке. Некоторые подходы не требуют, чтобы слово действительно существовало в языковой лексике (совокупности всех слов в языке). В качестве альтернативы, некоторые подходы к удалению суффиксов поддерживают базу данных (большой список) всех известных морфологических корней слов, которые существуют как настоящие слова. Эти подходы проверяют список на наличие термина до принятия решения. Обычно, если термин не существует, предпринимаются альтернативные действия. Это альтернативное действие может включать несколько других критериев. Отсутствие выходного термина может привести к тому, что алгоритм попробует использовать альтернативные правила удаления суффиксов.
Может случиться так, что два или более правила удаления суффиксов применяются к одному и тому же входному термину, что создает неоднозначность в отношении того, какое правило применять. Алгоритм может назначать (вручную или стохастически) приоритет тому или иному правилу. Или алгоритм может отклонить одно применение правила, потому что это приводит к несуществующему термину, тогда как другое перекрывающееся правило - нет. Например, учитывая английский термин friendlylies, алгоритм может определить суффикс ies, применить соответствующее правило и получить результат friendl. Friendl, скорее всего, не найден в лексиконе, и поэтому правило отклоняется.
Одним из усовершенствований по сравнению с удалением основного суффикса является использование замены суффикса. Подобно правилу удаления, правило замещения заменяет суффикс альтернативным суффиксом. Например, может существовать правило, заменяющее ies на y. Как это влияет на алгоритм, зависит от его конструкции. Чтобы проиллюстрировать, алгоритм может определять, что применяются как правило удаления суффикса ies, так и правило замены суффикса. Так как правило исключения приводит к тому, что термин в лексиконе не существует, а правило замены - нет, вместо этого применяется правило замены. В этом примере товарищеские матчи становятся дружескими, а не товарищескими.
Углубляясь в детали, можно сказать, что распространенный метод - применять правила циклически (рекурсивно, как сказали бы компьютерщики). После применения правила подстановки суффиксов в этом примере сценария выполняется второй проход, чтобы определить правила сопоставления для термина дружественный, где правило удаления ly, вероятно, идентифицировано и принято. Таким образом, товарищеские матчи становятся дружественными (через замену), которые становятся друзьями (через удаление).
Этот пример также помогает проиллюстрировать разницу между подходом, основанным на правилах, и подходом грубой силы. В подходе грубой силы алгоритм будет искать дружественные слова в наборе из сотен тысяч словоформ с изменяемой формой слова и в идеале находить соответствующую корневую форму friend. В подходе, основанном на правилах, три упомянутых выше правила будут применяться последовательно, чтобы прийти к одному и тому же решению. Скорее всего, метод грубой силы будет медленнее, так как алгоритмы поиска имеют прямой доступ к решению, тогда как на основе правил следует попробовать несколько вариантов и их комбинации, а затем выбрать, какой результат кажется лучшим.
Более сложный подход к проблеме определения основы слова - лемматизация. Этот процесс включает в себя сначала определение части речи слова и применение разных правил нормализации для каждой части речи. Часть речи сначала обнаруживается до попытки найти корень, поскольку для некоторых языков правила выделения корней меняются в зависимости от части речи слова.
Такой подход в значительной степени зависит от получения правильной лексической категории (части речи). Хотя правила нормализации для определенных категорий частично совпадают, определение неправильной категории или невозможность создания правильной категории ограничивает дополнительное преимущество этого подхода по сравнению с алгоритмами удаления суффиксов. Основная идея состоит в том, что, если стеммер способен уловить больше информации о слове, которое выделяется, он может применять более точные правила нормализации (которые, в отличие от правил удаления суффиксов, также могут изменять основу).
Стохастические алгоритмы включают использование вероятности для определения корневой формы слова. Стохастические алгоритмы обучаются (они «учатся») на таблице отношений корневой формы к измененной форме для разработки вероятностной модели. Эта модель обычно выражается в форме сложных лингвистических правил, похожих по своей природе на правила удаления суффиксов или лемматизации. Стемминг выполняется путем ввода измененной формы в обученную модель и создания модели корневой формы в соответствии со своим внутренним набором правил, что опять же похоже на удаление суффиксов и лемматизацию, за исключением того, что решения, связанные с применением наиболее подходящего правила, или или не ограничивать слово и просто возвращать одно и то же слово, или применять ли два разных правила последовательно, применяются на том основании, что выходное слово будет иметь наибольшую вероятность быть правильным (то есть наименьшую вероятность того, что неверно, как это обычно бывает).
Некоторые алгоритмы лемматизации являются стохастическими в том смысле, что каждому слову, которое может принадлежать нескольким частям речи, присваивается вероятность. При этом могут учитываться окружающие слова, называемые контекстом, или нет. Бесконтекстные грамматики не принимают во внимание дополнительную информацию. В любом случае после присвоения вероятностей каждой возможной части речи выбирается наиболее вероятная часть речи, и оттуда соответствующие правила нормализации применяются к входному слову для получения нормализованной (корневой) формы.
Некоторые методы выделения корней используют n-грамм контекст слова, чтобы выбрать правильную основу для слова.
Гибридные подходы используют два или более подходов, описанных выше, в унисон. Простым примером является алгоритм суффиксного дерева, который сначала обращается к таблице поиска с использованием грубой силы. Однако вместо того, чтобы пытаться сохранить весь набор отношений между словами на данном языке, таблица поиска остается небольшой и используется только для хранения небольшого количества «частых исключений», таких как «run =>run». Если слово отсутствует в списке исключений, примените удаление суффикса или лемматизацию и выведите результат.
В лингвистике термин аффикс относится либо к префиксу , либо к суффиксу . Помимо работы с суффиксами, несколько подходов также пытаются удалить общие префиксы. Например, для слова "неопределенно" укажите, что начальный "in" - это префикс, который можно удалить. Применяются многие из тех же подходов, упомянутых ранее, но под названием удаление аффиксов . Исследование создания основы аффиксов для нескольких европейских языков можно найти здесь.
Такие алгоритмы используют основную базу данных (например, набор документов, содержащих основные слова). Эти основы, как упоминалось выше, не обязательно сами по себе являются допустимыми словами (скорее, это обычные подстроки, такие как «брови» в «просмотре» и «просмотре»). Чтобы выделить слово, алгоритм пытается сопоставить его с основами из базы данных, применяя различные ограничения, такие как относительная длина основы-кандидата в слове (так, чтобы, например, короткий префикс «быть», который является основой таких слов, как «быть», «был» и «быть», не может рассматриваться как основа слова «рядом»)..
Хотя большая часть ранней академической работы в этой области была сосредоточена на английском языке (со значительным использованием алгоритма Портера Стеммера), многие другие языки были исследованы.
Иврит и арабский до сих пор считаются сложными для исследования языками для определения. Английские стеммеры довольно тривиальны (только изредка возникают проблемы, например, «dries» - это форма третьего лица единственного числа от глагола «dry», «axes» - множественное число от «ax», так и от «axis»); но разработка стеммеров становится все труднее, поскольку морфология, орфография и кодировка символов целевого языка становятся более сложными. Например, итальянский стеммер сложнее английского (из-за большего количества глагольных перегибов), русский - сложнее (больше существительных склонений ), ивритский еще сложнее ( из-за неконкатенативной морфологии, системы письма без гласных и требования удаления префиксов: основы иврита могут состоять из двух, трех или четырех символов, но не более) и т. д.
Многоязычное выделение корней применяет морфологические правила двух или более языков одновременно вместо правил только для одного языка при интерпретации поискового запроса. Существуют коммерческие системы, использующие многоязычное выделение стеблей.
В алгоритмах выделения стемминга есть два способа измерения ошибок: оверсемминг и подтемминг. Оверстемминг - это ошибка, при которой два отдельных флективных слова связаны с одним и тем же корнем, но не должно быть - ложное срабатывание. Подчеркивание - это ошибка, при которой два отдельных слова с изменяемой наклонностью должны быть связаны с одним корнем, но это не так - ложноотрицательный. Алгоритмы вывода пытаются минимизировать каждый тип ошибки, хотя уменьшение одного типа может привести к увеличению другого.
Например, широко используемый стеммер Портера переводит слова «универсальный», «университет» и «вселенная» в «универсальный». Это случай чрезмерного разбора: хотя эти три слова этимологически связаны, их современные значения находятся в самых разных областях, поэтому рассмотрение их как синонимов в поисковой системе, вероятно, снизит релевантность результатов поиска.
Примером нижнего стеммера в стеммере Портера является «выпускник» → «выпускник», «выпускник» → «выпускник», «выпускник» / «выпускники» → «выпускник». Это английское слово сохраняет латинскую морфологию, поэтому эти почти синонимы не объединяются.
Основание используется как приблизительный метод для группировки слов с похожим основным значением вместе. Например, текст, в котором упоминается «нарциссы», вероятно, тесно связан с текстом, в котором упоминается «нарциссы» (без букв s). Но в некоторых случаях слова с одной и той же морфологической основой имеют идиоматические значения, которые не связаны между собой: пользователь, вводящий слово «маркетинг», не будет удовлетворен большинством документов, в которых упоминается «рынки», но не «маркетинг».
Стеммеры являются обычными элементами в системах запросов, таких как Web поисковых системах. Однако вскоре было обнаружено, что эффективность корчевания для английских систем запросов довольно ограничена, и это привело к тому, что ранние исследователи информационного поиска сочли устранение несущественным в целом. Вместо этого может использоваться альтернативный подход, основанный на поиске n-граммов, а не основ. Кроме того, стеммеры могут дать больше преимуществ для других языков, чем английский.
Стемминг используется для определения словарей предметной области в анализе предметной области.
Многие коммерческие компании использовали стемминг по крайней мере с 1980-х годов и создали алгоритмические и лексические стеммеры на многих языках.
Стеммеры Snowball сравнивали с коммерческими лексическими стеммерами с различными
Поиск Google принял определение корней слова в 2003 году. Раньше поиск по запросу «рыба» не возвращал бы «рыбалка». Другие программные алгоритмы поиска различаются по использованию корней слов. Программы, которые просто ищут подстроки, очевидно, найдут «рыба» в «рыбалка», но при поиске «рыбы» не найдут вхождений слова «рыба».
Эта статья основана на материалах, взятых из Free On-line Dictionary of Computing до 1 ноября 2008 г. и включенных в соответствии с условиями «перелицензирования» GFDL, версия 1.3 или новее.
