Развиваем нечеткий поиск на примере МТР
Всем привет!
Одним из основополагающих инструментов при работе с данными является их поиск. В юнидате мы используем инструмент ElasticSearch как сервис полнотекстового поиска. В данной статье мы хотим поделиться нашим личным опытом развития fuzzy поиска в тематике материально-технических – ресурсов (далее МТР) как пример использования поиска в специализированных бизнес-кейсах. Статья не является руководством к применению, так как определенные решения могут не быть оптимальными вне контекста платформы, но могут быть полезны при решении похожих задач. Итак, приступим.
Немного об эластике
Elasticsearch – документно-ориентированная БД, которая использует индексы Apache Lucene для хранения и поиска данных. Каждая запись данных представлена в виде JSON-документа, который содержит в себе определенный набор поисковых полей – fields. Для каждого индекса задаются определенные настройки. Среди этих настроек есть поисковые анализаторы и фильтры, которые определяют правила поиска данных в документах, а также настройки поисковых алгоритмов. Elasticsearch обладает определенным набором алгоритмов, позволяющих выполнить нечеткий поиск по ключевым словам. Основу поиска составляет разбиение поисковой строки на подслова (термы) и их вхождение в значение поисковых полей.
В юнидате используются три анализатора поступившего поискового запроса, каждый из которых отвечает за определенный функционал поиска:
'unidata_default_analyzer',
'unidata_morph_analyzer',
unidata_search_analyzer'
unidata_default_analyzer разбивает поисковый запрос на целые слова по настроенному токенайзеру.
Далее идет морфология. Используется $morph поле, которое задействует unidata_morph_analyzer. Анализатор полученные термы преобразует к корню с помощью стемминга. Если поиск настроен с учетом морфологии, то, например, строка «Мама не мЫлА рАМУ» будет токенизирована на "мам", "мой", "рам". Уровень не используется, если морфология не поддерживается.
unidata_search_analyzer используется непосредственно в запросах к эластику, который задействует $default (указывает на unidata_default_analyzer) или $standard поле с добавлением n-грамм, приводит слова к нижнему регистру, убирает стоп-слова.
В итоге поисковый запрос пользователя, например, "Мама не мЫлА рАМУ" будет разделен на отдельные термы "мама", "мыла", "раму". А каждый терм дополнительно может разбиваться на n-граммы.
С чего мы начали
Когда пользователь юнидаты начинает работу с данными НСИ, то первое что-он видит - это форму полнотекстового поиска записей. На практике так вышло, что пользователь обращается к строгому поиску только тогда, когда полнотекстовый поиске не дает нужных результатов.
Когда мы разрабатывали полнотекстовый поиск, то изначально основной его целью было найти среди всего объема данных хоть что-нибудь, удовлетворяющее поисковому запросу. Для решения этой задачи мы воспользовались стандартным unidata_default_analyzer анализатором эластика, который разбивает поисковый запрос на n-граммы произвольной длины. В качестве фильтра мы использовали преобразование к нижнему регистру и исключение стоп-слов. Токенайзер по умолчанию делил исходный запрос на токены (термы) по спецсимволам, но мы добавили возможность устанавливать в качестве токенайзера конкретный символ, например, пробел. Так же мы используем wildcards. Эти настройки в определенной степени решали задачи и всегда находили более- менее релевантный результат до тех пор, пока мы не столкнулись с бизнес-кейсами экспертов в области ведения НСИ МТР, где наш нечеткий поиск дал сбой.
1. Большое количество в поисковых атрибутах отдельных букв и цифр, не связанных в четкие слова. N-граммы начинают сходить с ума, и алгоритмы эластика считают релевантными буквально все записи, где есть хотя бы один-два символа из поискового запроса во множестве поисковых атрибутов. Если ввести «Блок НКУ 1.3DT», то можно было найти все, начиная от блоков до насосов. При этом у всех нерелевантных записей был высокий score из-за частого вхождения n-грамм в виде отдельных наборов символов.
2. Обилие критичных для анализа спецсимволов, в основном это точки и тире. Проблема заключается в том, что пользователи не знают и не должны знать точное расположение всех этих символов в запросе. Пользователи просто вводят отдельные куски наименования через пробел, желая найти только те данные, где есть эти части. Более того, эти части часто пишутся в произвольном порядке, не сохраняя правильную последовательность. Поскольку часто токенайзером служит пробел, то получалось, что такие куски больше оценивались как самостоятельные термы, нежели части слова, поэтому релевантные записи уходили почти в самый конец поисковой выдачи
3. Наличие латиницы и кириллицы в значении полей. На примере выражения «Блок НКУ 1.3DT.T» можно заметить неоднозначность написания символов «Т» с точки зрения латиницы и кириллицы. Возник вопрос поддержки транслитерации строк в поиске данных
4. Непонимание расчета score эластиком на практике. Когда речь заходит о нечетком поиске, каждый заказчик хочет определить для себя некий объяснимый критерий релевантности, который в дальнейшем может быть использован для автоматизации управления данными. Этот вопрос является самым сложным для нас, так как требуются большое количество сил на реверс-инжиниринг поисковых алгоритмов, даже не смотря на имеющуюся теоретическую базу из документации эластика.
К чему пришли
Определив основные пользовательские кейсы, мы стали слона есть по частям. Прежде всего мы занялись решением проблемы номер 1. Чтобы не вводил пользователь, эластик в большинстве случаев в ответе возвращал много нерелевантного мусора, который был в топе поисковой выдачи. В первую очередь было принято решение сократить объем данных в нечетком поиске, принимая во внимание наличие у заказчика приоритетных атрибутов, по которым чаще всего ищутся записи.
Самым простым решением казалось использование boost-фактора, который предоставляет сам эластик. Однако на практике буст для определенных атрибутов не дал какого-либо значимого результата – количество мусора не уменьшилось, увеличился только score для записей. Мы предположили, что виной всему «статистическое загрязнение» другими менее значимыми поисковыми атрибутами. Тогда мы ввели в платформе термин «Дайджест-поле», означающий, что атрибут участвует в нечетком поиске, и выделили дайджест-поля отдельно от поисковых полей, которые используются в более строгом поиске. Мы скорректировали формирование запросов в эластик с учетом дайджест-полей и это уже дало первые результаты – количество нерелевантных записей заметно сократилось.
Далее мы пришли к выводу, что необходимо убрать n-граммы и в качестве поисковых термов использовать только слова, разделенные токенайзером, например тем же пробелом. Минус такого решения в том, что, отключая n-граммы, мы не даем пользователям совершать ошибки в словах или опечатки. Однако опыт взаимодействия с пользователями показал, что нетрудно найти и исправить ошибку в искомом запросе нежели искать в табличной части с результатом поиска нужные записи среди менее релевантных. Мы добавили опцию, позволяющую анализатору эластика использовать только $default поле в дадйжест-полях, таким образом запретив применение n-грамм. После отключения n-грамм и ввода дайджест полей количество нерелевантных записей еще больше сократилось за счет того, что эластик обрабатывал термы как есть, без дополнительных подстановок.
Далее оставалось только ввести логический оператор AND вместо OR, который бы просто связывал термы в поисковом запросе. Этот оператор в совокупности с токенайзером, который разделяет искомый запрос на термы по настраиваемым спец символам, позволяет пользователю не задумываться о наличии каких-либо спецсимволах – разделителях в наименовании, и гарантированно получить релевантный результат.
Решение задачи транслитерации строк предоставляет сам эластик, путем использования в поисковом анализаторе поддержки транслитерации латиницы и кириллицы и сохранения в индексе транслитерированных строк. Однако стандартная таблица транслитерации букв не полностью удовлетворяет требованиям пользователей. Например, русской букве «С» сопоставляется латинская “S”, в то время как пользователь ожидает преобразование в латинскую Си. Для этой задачи необходимо переопределить стандартную таблицу транслитерации букв.
Что же касается понимания расчета релевантности эластиком, то это наиболее сложная для задачи, оптимальное решение которой еще предстоит найти. Проблема не только в том, что одних математических формул недостаточно для полного объяснения расчета score, но и в том, что даже если мы в точности до десятых сможем определить все факторы, которые повлияли на расчет релевантности, то вряд ли пользователь или разработчик будет держать в голове все эти нюансы для принятия какого-либо решения в отношении нечеткого поиска, так как риск получить непредсказуемый результат достаточно велик. В наших проектах требуется найти достаточно легко интерпретируемый метод расчета релевантности без лишних технических нюансов, который бы приводил к гарантированному результату поисковой выдачи. Не исключено, что наши исследования приведут к созданию собственного алгоритма.
Кроме решения задач пользователей тематики МТР, у нас также имеется ряд задач в road map по улучшению поисковых платформы, которые помогут нашим пользователям без лишних усилий быстро находить нужные данные. В дополнение мы планируем использовать нечеткий поиск в разработке сервиса подбора аналогов и автоматической классификации записей, но это уже другая история.