Прослушать этот блог в виде подкаста: Ваше устройство не поддерживает элемент аудиоплеера.
Прослушать этот блог в виде подкаста:
Примерное время чтения: 3 минуты
Термин «нечеткий поиск» имеет несколько значений, и все они сводятся к идее приблизительного сопоставления. Наиболее распространенное понимание этого термина связано с нечетким сопоставлением строк, когда поисковая система сопоставляет слова, которые не совпадают полностью. Классический пример — опечатки, когда запросы с ошибками выдают результаты с правильным написанием. Но понятие нечеткости не ограничивается исправлением опечаток, как вы увидите далее. Например, оно также может исправлять плохо сформулированные запросы, распознавать разговорную лексику, расширять префиксы или устанавливать слабые категориальные связи между запросом и искомым контентом.
Нечеткое сопоставление, описанное в этой статье, позволяет поисковой системе применять некоторые (слегка) неточные методы сопоставления, чтобы гарантировать выдачу всех релевантных результатов. В этом смысле релевантность — не точная наука.
Релевантность поиска в целом
Отправной точкой для поиска является текстовое сопоставление, которое сопоставляет точные символы, буквы и слова запроса с записями в наборе данных. Допустим, вы ищете «лодку», поисковая система выдаст все записи со словом «лодка». Не «каноэ» и не «круизный лайнер».
Текстовое сопоставление имеет большой потенциал. При хороших данных запрос «лодка» выдаст каждую релевантную запись, если в ней содержится слово «лодка», например, в заголовках, описаниях и категориях. При еще более умных данных, когда вы ищете «лодку», поисковая система может выдать все, что плавает, а также уроки гребли или круизный отдых.
Но что, если слово «лодка» не встречается в записях, хотя данные содержат информацию, связанную с лодками? Здесь на помощь приходят синонимы. Но что, если кто-то хочет найти «каноэ» и закономерно пишет его как «каноу»? Без учета опечаток поисковая система не выдала бы никаких результатов.
Нечеткое сопоставление направлено на повышение релевантности, делая ее и весь процесс поиска еще более интуитивными. При правильном применении нечеткое сопоставление органично объединяет тесно связанные элементы, игнорирование которых было бы серьезной упущенной возможностью. Подобно сбору пазла, нечеткий поиск собирает похожие элементы, чтобы помочь вам найти именно ту самую деталь. Кроме того, поскольку люди уточняют свои потребности в процессе поиска, нечеткий поиск предлагает варианты на основе сходства, подобно дегустации блюд перед заказом самого лучшего из них.
Инструменты поиска, такие как Algolia (нечеткий поиск с допуском опечаток), Elastic (нечеткий поиск), Coveo (нечеткий поиск) и Constructor.io (правила нечеткого поиска), предлагают функции нечеткого сопоставления. Все они подходят к этому вопросу по-разному. Мы рассмотрим разнообразие методов Algolia.
Определения нечеткого поиска и нечеткого сопоставления
Что такое нечеткий поиск?
Приблизительное сопоставление строк в противовес точному сопоставлению строк. Нечеткий поиск сопоставляет два или более слов, даже если в них есть опечатки или орфографические ошибки. Нечеткий поиск решает проблемы неуклюжих пальцев, спешащих и невнимательных пользователей, мобильных пользователей, а также сложности правописания на любом языке мира. Нечеткий поиск также может играть роль в сопоставлении данных, создаваемых пользователями, которые, как правило, ненадежны, поскольку пользователи делают опечатки и используют альтернативные или локализованные варианты написания одних и тех же слов. Сюда также может входить сопоставление на основе фонетики и звучания.
Другие названия нечеткого поиска: нечеткое или приблизительное сопоставление строк.
Примеры:
- Введите «helo», найдите записи с «hello»
- Введите «help», найдите записи с help и hello
Смотрите больше примеров и описание того, как это делается, ниже.
Что такое нечеткое сопоставление?
Расширяет нечеткость поиска, включая поиск информации на основе сходства. Нечеткое сопоставление — это широкий термин, поэтому мы будем говорить только о языковых сходствах, таких как синонимы, грамматика (множественное число, спряжение глаголов, окончания существительных и т. д.), словарные методы и другие эвристические методы или методы NLP. Ниже мы также включим сходства, обычно используемые поисковыми системами, такие как сопоставление частей слов, фраз или запросов, а также использование фильтров.
Примеры:
- Введите «pants», найдите pants, trousers, slacks (синонимы)
- Введите «be», найдите Beatles, bees (поиск по префиксу)
Смотрите больше примеров и описание того, как это делается, ниже.
Другие варианты использования «нечеткости»
- Нечеткие множества группируют слова (и объекты) на основе общих характеристик. Например, форма американского футбольного мяча, мяча для регби и яйца делает эти предметы более или менее похожими (продолговатая форма), но футбол и регби ближе друг к другу, поскольку они также обладают качествами прыгучести и спорта (не считая игры с яйцом в ложке).
- Нечеткая логика строит логические отношения на основе относительной близости, а не бинарных понятий вроде «истина» и «ложь» (два объекта соответствуют друг другу на том основании, что оба они «высокие», а не имеют абсолютно одинаковый рост).
Обратите внимание, что мы исключаем любое нечеткое сопоставление на основе семантики, машинного обучения или статистических методов вроде TF-IDF.
Нечеткий поиск с использованием допуска опечаток
Допуск опечаток позволяет пользователям совершать ошибки при наборе текста и все равно находить нужные записи. Это достигается путем сопоставления слов, близких по написанию.
Что именно представляет собой опечатка?
- Пропущенная буква в слове: «strm» → «storm»
- Лишняя буква: «stoorm» → «storm»
- Переставленные местами буквы: «strom» → «storm»
- Замененная буква: «storl» → «storm»
Алгоритм расстояния правописания (расстояние Дамерау — Левенштейна)
Алгоритм допуска опечаток в Algolia основан на расстоянии, в соответствии с алгоритмом расстояния Дамерау — Левенштейна. Расстояние относится к разнице в написании между набранным словом и его точным совпадением в индексе. Расстояние имеет точное значение: это минимальное количество операций (добавление, удаление, замена или перестановка символов), необходимых для превращения одного слова в другое. Идеальное совпадение имеет расстояние = 0. Когда есть идеальное совпадение или расстояние невелико (одна или две буквы введены ошибочно), происходит совпадение, и запись добавляется в результаты.
Например, если поисковая система получает слово вроде «strm», это может означать «storm» или «strum» (расстояние = 1 / одна буква неверна), либо «star» или «warm» (расстояние = 2 / две буквы неверны).
Расстояние устанавливает порог допуска. Порог установлен на уровне 2: когда слово имеет расстояние в 3 или более ошибок, оно «не допускается» (не включается в результаты).
Другие примеры нечеткого поиска на основе допуска опечаток
Ниже приведено несколько примеров того, как Algolia подсчитывает операции, необходимые для преобразования слова с целью поиска записей с именем «Michael»:
Ранжирование и допуск опечаток
С точки зрения релевантности: все нечеткие сопоставления на основе различий в написании считаются менее релевантными, чем точные совпадения. Таким образом, записи с расстоянием 0, то есть точные совпадения, ранжируются (упорядочиваются) выше, чем записи с опечатками. Аналогично, записи с 1 опечаткой ранжируются выше, чем записи с 2 опечатками.
Нечеткое сопоставление с синонимами
Нечеткое сопоставление должно позволять пользователям писать так, как они говорят, и использовать собственный словарный запас. Один из способов добиться этого — использование синонимов.
Синонимы указывают движку, какие слова и выражения следует считать эквивалентными — например, брюки = штаны. Таким образом, поиск по слову «штаны» вернет и «штаны», и «брюки», а поиск по слову «брюки» также вернет и «брюки», и «штаны».
Синонимы могут управляться словарем. Вы можете использовать тезаурус. Тем не менее, алгоритм поиска на основе тезауруса неприменим, так как он возвращает слишком много похожих результатов. У каждого слова в тезаурусе есть множество синонимов, что полезно для писателей, но не для запроса очень специфического набора данных. Например, у слова «слаксы» может быть несколько значений (безделье, свободный, низкая активность), и для каждого — несколько синонимов. Но в индексе магазина одежды единственными релевантными синонимами для «слаксов» являются «брюки» и «штаны».
Наконец, поисковые системы могут со временем обнаруживать общие синонимы с помощью машинного обучения, создавая таким образом динамический список релевантных синонимов.
Другие методы нечеткого поиска
Совпадение части слова с помощью префиксного поиска
Поиск по префиксу играет центральную роль в функции поиска Algolia «на ходу» (as-you-type). Он позволяет движку начинать сопоставление записей на основе частей слов.
Например, записи, содержащие «абрикос», возвращаются, как только пользователь вводит «а», «аб», «абр». Движку не нужно ждать совпадения слова целиком перед отображением результатов.
Гибкое сопоставление строк путем поиска в середине слова («содержит»)
Запрос может быть настроен на сопоставление и ранжирование записей на основе позиции слова в атрибуте записи. Другими словами, совпадение может начинаться в середине атрибута.
- Запрос «hiking» соответствует записи: «Backpacks used for hiking and traveling».
Совпадение части фразы с необязательными словами
Обычно для того, чтобы запись соответствовала запросу, она должна содержать все слова из запроса. Создавая список необязательных слов, вы можете находить записи, которые соответствуют только некоторым из слов.
- Запрос «backpacks hiking» соответствует записям в магазине, который продает только рюкзаки. Магазин может захотеть удалить слово «backpacks» из запроса (сделав его тем самым необязательным словом), поскольку они не используют слово «backpack» в названии товара, но при этом они не хотят упустить хорошие результаты, если кто-то случайно включит его в запрос.
Удаление слов при отсутствии результатов
Поисковая система может начать удалять слова, если полная фраза не дает результатов.
- Запрос «hiking backpacks heavy clothing», ни одна запись не совпадает (слишком много слов), поэтому движок удаляет «heavy clothing» и находит рюкзаки, используемые для пешего туризма.
Нечеткая группировка на основе надежной фильтрации и фасетирования
Фильтрация лежит в основе всех поисковых систем, так же как и фасетирование — интерфейсная сторона фильтрации. Добавление характеристик к вашим данным (таких как бренд, жанр) имеет решающее значение для любого поиска, обзора и поиска информации. Тегирование записей созданными пользователями категориями и вашим собственным глубоким пониманием данных создает более богатую комбинацию результатов на основе нечеткой группировки, описанной выше.
Кроме того, синтаксис фильтров «AND» и «OR» расширяет группировку контента, позволяя движку объединять записи с множественными сходствами и различиями.
Необязательные фильтры и скоринг фильтров
Необязательная фильтрация ведет себя как обычные фильтры, то есть она возвращает записи, которые соответствуют как запросу, так и фильтрам. Однако она также возвращает записи, которые не соответствуют фильтрам. Это влияет на ранжирование: записи, соответствующие фильтрам, занимают более высокие позиции, чем записи, не соответствующие фильтрам. Если вы используете отрицательные фильтры, элементы, соответствующие вашему фильтру, ранжируются ниже остальных записей.
Скоринг фильтров позволяет привлекать больше записей, но контролирует ранжирование так, чтобы нечеткие совпадения находились ниже точных.
Итак... Как же обуздать множество всех этих нечетких поисков и сопоставлений?
Добавление нечеткой логики, несмотря на ее мощность, сопряжено с определенным риском. Она может возвращать слишком много результатов, чтобы пользователь мог их просеять, или может выдавать неожиданные результаты, которые, по мнению пользователя, нарушают релевантность результатов.
Задача поисковой системы — ограничить влияние этого расширения информации. Например, отдавая более высокий приоритет точным совпадениям, гарантируя, что точные совпадения появляются вверху результатов, выше нечетких:
- В случае опечаток точные совпадения считаются более релевантными, чем неточные (даже если опечатка очевидна для пользователя).
- В случае синонимов точные совпадения более релевантны, чем совпадения по синонимам (даже если слово в запросе имеет несколько значений, а синоним был бы лучшим выбором).
По сути, движки подстраховывают алгоритм нечеткого поиска, отображая нечеткие совпадения после точных.
Существует также множество паттернов пользовательского интерфейса для управления этим. Например, Google и другие поисковые системы добавляют «предложенные варианты написания» прямо под строкой поиска. Или они предлагают функцию автозаполнения или подсказок запросов, когда пользователю в выпадающем списке по мере ввода предлагаются варианты запросов (и категорий), которые он может выбрать.
Но правильное решение скрывается под поверхностью, оставаясь абсолютно прозрачным для пользователя: поисковая система возвращает результаты, которые создают у пользователя интуитивное ощущение, что показанные элементы являются лучшими и наиболее релевантными результатами — даже если они не полностью совпадают с текстом запроса.
