Толерантный и подстановочный поиск

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

Definition

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

Scope

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

Core questions

• Как запросы с подстановочными символами, такие как префиксные, суффиксные и инфиксные шаблоны, оцениваются по словарю?
• Как пермутермные и k-граммные индексы поддерживают поиск с подстановочными символами?
• Как находится ближайший правильно написанный термин для ошибочного термина запроса?
• Как редакционное (Левенштейна) расстояние количественно определяет разницу между двумя строками?
• Как фонетическое сопоставление, такое как Soundex, группирует термины, которые звучат похоже?

Key concepts

• запрос с подстановочными символами
• пермутермный индекс
• k-граммный индекс
• редакционное (Левенштейна) расстояние
• исправление орфографии
• фонетическое сопоставление (Soundex)
• приблизительное сопоставление строк
• генерация терминов-кандидатов

Key theories

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

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

Исправление орфографии по редакционному расстоянию

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

Clinical relevance

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

History

Приблизительное сопоставление и исправление орфографии имеют давнюю историю в вычислительной технике, при этом Soundex датируется началом XX века и использовался для индексации записей. Обзор Кукич 1992 года объединил методы автоматического исправления орфографии, а обзор Наварро 2001 года систематизировал приблизительное сопоставление строк. Эти методы стали стандартными компонентами поисковых словарей, поскольку веб-поиск сделал необходимым гибкую обработку запросов.

Key figures

• Karen Kukich
• Gonzalo Navarro

Seminal works

• manning2008
• kukich1992
• navarro2001

Frequently asked questions

Как поисковая система обрабатывает подстановочный символ, такой как «comput*»?

Она использует вспомогательную словарную структуру, такую как пермутермный или k-граммный индекс, чтобы найти все термины, соответствующие шаблону (computer, computing, computation и так далее), а затем оценивает исходный запрос, как если бы эти термины были перечислены явно.

Что такое редакционное расстояние и почему оно используется для исправления орфографии?

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