LSH (Locality-Sensitive Hashing) — это локально-чувствительное хеширование. Это класс алгоритмов, которые хешируют объекты (векторы, строки, изображения) так, что похожие объекты с высокой вероятностью попадают в одну корзину (bucket), а непохожие — в разные. Это противоположность криптографическим хешам (MD5, SHA), где малейшее изменение входных данных полностью меняет хеш.
LSH-индекс — это структура данных для приближённого поиска ближайших соседей (Approximate Nearest Neighbors, ANN), построенная на основе нескольких LSH-функций. Она позволяет за сублинейное время (часто O(1) или O(log N)) найти все объекты, похожие на запросный, даже в миллиардных коллекциях.
Как устроен LSH (на примере битовых строк и расстояния Хэмминга)
Возьмём простейшую LSH-функцию: случайно выбрать `k` позиций в битовой строке и взять их как `k`-битный хеш.
Два объекта, различающиеся в небольшом числе бит, с хорошей вероятностью будут иметь одинаковые `k`-битные подстроки.
Однако одной такой функции недостаточно: она даёт много ложных срабатываний и пропусков. Поэтому LSH-индекс обычно состоит из:
L хеш-таблиц;
Для каждой таблицы своя комбинация из `k` позиций (или своя проекция).
При вставке объекта для каждой таблицы вычисляется хеш-значение, и объект кладётся в соответствующую корзину.
Поиск в LSH-индексе
Для поиска похожих на запрос `q`:
Для каждой из `L` таблиц вычислить хеш `q`.
Извлечь все объекты из корзин с этими хешами (это кандидаты).
Вычислить точное расстояние между `q` и каждым кандидатом.
Вернуть `K` ближайших (или все с расстоянием ниже порога).
Почему LSH-индекс эффективен?
Время поиска не зависит линейно от размера базы, а определяется параметрами `k` и `L`. Обычно `L` — десятки или сотни.
Гарантия: для любого соседа на расстоянии `R` вероятность найти его выше заданного порога.
LSH-индексы существуют для многих метрик: косинусная близость (SimHash), евклидово (E2LSH), расстояние Хэмминга, Jaccard (MinHash) и др.
Простой пример (битовые строки, длина 64)
Выбираем `k=16` случайных позиций.
Делаем `L=20` таких таблиц.
Объект `A` имеет хеш `0x3F2A` в первой таблице.
Объект `B` отличается от `A` всего в 3 битах — с высокой вероятностью `B` попадёт в ту же корзину хотя бы в одной из 20 таблиц.
Именно так работают LSH-индексы в библиотеках вроде FAISS, Annoy, ScaNN или в реализациях SimHash (например, в поиске дубликатов в Google).
