Прослушайте этот блог в формате подкаста: Ваш браузер не поддерживает аудиоэлемент.

Прослушайте этот блог в формате подкаста:

Примерное время чтения: 3 минуты

Термин «нечеткий поиск» (fuzzy search) имеет несколько значений, и все они вращаются вокруг идеи приблизительного сопоставления. Наиболее распространенное понимание этого термина связано с нечетким сопоставлением строк, когда поисковая система находит слова, которые не совпадают точно. Классический пример — опечатки, когда запросы с ошибками приводят к результатам с правильным написанием. Но, как вы увидите, нечеткость — это не только исправление опечаток. Например, она также может исправлять плохо сформулированные запросы, распознавать разговорную лексику, расширять префиксы или выстраивать свободные категориальные связи между запросом и искомым контентом.

Нечеткое сопоставление (fuzzy matching), описанное в этой статье, позволяет поисковой системе применять некоторые (слегка) неточные методы сопоставления, чтобы гарантировать возврат всех релевантных результатов. В этом смысле релевантность не является точной наукой.

Релевантность поиска в целом

Отправной точкой для поиска является текстовое сопоставление, которое соотносит точные символы, буквы и слова запроса с записями в наборе данных. Скажем, вы ищете «лодка» (boat), поисковая система вернет все записи, содержащие слово «лодка». Не «каноэ» и не «круизный лайнер».

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

Но что, если слово «лодка» не встречается в записях, хотя данные содержат информацию, связанную с лодками? Здесь на помощь приходят синонимы. А что, если кто-то хочет найти «каноэ» (canoe) и пишет его как «canou»? Без учета опечаток поисковая система не выдаст никаких результатов.

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

Инструменты поиска, такие как Algolia (нечеткий поиск с учетом опечаток), Elastic (нечеткий поиск), Coveo (нечеткий поиск) и Constructor.io (правила нечеткого поиска), предлагают нечеткое сопоставление. Все они подходят к этому вопросу по-разному. Мы обсудим различные методы Algolia.

Определения нечеткого поиска и нечеткого сопоставления

Что такое нечеткий поиск?

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

Другие названия для нечеткого поиска: нечеткое или приблизительное сопоставление строк.

Примеры:

Введите «helo», найдите записи с «hello»

Введите «help», найдите записи с help и hello

Смотрите больше примеров и то, как это делается, ниже.

Что такое нечеткое сопоставление?

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

Примеры:

Введите «pants» (брюки), найдите pants, trousers, slacks (синонимы)

Введите «be», найдите Beatles, bees (поиск по префиксу)

Смотрите больше примеров и то, как это делается, ниже.

Другие варианты использования «нечеткости»

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

Нечеткая логика выстраивает логические отношения на основе относительной близости, а не бинарных значений, таких как истина и ложь (два объекта совпадают, основываясь на том, что оба они «высокие», а не имеют одинаковый точный рост).

Обратите внимание, что мы исключим любое нечеткое сопоставление, основанное на семантике, машинном обучении или статистических методах, таких как TF-IDF.

Нечеткий поиск с использованием учета опечаток (Typo Tolerance)

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

Что именно является опечаткой?

Пропущенная буква в слове, «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 и другие поисковые системы добавляют «предлагаемые варианты написания» прямо под строкой поиска. Или они предлагают функцию автозаполнения или подсказок запросов, где пользователю в выпадающем списке по мере ввода предлагаются варианты запросов (и категорий), которые он может выбрать.

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