Слушайте этот блог в формате подкаста: Ваш браузер не поддерживает аудиоэлемент.
Слушайте этот блог в формате подкаста:
Примерное время чтения: 3 минуты
Термин «нечеткий поиск» (fuzzy search) имеет несколько значений, каждое из которых вращается вокруг идеи приблизительного сопоставления. Наиболее распространенное понимание этого термина связано с нечетким сопоставлением строк, когда поисковая система находит слова, которые не совпадают в точности. Классический пример — опечатки, когда запросы с ошибками приводят к результатам с правильным написанием. Но, как вы увидите, нечеткость — это не только исправление опечаток. Например, она также может исправлять плохо сформулированные запросы, распознавать разговорную лексику, расширять префиксы или выстраивать свободные категориальные связи между запросом и искомым контентом.
Нечеткое сопоставление, описанное в этой статье, позволяет поисковой системе применять некоторые (слегка) неточные методы сопоставления, чтобы гарантировать возврат всех релевантных результатов. В этом смысле релевантность не является точной наукой.
Релевантность поиска в целом
Отправной точкой для поиска является текстовое сопоставление, которое соотносит точные символы, буквы и слова запроса с записями в наборе данных. Скажем, вы ищете «лодка», поисковая система вернет все записи, содержащие слово «лодка». Не «каноэ» и не «круизный лайнер».
Текстовое сопоставление очень эффективно. При наличии качественных данных запрос «лодка» вернет каждую релевантную запись, если она содержит слово «лодка», например, в заголовках, описаниях и категориях. При еще более «умных» данных, когда вы ищете «лодку», поисковая система может вернуть все, что плавает, а также уроки катания на лодках или круизные туры.
Но что, если слово «лодка» не встречается в записях, хотя данные содержат информацию, связанную с лодками? Здесь на помощь приходят синонимы. А что, если кто-то хочет найти «каноэ» и пишет его как «каноу»? Без учета опечаток поисковая система не выдаст никаких результатов.
Нечеткое сопоставление направлено на повышение релевантности, делая релевантность и общий опыт поиска еще более интуитивно понятными. При правильном выполнении нечеткое сопоставление органично объединяет близкие по смыслу элементы, в противном случае это было бы серьезной потерей возможностей. Подобно сборке пазла, нечеткий поиск собирает похожие фрагменты, чтобы помочь вам найти именно тот, который нужен. Кроме того, поскольку люди определяют, что им нужно, в процессе поиска, нечеткий поиск предлагает варианты, основанные на сходстве, подобно дегустации перед заказом лучшего блюда.
Инструменты поиска, такие как 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 опечатками.
Нечеткое сопоставление с синонимами
Нечеткое сопоставление должно позволять пользователям писать так, как они говорят, и использовать свой собственный словарный запас. Один из способов достичь этого — использование синонимов.
Синонимы сообщают поисковому движку, какие слова и выражения следует считать эквивалентными — например, «брюки» = «штаны». Таким образом, поиск по запросу «штаны» вернет результаты как для «штанов», так и для «брюк», а поиск по запросу «брюки» также вернет результаты для обоих вариантов.
Синонимы могут быть основаны на словарях. Вы можете использовать тезаурус. Однако алгоритм поиска, основанный на тезаурусе, непригоден для использования, так как он будет выдавать слишком много похожих результатов. У каждого слова в тезаурусе есть множество синонимов, что полезно для писателей, но не для выполнения запросов к очень специфическому набору данных. Например, слово «слакс» может иметь несколько значений (лень, свободный, низкая активность), и для каждого из них — несколько синонимов. Но в индексе магазина одежды единственными релевантными синонимами для «слаксов» являются «брюки» и «штаны».
Наконец, поисковые системы могут со временем обнаруживать распространенные синонимы с помощью машинного обучения, создавая таким образом динамический список релевантных синонимов.
Другие методы нечеткого сопоставления
Частичное сопоставление слов с помощью поиска по префиксу
Сопоставление по префиксу является центральным элементом функции поиска «на лету» (as-you-type) в Algolia. Оно позволяет движку начинать сопоставление записей на основе части слов.
Например, записи, содержащие слово «абрикос», возвращаются, как только пользователь вводит «а», «аб», «абри». Движку не нужно ждать ввода полного слова, чтобы отобразить результаты.
Гибкое сопоставление строк путем поиска в середине слова («содержит»)
Запрос можно настроить так, чтобы он находил и ранжировал записи на основе позиции слова внутри атрибута записи. Другими словами, совпадение может начинаться с середины атрибута.
- Запрос «поход» совпадает с записью: «Рюкзаки для походов и путешествий».
Частичное сопоставление фраз с помощью необязательных слов
Обычно для того, чтобы запись соответствовала запросу, она должна содержать все слова из него. Создав список необязательных слов, вы можете находить записи, которые соответствуют лишь некоторым из этих слов.
- Запрос «рюкзаки для походов» находит записи в магазине, который продает только рюкзаки. Магазин может захотеть удалить слово «рюкзаки» из запроса (сделав его необязательным), потому что они не используют слово «рюкзак» в названии товара, но при этом не хотят упустить хорошие результаты, если кто-то случайно включит это слово в запрос.
Удаление слов при отсутствии результатов
Поисковая система может начать удалять слова, если полная фраза не дает результатов.
- Запрос «походные рюкзаки тяжелая одежда» не дает совпадений (слишком много слов), поэтому движок удаляет «тяжелая одежда» и находит рюкзаки, используемые для походов.
Нечеткая группировка на основе надежной фильтрации и фасетирования
Фильтрация является базовой функцией для всех поисковых систем, как и фасетирование — внешний интерфейс фильтрации. Добавление характеристик к вашим данным (например, бренд, жанр) имеет решающее значение для любого поиска, просмотра и обнаружения. Тегирование записей пользовательскими категориями и собственное глубокое понимание ваших данных создают более богатое сочетание результатов, основанное на нечеткой группировке, как описано выше.
Кроме того, синтаксис фильтров «И» (AND) и «ИЛИ» (OR) расширяет возможности группировки контента, позволяя движку объединять записи с множественными сходствами, а также различиями.
Необязательные фильтры и скоринг фильтров
Необязательная фильтрация работает как обычные фильтры, то есть возвращает записи, соответствующие как запросу, так и фильтрам. Однако она также возвращает записи, которые не соответствуют фильтрам. Это влияет на ранжирование: записи, соответствующие фильтрам, ранжируются выше, чем те, которые им не соответствуют. Если вы используете отрицательные фильтры, элементы, соответствующие вашему фильтру, ранжируются ниже других записей.
Скоринг фильтров позволяет привлекать больше записей, но контролирует ранжирование так, чтобы нечеткие совпадения ранжировались ниже точных.
Итак... Как же обуздать множество всех этих нечетких поисков и сопоставлений?
Добавление нечеткой логики, хотя и является мощным инструментом, сопряжено с определенным риском. Оно может вернуть слишком много результатов, которые пользователю будет трудно просмотреть, или выдать неожиданные результаты, которые, по мнению пользователя, могут нарушить релевантность выдачи.
Задача поисковой системы — ограничить влияние этого расширения информации. Например, отдавая более высокий приоритет точным совпадениям, гарантируя, что они появятся в верхней части результатов, над нечеткими:
- В случае опечаток точные совпадения считаются более релевантными, чем неточные (даже если опечатка очевидна для пользователя).
- При использовании синонимов точные совпадения более релевантны, чем совпадения по синонимам (даже если слово в запросе имеет несколько значений и синоним был бы лучшим выбором).
По сути, движки страхуют алгоритм нечеткого поиска, отображая нечеткие совпадения после точных.
Существует также множество паттернов пользовательского интерфейса для управления этим процессом. Например, Google и другие поисковые системы добавляют «предлагаемые варианты написания» прямо под строкой поиска. Или они предлагают функцию автозаполнения или подсказок запросов, где пользователю в выпадающем списке по мере ввода предлагаются варианты запросов (и категорий), которые он может выбрать.
Но правильное решение находится под поверхностью, оно полностью прозрачно для пользователя: поисковая система возвращает результаты, которые создают у пользователя интуитивное ощущение, что отображаемые элементы являются лучшими и наиболее релевантными — даже если они не в точности соответствуют тексту запроса.