Как найти полнотекстовым поиском

Полнотекстовый поиск и его возможности

Многие СУБД поддерживают методы полнотекстового поиска (Fulltext search), которые позволяют очень быстро находить нужную информацию в больших объемах текста.

В отличие от оператора LIKE, такой тип поиска предусматривает создание соответствующего полнотекстового индекса, который представляет собой своеобразный словарь упоминаний слов в полях. Под словом обычно понимается совокупность из не менее 3-х не пробельных символов (но это может быть изменено). В зависимости от данных словаря может быть вычислена релевантность – сравнительная мера соответствия запроса найденной информации.

В статье рассказывается как работать с полнотекстовым поиском на примере БД MySQL, а так же приведу примеры «нестандартного» использования данного механизма.

В MySQL возможности полнотекстового поиска (только для MyISAM-таблиц) поддерживаются начиная с версии 3.23.23. В последующих версиях механизм потерпел существенные доработки и расширения, в тоге превратившись в мощное средство для создания поисковых механизмов веб-приложений. Главная особенность – быстрый поиск слов в очень больших объемах текстовой информации.

Индекс FULLTEXT

Итак, чтобы работать с полнотекстовым поиском, сначала нам нужно создать соответствующий индекс. Он называется FULLTEXT, и может быть наложен на поля CHAR, VARCHAR и TEXT. Причем, как и в случае с обычным индексом – если происходит поиск по 2-м полям, то нужен объединенный индекс 2-х полей, используйте поиск по одному полю – нужен индекс только этого поля. Например:

CREATE TABLE `articles` (
`id` int(10) unsigned NOT NULL auto_increment,
`title` varchar(200) default NULL,
`body` text,
PRIMARY KEY (`id`),
FULLTEXT KEY `ft1` (`title`,`body`),
FULLTEXT KEY `ft2` (`body`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8;

В этом примере создается таблица с 2-мя полнотекстовыми индексами: ft1 и ft2, которые можно использовать для поиска в полях title и body, или только в body. Только в поле title искать не получится.

Конструкция MATCH-AGAINST

Собственно для самого полнотекстового поиска в MySQL используется конструкция MATCH(filelds)… AGAINST(words). Она может работать в различных режимах, которые достаточно сильно между собой отличаются. Для всех действует следующее правило: данная конструкция возвращает условную релевантность, но способ вычисления которой может быть разным в зависимости от режима. Еще стоит добавить что во всех режимах поиск всегда регистрозависимый. Далее более подробно о каждом из них.

MATCH-AGAINST IN NATURAL LANGUAGE MODE

— это основной вид поиска, который используется по умолчанию, т.е. если режим не указан:

SELECT * FROM `articles` WHERE MATCH (title,body) AGAINST ('database');

В этом примере мы ищем слово database в полях title и body таблицы articles на основе индекса ft1 (см. пример создания таблицы выше). Выборка будет автоматически отсортирована по релевантности – это происходит в случае указания конструкции MATCH-AGAINST внутри блока WHERE и не задано условие сортировки ORDER BY.

Кстати, несмотря на возможности алиасов, при запросах конструкцию приходится повторять в разных местах, что усложняет запросы. Вот например нельзя написать так:

SELECT *, MATCH (title,body) AGAINST ('database') as REL
FROM `articles`
WHERE REL > 0;

— этот запрос выдаст ошибку: поле Rel не определено. Что бы работало, придется продублировать данную конструкцию:

SELECT *, MATCH (title,body) AGAINST ('database') as REL
FROM `articles`
WHERE MATCH (title,body) AGAINST ('database') > 0;

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

В примере выше в переменной REL будет вычислена релевантность. Эта величина зависит прежде всего от количества слов в полях tilte и body, того насколько близко данное слово встречается к началу текста, отношения количества встретившихся слов к количеству всех слов в поле и др.

Например, релевантность будет не нулевая, если слово database встретится либо в title, либо body, но если оно встретится и там и там, значение релевантности будет выше, нежели если оно два раза встретится в body.

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

Еще следует заметить что для IN NATURAL LANGUAGE MODE действует так называемое «50% threshold». Это означает, что если слово встречается более чем в 50% всех просматриваемых полей, то оно не будет учитываться, и поиск по этому слову не даст результатов.

MATCH-AGAINST IN BOOLEAN MODE

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

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

Еще особенностями бинарного режима является отсутствие автоматической сортировки в случае указания условия WHERE, однако для сортировки можно использовать алиас:

SELECT *,
MATCH (title,body) AGAINST ('+database MySQL' IN BOOLEAN MODE) as REL
FROM `articles`
WHERE MATCH (title,body) AGAINST ('+database MySQL' IN BOOLEAN MODE)
ORDER BY REL;

Пример выведет все записи содержащие слово database, но если в записи присутствует слово MySQL, то его релевантность будет выше. Записи будут отсортированы по релевантности.

В бинарном режиме отсутствует ограничение «50% threshold». Бинарный режим можно использовать и без создания полнотекстового индекса, однако это будет работать очень медленно.

MATCH-AGAINST IN NATURAL LANGUAGE MODE WITH QUERY EXPANSION

Или просто «WITH QUERY EXPANSION». Работает примерно также, как NATURAL LANGUAGE MODE, с той лишь разницей, то в результат поиска попадают не только совпадения с шаблоном, но и возможные логические совпадения. Это работает примерно так:

Сначала MySQL выполняет запрос аналогичный NATURAL LANGUAGE MODE и формирует результат. По этому результату производится попытка вычислить слова, которые так же имеют высокую релевантность для полученной выборки. В случае, если эти слова присутствуют производится поиск и по ним тоже, но значение их на релевантность будет существенно ниже. Отдается смешанная выборка – сначала те результаты, где слово присутствует, а потом те, которые были получены в результате «повторного» поиска.

WITH QUERY EXPANSION не рекомендуется использовать для больших объемов информации, так как в результат может попасть очень много лишнего.

Использование FULLTEXT SEARCH

Пара слов об алгоритмах поиска

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

1. убрать все HTML-теги
2. убрать все непечатные символы, знаки препинания и тому подобное
3. убрать все слова длинной менее 3-х символов
4. перевести все слова в нижний регистр

— это только в самом простом случае, без учета морфологии, подсветки, учета ключевых слов и кодировки.

Соответственно, с поисковым запросом надо сделать тоже самое. Режим поиска используется любой – как удобнее… А вообще поиск – это отдельная тема, про которую нужна отдельная статья.

Раскрытие связок многое-ко-многим

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

Допустим, у нас есть две большие таблицы: с пользователями и группами пользователей. Причем, каждый пользователь имеет отношение к большому количеству различных групп, в свою очередь группы включают в себя большое количество пользователей. При нормальном соотношении (т.е. раскрытии через 3-ю таблицу), что бы выбрать все группы, которые принадлежат к некоторому пользователю понадобиться сделать запрос, объединяющий 2 или 3 таблицы, что даже при присутствии индексов очень накладно.

Однако можно выполнить денормализацию по следующей схеме:

Теперь, что бы выбрать группы, принадлежащие к пользователю 2 можно сделать:

SELECT *
FROM `groups`
WHERE MATCH (groups) AGAINST ('+user2' IN BOOLEAN MODE);

Это будет работать намного быстрее, чем исходный вариант (с 3-ей таблицей). Аналогично с группами, но если подобные выборки нам в принципе не нужны, то можно обойтись без соответствующего поля в таблице групп. Тогда получится что-то вроде «односторонней» связи M:N. То есть можно вычислить все M, которые принадлежат к N, не нельзя сделать обратного.

В этом случае, как правило, используется IN BOOLEAN MODE.

— Кстати, на эту схему очень хорошо ложится тегирование информации, но там не все так просто и это опять же отдельная тема.

Использование релевантности как меры отношения одного объекта к другому

Один из алгоритмов для вычисления статей, «похожих» на данную статью. Всё просто: берутся теги данной статьи, и делается полнотекстовый запрос по полю с тегами всех остальных статей с сортировкой по релевантности (если она нужна). Естественно, сначала вылезут те, которые содержат максимальное совпадение по тегам.

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

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

И кое-что в заключение:

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

Содержание:

1.       Что такое полнотекстовый поиск данных?

2.       Как включить доступность полнотекстового поиска в 1С?

3.       Как осуществляется полнотекстовый поиск данных?  

1.    Что такое полнотекстовый поиск данных?

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

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

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

2.    Как включить доступность полнотекстового поиска в 1С?

Механизм полнотекстового поиска будет доступен при включенном флаге «Полнотекстовый поиск данных». Данный флаг доступен в настройках базы и расположен в разделе «Администрирование» → «Общие настройки» → «Полнотекстовый поиск данных» (в зависимости от конфигурации, расположение настройки может отличаться, тогда включить/отключить флаг поиска можно в меню «Все функции»)

Полнотекстовый поиск данных в 1С

Для открытия окна поиска надо нажать «лупу» в панели инструментов или вызвать сочетанием клавиш Ctrl+Shift+F.

Открытие окна поиска   

3.    Как осуществляется полнотекстовый поиск данных?

Для полнотекстового поиска в 1С наберите часть слова, слово или словосочетание.

Процесс полнотекстового поиска в 1С

Помимо точного текста допускается использование более сложных поисковых запросов (правила использования поисковых операторов для осуществления запросов полнотекстового поиска в данных смотри на рисунке ниже)

Язык запросов полнотекстового поиска данных

Прежде чем начать поиск область полнотекстового поискав 1С 8.3 Предприятие можно сократить, для этого надо перейти по гиперссылке в строке «Области поиска», перевести переключатель в положение «В разделах» и выбрать разделы или отдельные объекты разделов установив на них флажки.

Сокращение области полнотекстового поиска в 1С

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

Использование полнотекстового поиска данных

В результате в окне результата поиска будут выведены все объекты, содержащие указанный текст.

Окно результатов поиска

Любой из отображенных объектов можно открыть, нажав на его название.

Открытие объектов в окне результатов поиска

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

Перемещение в окне результатов поиска

Специалист компании «Кодерлайн»

Зоя Косьяненко

Управление полнотекстовым поиском

В программе “1С:Бухгалтерия 8” реализован механизм полнотекстового поиска, что позволяет быстро найти нужную информацию в справочниках, документах, отчётах или в информационной базе.

Чтобы начать поиск необходимо установить курсор в поле «Поиск» или нажать сочетание клавиш “Ctrl” и “F”. Начните набирать текст и поиск будет запущен автоматически. Ниже представлен пример поиска в справочнике «Номенклатура».

По кнопке со значком лупы (сочетанием клавиш “Alt” и “F” или по кнопке “Ещё”) можно выбрать “Расширенный поиск” и установить параметры поиска.

При работе с полнотекстовым поиском у пользователя могут возникнуть следующие трудности:

1) Поиск работает некорректно – пользователь начинает вводить символ, программа осуществляет поиск, после ввода следующих символов список формируется пустым, несмотря на то, что в программе есть объекты, удовлетворяющие критериям поиска.

2) Поиск осуществляется медленно.

3) Поиск не работает.

Для устранения вышеуказанных проблем необходимо:

• Проверить корректность ввода данных в поисковую строку – убедится, что все буквы вводятся на одной раскладке клавиатуры, проверить нет ли отбора в списке и т.д.

• Проверить включен ли полнотекстовый поиск данных, для этого необходимо перейти в раздел «Администрирование» – «Общие настройки».

Открыть подраздел «Поиск данных» и установить галочку в поле «Полнотекстовый поиск данных».

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

При нажатии на кнопку «Очистить индекс» программа оповестит о том, что все индексы будут очищены, необходимо нажать на кнопку «Да».

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

Далее необходимо обновить индекс, нажав на соответствующую кнопку, когда индекс обновится, кнопка «Обновить индекс» станет недоступна, а статус индекса сменится на «Обновление не требуется».

Для того что бы вышеуказанные трудности не возникали и поиск работал корректно, необходимо настроить выполнение двух регламентных заданий – «Обновление индекса ППД» и «Слияние индекса ППД».

Необходимо зайти в раздел «Администрирование» – «Обслуживание».

Открыть подраздел «Регламентные операции» – «Регламентные и фоновые задания».

На закладе «Регламентные задания» необходимо найти «Обновление индекса ППД» и «Слияние индекса ППД» нажать двойным щелчком мыши, поставить галочку «Включено».

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

Переключаясь между вкладками «Общие», «Дневное», «Недельное» и «Месячное» можно задать своё расписание. В примере настроено на каждый день с 8:00:00 каждые 60 секунд.

После настройки расписания необходимо нажать на кнопку «ОК» и сохранить изменения, нажав на кнопку «Записать и закрыть».

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

Введение

Мы все постоянно сталкиваемся с так называемым полнотекстовым поиском — нахождением документов по поисковой фразе. Самый известный пример — это поиск Google.

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

Мы в DD Planet разрабатываем сервисы поиска и аналитики по базам данных B2B-закупок и активно используем Elasticsearch. Но когда мы попытались организовать поиск и сопоставление очень коротких документов (наименований товаров), то столкнулись с рядом проблем.

Как работает полнотекстовый поиск

Большинство систем полнотекстового поиска, в том числе и Elasticsearch, основаны на обратном индексе — структуре данных, где для каждого слова из базы документов хранятся все документы, в которых оно встречается. Обратный индекс используется для поиска по текстам.

Пусть у нас есть корпус из базы из трех текстов:

T0="синяя ручка»", 
T1="синее дерево", 
T2="красное дерево",

тогда обратный индекс будет выглядеть следующим образом:

"синий": {0, 1}
"ручка": {0}
"дерево": {1, 2}
"красный": {2}

Поиск по одному слову очевиден — это просто список всех документов, соответствующих поисковому слову. При поиске фразы можно производить как пересечение, так объединение результатов поиска по отдельным словам с целью ранжировать результаты по релевантности. Рассмотрим, например, поиск фразы «красная ручка». Поиск по слову «красный» дает результат {2}, по слову «ручка» — {0}. Пересечение пусто, поэтому точно совпадения нет. Если считать частичное совпадение, то получится два документа {0, 2} c степенью соответствия ½. В реальных поисковых системах обычно применяются более сложные методики ранжирования, например, с учетом TF-IDF, однако в результаты выдачи не может попасть документ без текстового совпадения с поисковым запросом.

Проблемы полнотекстового поиска

Если нам необходимо не просто искать внутри данных, а сопоставлять их, находить похожую информацию или те же данные, только написанные по-другому, то мы сталкиваемся со следующими проблемами:

1. Контекстная значимость слов.
   Вернемся к предыдущему примеру: словосочетания «синяя ручка» и «красное дерево» отличаются от фразы «красная ручка» одинаково одним слово, имеют примерно одну релевантность, однако семантически «красная ручка» намного ближе к «синей ручке», чем к «красному дереву». На мой взгляд, с этим сложнее всего бороться. 
   Можно применить технику с весами слов в поисковом запросе. Но такое решение переводит одну задачу в другую: непонятно, как определить эти веса адекватно. Самым простым вариантом является, как уже отмечалось, вычисление TF-IDF, но этот подход как минимум не учитывает порядка слов.
2. Разное написание одинаковых по значению слов.
   Другая проблема — сокращения и синонимы в наименованиях товарных позиций, например, не только «лист бумаги А4», а также «А4», «бумага для принтера», «лист А4» и т. д. 
   Решение проблемы — загрузка в Elasticsearch словарей синонимов. Однако сборка обширных библиотек синонимов если и реальна, то очень трудоемка, особенно в узкоспециализированных областях.
3. Разное значение одинаковых по написанию слов.
   Обратной проблемой является то, что исходя из контекста слова могут иметь разное значение. Например, во фразах «ключ дверной» и «ключ активации Windows» слово «ключ» имеет совершенно разное значение.  

NLP как решение проблем

Одним из технологичных способов решить вышеупомянутые задачи является применение NLP подходов. NLP (Natural Language Processing) — общее направление искусственного интеллекта и математической лингвистики, которое изучает проблемы компьютерного анализа и синтеза естественных языков. 

NLP использует семантико-синтаксический анализ введенного текста, учитывает естественно-языковые средства. Сейчас существует множество готовых моделей, фреймворков и уже решенных проблем в этой области.

Как определить степень «похожести» фраз

В NLP есть следующая задача — Paraphrase Identification — это изучение двух текстовых объектов (например, предложений) и определения, имеют ли они одинаковое значение (то есть являются парафразами). Пример парафраз: «Завтра кафе работает до 17:00» и «На следующий день кафетерий будет работать до пяти вечера». Почему это нам интересно? С помощью парафразирования мы можем анализировать текстовые описания товаров и выяснять, связаны ли они с одним товаром или нет.

Эта задача хорошо исследована. Существуют большие базы данных парафраз на русском и английском языках. В качестве инструмента для решения этой проблемы мы обратились к библиотеке DeepPavlov.ai [1], мощному фреймворку, разработанному в МФТИ. В нем собраны различные подходы и модели, связанные с обработкой русского языка.

Следующим шагом было получение базы парафраз. Так как наша тематика достаточна специфична (поиск товаров), нам нужна собственная база данных. Мы воспользовались агрегаторами магазинов вида Яндекс.Маркета. Взяли одно название товара с Маркета и другое название этого же товара в интернет-магазине. 

Экспериментируя с разными моделями, имеющимися в DeepPavlov, мы поняли — основной вклад в результат дают не настройки модели, а качество наших данных.

Как организовать поиск, когда у нас почти ничего нет

Однако нам нужно не просто определять степени соответствия, а находить наиболее похожие товары. Как это сделать? Можно использовать полный перебор, однако он имеет сложность поиска $inline$O(N)$inline$ и занимает много времени, тогда как обратный индекс Elasticsearch имеет сложность поиска $inline$O(log N)$inline$. Попробуем достичь такой же скорости поиска.

Что мы имеем: множество строк и некоторую функцию, описывающую степень соответствия между этими строками. Будем далее называть эту функцию расстоянием. 

Если покопаться в теории, можно наткнуться на следующую математическую структуру: метрическое пространство — это множество, на котором определена функция $inline$d$inline$ такая, что выполняются следующие аксиомы:

1. Расстояние равно нулю только при равенстве двух объектов $inline$d(x, y) = 0$inline$, если $inline$x=y$inline$. 
2. Расстояние симметрично $inline$d(x, y) = d(y, x).$inline$
3. Самая сложная из аксиом — неравенство треугольника $inline$d(x,z)≤ d(x,y)+d(y,z).$inline$ Это значит, что сумма расстояний не меньше, чем расстояние между крайними объектами.

Зачем нам нужна такая сложная структура? Она нужна для эффективного решения задач поиска ближайших соседей (Nearest neighbor search) — в нашем случае поиска похожих товаров. Такая задача может быть решена в метрическом пространстве с помощью структуры vantage-point tree, поиск в которой имеет асимптотику поиска $inline$O(log N)$inline$ [2]. Заметим, если бы речь шла о векторах, эта задача решилась намного проще, например, с помощью Kd-деревьев. Однако так как наши объекты более абстрактны, все гораздо сложнее.

Vantage-point tree

Посмотрим, как работает vantage-point tree [3]. Оно напоминает ball-tree, используемый в векторных пространствах. Его структура представляет собой бинарное дерево. Рассмотрим, как оно строится. Мы берем в качестве вершины некоторый объект из множества (vantage-point) и рисуем вокруг него окружность (изображена на рисунке ниже).

Все объекты, находящиеся внутри окружности (то есть на расстоянии $inline$≤S$inline$ от vantage-point), идут в левую часть дерева. Остальные — в правую часть. Далее процедура повторяется для каждого поддерева. Чтобы дерево было сбалансировано, надо стараться выбирать S так, чтобы исходное множество объектов делилось на примерно равные части. Это несложно сделать, если заранее просчитать все расстояния и найти их медиану.

Предположим, мы хотим найти K ближайших соседей к точке $inline$X$inline$ (отмечена красным крестиком на рисунке). Мы еще не нашли ни одной точки, поэтому в качестве ближайшего кандидата берем вершину дерева (возможно, потом мы удалим эту точку). Запоминаем значение $inline$D$inline$ — текущее расстояние до самого дальнего кандидата. Теперь надо решить, нужно ли нам искать в обоих поддеревьях или достаточно проверить только одно и них.

Так как точка $inline$X$inline$ находится внутри нашей окружности, мы должны сначала проверить «внутреннее» поддерево. Находим в этом поддереве синюю точку и обновляем $inline$D$inline$. Надо ли нам проверять «внешнее» поддерево? Мы рассмотрели все точки внутри окружности, но так как $inline$D > T$inline$ (расстояние от X до окружности), за пределами окружности могут существовать более близкие точки. Значит, нам надо проверить «внешнее» поддерево.

Однако если мы уже собрали K ближайших точек, а $inline$D ≤ T$inline$, то проверять «внешнее» поддерево нет необходимости. Это и обеспечивает выигрыш в производительности по сравнению с полным перебором.

Метрическая функция

Мы решили использовать нашу функцию парафразирования $inline$left(f(x,y)right)$inline$ в качестве расстояния для построения vantage-point tree и столкнулись с рядом проблем:

1. Не выполняется первая аксиома — расстояние между точками равно нулю только при условии, что они равны. Это условие не выполняется уже на обучающей выборке, так как мы полагали, что некоторые фразы означают одно и то же при их разном написании. Для решения проблемы мы добавили к основному расстоянию cosine расстояние по Doc2Vec с небольшим весом — оно будет гарантировано различно для разных объектов. 

   $$display$$d(x,y)=f(x,y)+ε cdot S_{Doc2Vec}(x cdot y )$$display$$

   Однако вопрос подбора весового коэффициента ε остается открытым — с этим надо экспериментировать на реальных данных.

2. Модель несимметрична. Почему? Понять это достаточно сложно, но, скорее всего, проблема в ошибке округления float32. Из-за сложности модели ошибка накапливается в слоях нейронов. Эта проблема легко решается вычислением сначала расстояния от $inline$x$inline$ до $inline$y$inline$, а потом наоборот, и суммированием результата. 

   $$display$$d(x,y)=f(x,y)+f(y,x)$$display$$

3. Не всегда выполняется неравенство треугольника $inline$d(x,z)≤ d(x,y)+d(y,z)$inline$. Причиной этого являются особенности обучения нашей модели парафразирования. Например, рассмотрим фразы

   x="красная машина", y="синяя машина", z="синий микроавтобус"

   Это наглядный пример, когда $inline$d(x,z) ≥ d(x,y)+d(y,z).$inline$ Из-за этого поисковая выдача иногда получается неупорядоченной. Исправить аналитически это не получается, но компенсировать это может увеличение веса расстояния Doc2Vec — для него неравенство треугольника выполняется всегда. 

Выполнив формальные критерии, описанные выше, мы столкнулись на практике с другой проблемой — время поиска росло линейно, а не логарифмически, как мы ожидали. Покопавшись в литературе, мы выяснили: логарифмическая скорость поиска имеет место для примерно равномерного распределения точек в пространстве [2]. А у нас объекты распределены неравномерно — они чаще дальше, чем ближе. 

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

Итоги

Пока что мы проводили тестирование на небольших базах данных (до миллиона объектов), и там наш поиск работает достаточно хорошо. Время сборки дерева растет практически линейно с небольшим логарифмическим коэффициентом. 

Рост времени поиска близок к логарифмическому. Почему рост времени поиска не всегда равномерен? Дело в том, что работа поиска зависит от распределения точек в пространстве. Возникает интересный вопрос: если бы мы могли управлять распределением точек в пространстве, то какое распределение было бы оптимальным? В литературе по vantage-point tree этот вопрос обычно не обсуждается, но обсуждается смежный вопрос — как оптимально выбрать vantage-point. 

Например, в метрическом пространстве нужно брать самую крайнюю точку[2], тогда на границе будет меньше всего точек и поиск станет лучше. Но эта идея реализуема только в пространстве с понятиями лево, право и край. В пространстве без порядка объектов эта идея не работает. 

Наше решение не является «серебряной пулей». Мы пробовали его для поиска товаров, и получилось отлично. Если выбрать другую тематику, результаты могут быть совершенно другими. 

Сейчас мы работаем над развитием и оптимизацией технологии. Мы хотим создать не просто алгоритмические или математические структуры, а реально работающие поисковые системы. Текущие результаты можно посмотреть на GitHub или попробовать через pip install nlp-text-search.

Литература

[1] http://docs.deeppavlov.ai/en/master/.

[2] Yianilos (1993). Data structures and algorithms for nearest neighbor search in general metric spaces. Fourth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics Philadelphia, PA, USA. pp. 311–321. pny93. http://web.cs.iastate.edu/~honavar/nndatastructures.pdf.

[3] http://stevehanov.ca/blog/?id=130

Автор: Басалов Юрий

Источник