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

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

Неточный поиск дубликатов активируется при настройке Правила сопоставления, когда выбран алгоритм Неточное соответствие. Когда правило срабатывает, то запускается поиск записей-дубликатов. Поиск идет в хранилище 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-грамм). Ввод разбивается на триграммы и превращается в НАБОР (порядок не имеет значения, значения не повторяются).

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

Особенности триграмм

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

При создании триграмм в начале лексемы используется префикс в два пробела, образующий две первые триграммы (например, ' 2' и ' 20' для 2004361651), а в конце лексемы только один префикс - т.е один пробел (например, '51 ' для 2004361651).

Пример: два сравниваемых значения 2004361651 и 2004361656 имеют по 11 триграмм, из которых 9 - общие, что даст коэффициент схожести = 0.8181818, и записи попадут в потенциальные дубликаты.

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

Отсекающее условие по триграммам может иметь вид: t1.column_name <% t2.column_name and word_similarity(t1.column_name, t2.column_name) >= [similarity threshold from algo settings]

  • где <% - специальный оператор, который возвращает true, если схожесть между упорядоченным набором триграмм из t1.column_name и самым длинным похожим фрагментом упорядоченного набора триграмм из t2.column_name >= pg_trgm.word_similarity_threshold.

  • pg_trgm.word_similarity_threshold - GUC переменная, выставляемая в настройках сервера БД и по умолчанию равная 0.6 (не редактируется без крайней необходимости).

Оператор ищет во втором аргументе максимально длинный участок (слово, подстроку), похожий на первый аргумент, и возвращает значение их схожести.

Далее проверяется схожесть против настроек с помощью word_similarity(...), что аналогично принципу работы оператора <%, но выдается точное значение схожести.

Запуск word_similarity (например, для '2004361651', '2004361656') дает коэффициент схожести = 0.8181818.

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

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

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

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

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