Статус: в неточном поиске (fuzzy match)

Неточный поиск. Что это и зачем нужно?

Есть список чего-угодно, по-питоновски - list[str]. В нём надо найти элементы, которые похожи друг на друга. В роли списка могут быть названия файлов, имена людей, элементы справочников, перечень ИТ-систем и т.д. и т.п. Такая задача удивительно часто встречается в жизни.

Под неточными дубликатами мы понимаем такие две текстовые строчки, которые бы человек посчитал практически одинаковыми, за исключением технических/случайных разниц. Например, ошибки, опечатки и т.п. Конечно, метрика "неточных дубликатов" непрерывная, но рассматривается именно в таком ключе.

Для решения этой задачи нам надо научиться сопоставлять две строки и определять метрику похожести.

# для примера две короткие строчки
string_1 = 'работа 28'
string_2 = 'робот Петя_(28)'

fuzzy_match_function(string_1, string_2)  # -> 0.583 - это степень сходства
# возвращает метрику похожести, например, от 0 до 1

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

• расстояние Левенштейна - медленный;

• N-gram, обычно 2-3 gram - медленный;

• фонетические алгоритмы, типа Soundex - решают другую задачу, сходность звучания;

• полнотекстовой поиск, типа Meilisearch - обычно решает другую задачу, поиск подстроки в большом тексте, часто онлайн поиск (набираем на клавиатуре - сразу видим результат). Для нашего неточного поиска напрямую не походит.

Наивная реализация неточного поиска выглядит так:

import Levenshtein
import pandas as pd

list1 = ["apple", "banana", "appl", "date", "elderberry", "eilderbery"]

rows = []
for a in list1:
    for b in list1:
        score = Levenshtein.distance(a, b)  # тут работает С, довольно быстро
        rows.append({"s1": a, "s2": b, "score": score})
# асимптотика квадратичная
# вычисления расстояний, даже на С - занимает определённое время
# если в списке будет несколько миллионов элементов, это будет работать долго

Первый раз подобную задачу я решал ещё на MS Excel (vba). Макрос брал тут. Там же нашёл первую мини-статью, с которой началось долгое изучение данного направления.

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

Предобработка строк

Исходим из того, что набор строк не имеет точных дубликатов. Надо помочь алгоритму сопоставить неточные дубликаты.

Предобработка каждой строчки удаляет наиболее частые технические разницы и оставляет основу. Наглядно ниже в коде.

import re

# переводим в маленькие буквы
# оставляем только русские и английские буквы - обычно этого достаточно
# иногда оставляют цифры, это уже зависит от задачи
def clean_string(text):
    text = text.lower()
    text = re.sub(r'[^а-яёa-z0-9]', ' ', text)  # тут цифры удаляются
    text = re.sub(r'\s+', ' ', text)
    return text.strip()

string_1 = 'работа 28'  #  -> 'работа 28'
string_2 = 'робот    Петя_(28)'  # -> 'робот петя 28'

fuzzy_match_function(string_1, string_2)  # -> 0.583 без предобработки

string_1 = clean_string(string_1)
string_2 = clean_string(string_2)
fuzzy_match_function(string_1, string_2)  # -> 0.636 с предобработкой. Лучше!

Предобработка имеет еще один интересный эффект - снижение размера алфавита. Часто количество уникальных utf-8 символов в тексте составляет 100-200 штук. - len(set('тут много текста')) При создании 2-gram это дает теоретический максимум 200 ** 200 различных биграмм (квадрат алфавита). Много. А если мы оставляем только 33 рус. + 26 англ. + один пробел, то получаем 60*60. Это упрощает нам жизнь на следующих этапах.

Иногда предобработка еще включает:

• удаление стоп-слов (nltk stop words);

• удаление латиницы (сильно снижаем размер алфавита);

• перевод латиницы на кириллицу (транслитерация);

• экспериментировали с удалением "неважных" букв, но не получилось.

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

Векторизация

Это ключевое отличие от классических подходов (Левенштейн, n-gram). Все строчки переводятся в вектора. Основных способа векторизации три.

from sklearn.feature_extraction.text import (TfidfVectorizer, 
                                             HashingVectorizer,
                                             CountVectorizer)

Обычно используем TfidfVectorizer, т.к. он максимизирует качество получаемых векторов (есть IDF, нет хэш-коллизий).

Три аргумента TfidfVectorizer особенно важны, обычно настраиваются так:

• analyzer = 'char_wb' - будут выделяться только ngram в пределах слова (wb = word boundary). Всегда настраиваем так, т.к. ищем именно техническое сходство букв и буквосочетаний в коротких текстах;

• ngram_range = (2, 3) - ngram/подстроки длинной 2 и 3. Можно поэкспериментировать с большими ngram, например (2, 5);

• norm = 'l2' - всегда ставим так. Чтобы произведение векторов (inner/dot product) давало косинусную близость (cosine similarity) и чтобы длина векторов не играла роль (все вектора приводятся к единичной длине).

Полученные вектора имеют важное свойство: все числа в них - неотрицательные (лежат в первой четверти). Это простое следствие того, что TfidfVectorizer считает частотность ngram, которая не может быть отрицательной.

Значит угол между ними может быть от 0 до 90 (π / 2) градусов. Вспоминая график косинуса, понимаем, что метрика сходства будет лежать на отрезке [0, 1].

по X угол, по Y значения функции косинуса

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

Снижение размерности векторов

Обычно размерность векторов TfidfVectorizer очень большая, десятки/сотни тысяч. Дальнейшая работа с ними будет затруднена (много весят, медленные, проклятие размерности).

Эта проблема частично решается тем, что TfidfVectorizer возвращает разряженную матрицу CSR matrix от scipy (храним только ненулевые элементы матрицы). Но так можно только хранить и проводить простые манипуляции. Дальнейшие операции по поиску векторов потребуют сделать массив плотным, т.е. перевести в np.array.

К примеру, если у нас 5 млн. векторов размерностью 200_000, то вектора займут 3.7 терабайта (float32) на диске, что невероятно много. Если такие вектора начать перемножать (X @ X.T), то ждать придётся несколько месяцев. Да и хранить их негде.

Поэтому при получении векторов сразу снижают их размерность.

Вообще, алгоритмов снижения размерности много (MDS, t-SNE, UMAP, PCA, Truncated SVD). Но на больших данных мы применяем: SparseRandomProjection. Суть там простая, создается случайная матрица нужного размера и наши вектора на неё умножаются. Размер меняется соответственным образом.

Обработка идет частями. Прочитали строки -> векторизовали в CSR -> снизили размерность -> записали на диск плотные маленькие вектора.

когда узнал как работает SparseRandomProjection)) но вообще там даже лемма Джонсона–Линденштраусса есть, т.е. всё по науке

Ключевой и единственный параметр SparseRandomProjection - это размерность целевого вектора. Определять надо опытным путем. Для тестов можно начать с 32, далее поднимать, контролируя скорость и качество. Обычно, получается от 512 до 10_000.

Поиск неточных дубликатов

Итак, у нас есть набор векторов. Первое желание сделать так:

# full pairwise dot‐product matrix (в нашем случае это как раз косинусная близость)
dot_product = X @ X.T

# либо что-то аналогичное
from scipy.spatial.distance import pdist, squareform
from torch import cdist  # можно даже с GPU
from scipy.spatial.distance import cdist
from sparse_dot_topn import sparse_dot_topn

Проблема в том, что если у нас 5-20 млн. строк, то это всё будет работать долго.

Тут появляется ключевой инструмент, который помогает нам сделать всё быстро и с контролируемой потерей качества - Faiss (python библиотека). Детали есть в этой статье на хабре.

Самый интересный индекс в faiss - IndexIVFPQ, он использует две оптимизации:

• все вектора делятся на части, каждая часть кодируется одним байтом. Например, у нас размерность 10_000, тип данных float32 (4 байта). Итого, 40_000 байт. А если разрежем вектор на 32 части, то получим 32 байта. Огромный выигрыш по размеру и по скорости работы с векторами. Качество немного снижается, конечно.

• все вектора кластеризуются. Определяются представители каждого кластера. Поиск будет проводится только по самым близким кластерам к целевому вектору.

Эти две настройки позволяют обрабатывать огромные объемы данных на CPU (у faiss есть GPU версия, но там сложности с компиляцией, возможно, через conda-forge это и заработает).

Общая логика этого шага - искать все строки в самом этом же списке:

import faiss

d = 128
nlist = 100
m = 8
nbits = 8
train_n = 10000
k = 5  # выбор top N похожих которые хотим найти

idx = faiss.IndexIVFPQ(faiss.IndexFlatL2(d), d, nlist, m, nbits)
idx.train(B[:train_n])  # тренировать можно батчами и только на выборке
idx.add(B)  # добавить надо все вектора, конечно
D, I = idx.search(A, k) # поиск можно батчами делать

Данный поиск даёт только k-NN, т.е. k ближайших соседей для каждой строки в списке.

При дальнейшей обработке результатов надо помнить:

• мы сравниваем список с самим собой, поэтому самый похожий элемент - всегда будет сам этот элемент;

• допустим у нас 100 векторов и мы сделали поиск top3 (100*3=300). Из них 100 элементов сразу можно убрать, т.к. это графовые "петли", элемент похож сам на себя. В остальном уникальных ребер может быть от 200 до 100. Это зависит попало ли ребро в top3 два раза или только один.

На этом ресурсозатратный этап завершен.

Графовая обработка

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

Можно взять все компоненты связности графа и сказать, что это и есть кластера похожих элементов (неточные дубликаты). Проблема в том, "муха" может быть похоже на "слона" через 10 промежуточных текстовых строк.

Поэтому обычно запускается алгоритм поиска сообществ на взвешенном графе (Louvain Community Detection Algorithm, networkx или igraph). Это даёт более обособленные и логичные наборы дубликатов.

Конечно, форматы результатов и финальная предобработка могут отличаться. Например, можно визуализировать граф, который мы получили на этапе k-NN. Это уже несет в себе массу полезной информации.

Один список VS набор списков

Довольно большая развилка состоит в количестве списков, которые мы имеем в начале.

• либо это один список. Дубликаты надо искать в нём (выше как раз эта ситуация);

• либо это несколько списков, Дубликаты надо искать только между ними.

Если возникает вторая ситуация, то меняется этап создания индексов faiss. Для каждого списка создается свой индекс. Сопоставление идет переборов всех пар списков (количество комбинаций из N по 2).

А если данных еще больше?

Этот путь мы не пробовали на практике, но если строк будут будут десятки/сотни миллионов, то скорее всего подход выше не сработает. Потребуется полностью менять архитектуру.

Самым очевидным решением будет LSH (MinHash либо SimHash). Качество снижается ощутимо, но масштабируется на невероятные объемы.

Оценка качества неточного поиска и подбор параметров

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

Мы пытались использовать два подхода, но явного повышения качества не получили:

• разметка человеком. Даём человеку пары, он размечает похоже/не похоже. Мы определяем порог косинусной близости (определяем эталон человеческого восприятия неточных дубликатов).

• создаём синтетические данные. Включаем туда два подготовленных набора пар: которые точно дубликаты и которые точно НЕ дубликаты (определяем экспертно). В идеале, наш механизм должен найти как можно больше дубликатов и не найти ни одного "не дубликата". Это позволяет проверить корректность всего алгоритма от начала до конца.

Чему я научился изучая неточный поиск

Путь от Levenshtein.distance(a, b) до idx.search(A, k) составил более 2 лет. И не завершен даже сейчас. Возникают новые аспекты задачи, новые требования, новые инструменты.

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

1. Всегда надо понимать на какой машине будет исполняться алгоритм (RAM, физические ядра, SSD, GPU);

2. Разработка сложного алгоритма - вечная борьба с OOM и временем исполнения кода;

3. Многопроцессорность - всегда оценивать, можно ли применить;

4. Memory mappings, обработка данных частями - часто без этого ничего не заработает;

5. Файловая система/файлы - полноправные контейнеры данных. Особенно удобны для межпроцессорной передачи данных (IPC) и хранения данных, превышающих RAM (когда обработка возможно только частями);

6. Самый производительный код - это либо numpy, либо torch GPU, либо скомпилированный код на быстрых языках (faiss на С++), polars/duckdb. Забываем про pandas, обычные python list/tuple/set;

7. Байты/биты - основа информации. Желательно понимать, как пишутся и читаются байты. Для меня открытием были: python struct, byte array, byte string;

8. Numpy array - крайне важен для проектирования сложных алгоритмов. (shape, strides, C/Fortran contiguous, dtype, byte order, view VS copy). Недаром говорят, что Numpy - фундаментальная библиотека для научных вычислений;

9. Разряженные матрицы важны (обычно хватает CSR). Именно они позволяют хранить огромное количество высокоразмерных разряженных векторов после TfidfVectorizer;

10. Графы позволяют удобно воспринимать сложные структуры данных. Про них я отдельную статью писал на хабр;

11. Базовая линейная алгебра, матрицы - часто встречаются при работе с векторами (~каждый день).

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

Про нейросети я тоже пишу, в своем tg канале тут, если понравилась статья - рекомендую посмотреть.