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

Общая информация

Неточный поиск дубликатов активируется при настройке Правила сопоставления, когда выбран алгоритм Неточное соответствие. Когда правило срабатывает, то запускается поиск записей-дубликатов. Поиск идет в хранилище PostgreSQL.

Алгоритм нечеткого сопоставления имеет название org.unidata.mdm.matching.storage.postgres.service.impl.algorithm.InexactAlgorithm.

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

Этапы поиска

Подход 1

Шаг 1. Вводные данные оптимизируются. Ввод превращается в объект tsvector, переводится в нижний регистр, подвергается стеммингу (и приводится к канонической форме). Стемминг — процесс нахождения стеммы (основы слова). Стемминг позволяет делать поисковый движок независимым от формы слова (Рисунок 1).

Применяется только словарный стемминг, когда выделяется корень слова.

Значение типа tsvector содержит отсортированный список неповторяющихся лексем, т.е. слов, нормализованных так, что все словоформы сводятся к одной. Сортировка и исключение повторяющихся слов производится автоматически при вводе значения, как показано в примере ниже. Подробнее см. документацию по tsvector и tsquery

SELECT 'a fat cat sat on a mat and ate a fat rat'::tsvector;
                    tsvector
----------------------------------------------------
'a' 'and' 'ate' 'cat' 'fat' 'mat' 'on' 'rat' 'sat'
Пример стемминга

Рисунок 1 – Пример стемминга

Шаг 2. Затем схожие манипуляции выполняются для превращения ввода в объект типа tsquery (полнотекстовый поиск). Значение tsquery содержит искомые лексемы, объединяемые логическими операторами & (И), | (ИЛИ).

Шаг 3. Затем объекты с разными ID (разные записи матчинга) сравниваются в терминах соответствия запроса вектору лексем tsvector @@ tsquery.

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

Подход 2

Шаг 4. Если соответствие не обнаружено, дополнительно используется поиск по триграммам (особый вид n-грамм). Ввод разбивается на триграммы и превращается в НАБОР (порядок не имеет значения, значения не повторяются).

В триграммы попадают буквы и пробелы, а знаки препинания очищаются.

Два набора двух разных записей сравниваются на похожесть через вычисление индекса Жаккара: нахождение частного от пересечения двух наборов и их объединения.

Пример: две записи содержат в двух наборах 14 одинаковых триграмм. Всего в двух наборах содержится 19 уникальных триграмм. Значит коэффициент похожести будет равен 14 / 19 = 0.73.

Коэффициент по умолчанию установлен на 0.65 как оптимальный, но может быть изменен при необходимости.

Настройка неточного поиска

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

  • Язык содержимого (contentLanguage) - в текущей реализации поддерживаются только русский и английский (по умолчанию). Используется для подхода 1.

  • Порог схожести (similarityPercentage) - отсекает наборы триграмм по коэффициенту схожести. Значение в диапазоне от 0.00 до 1.00 включительно. По умолчанию = 0.65. Используется для подхода 2.

  • Тип объединения (concatenationType) - тип объединения лексем в объектах tsquery. В текущей реализации поддерживаются & (И) и | (ИЛИ). По умолчанию: & (И). Используется для подхода 1.