Что решает
дедупликация
Статьи
STR
Алгоритм
Алгоритм Рабина — Карпа
Хеш окна катится по тексту, буквы сравниваются только при совпадении хеша; тысячи образцов — за один проход.
O(n + m) в среднем
1 задача
PAR
Алгоритм
Ближайшая пара точек
Две ближайшие точки из n за n log n: разрез, полоса шириной 2d и семь соседей; сеткой — за n в среднем.
O(n log n)
2 задачи
SYS
Алгоритм
MinHash и LSH
Подпись из K минимумов хешей: доля совпавших — оценка сходства Жаккара; полосы LSH сводят похожие пары в одни корзины.
O(K·S) на подписи, O(n·b) на корзины, плюс проверка кандидатов
2 задачи
Задачи
Часто рядом
хеширование 3 случайность 3 похожесть 2 классика 2 собеседования 2 в проде 2 поиск в тексте 1 скользящее окно 1 ближайший сосед 1 точки на плоскости 1 разделяй и властвуй 1 геоданные 1