MinHash: как найти дубликаты текста

MinHash: как найти дубликаты текста — это способ оценить сходство Жаккара между множествами шинглов за линейное время и в небольшом фиксированном объёме памяти, как описывает документация datasketch. Полный цикл поиска дубликатов состоит из нормализации, шинглов, точного Jaccard, сигнатур MinHash, порога и проверки кандидатов.

Что именно считает MinHash и где проходят границы метода

Документация datasketch определяет MinHash как оценку сходства Жаккара между множествами произвольного размера за линейное время и в небольшом фиксированном объёме памяти. Метод предложил Андрей Бродер, ссылка на его работу есть на той же странице. Оценка строится вероятностно: каждый слот подписи хранит минимум, который увидела соответствующая перестановка, и доля совпавших слотов служит оценкой сходства.

Ключевое свойство описано там же: два множества попадают одним и тем же значением в слот k с вероятностью, равной их сходству Жаккара. Каждая перестановка в схеме affine является биекцией, поэтому шаг перестановки не добавляет собственных коллизий. Источниками ошибки остаются шум выборки из num_perm слотов и коллизии во входной хеш-функции.

Границы метода видны в разделе о схеме affine32. Ширина схемы w задаёт пространство входного хеша, и это пространство служит единственным ограничением ёмкости. При w=32 доступно около 4.3 миллиарда различных отпечатков, поэтому с ростом множеств разные элементы всё чаще получают одинаковый отпечаток, и подпись перестаёт их различать. Два множества без общих элементов всё равно делят часть отпечатков, и их оценка поднимается выше нуля. Этот неизбежный уровень документация называет saturation floor.

В числах 32-битный уровень составляет примерно +0.001 при 10 миллионах элементов на множество, +0.01 при 100 миллионах и +0.12 при миллиарде. До примерно 100 миллионов элементов на множество уровень остаётся ниже ошибки выборки подписи с num_perm=128, которая составляет около 0.03–0.04. Схема affine64 работает по 64-битным значениям, требует вдвое больше памяти на подпись и обновляется медленнее в 1.3–2 раза по сравнению с affine32, а её измерение читается как 0.0000 вплоть до 10 миллиардов элементов на множество.

Отдельная граница касается совместимости. Объекты MinHash, созданные с разными схемами, нельзя сравнивать, объединять или соединять: jaccard(), merge() и union() поднимают ValueError при несовпадении схемы. Все хеш-значения схемы по умолчанию изменились в версии 2.0.0, поэтому подписи и LSH-индексы, сохранённые более ранними версиями, смешиваются с новыми только при явной передаче scheme=»legacy». Для перехода на новое значение по умолчанию документация советует пересчитать подписи из исходных данных и перестроить сохранённый LSH-индекс.

Практический вывод для читателя: MinHash отвечает на вопрос о лексическом сходстве нормализованных множеств. Семантические парафразы, переводы и пересказы другими словами остаются за пределами этой оценки. Документация NeMo Curator разделяет три подхода: точное совпадение по MD5, нечёткое совпадение по MinHash и LSH, семантическое совпадение по эмбеддингам. MinHash попадает во вторую категорию и нацелен на документы с небольшими правками форматирования или опечатками.

Полный учебный ввод и ручной эталон

Учебный корпус состоит из четырёх текстов. Три базовых: D1=’red blue green’, D2=’red blue green yellow’, D3=’black white’. Положительный дубликат: D4=’RED BLUE GREEN’. Политика нормализации и хранения одинакова во всех частях примера.

Нормализация приводит текст к нижнему регистру и строит word bigrams. Для D1 получается множество S1={red blue, blue green}, для D2 — S2={red blue, blue green, green yellow}, для D3 — S3={black white}. Точный Jaccard даёт D1/D2=2/3≈0.667, D1/D3=0, D2/D3=0.

Две hash-перестановки заданы на универсуме шинглов. Первая: h1(red blue)=1, h1(blue green)=3, h1(green yellow)=4, h1(black white)=2. Вторая: h2(red blue)=4, h2(blue green)=1, h2(green yellow)=3, h2(black white)=2. Минимумы по слотам дают сигнатуры D1=(1,1), D2=(1,1), D3=(2,2).

Оценка D1/D2=1.0 расходится с точным значением 2/3. Это иллюстрация ошибки короткой подписи: две перестановки дают слишком грубую выборку, и совпадение всех слотов случается при неполном сходстве множеств. Игрушечные перестановки здесь являются детерминированными функциями. Качество промышленной конфигурации ими не подтверждается.

Ручной эталон вывода кода: D1/D2 0.6666666666666666 KEEP; D1/D3 0.0 KEEP; D2/D3 0.0 KEEP. Положительный случай задан полностью: D4=’RED BLUE GREEN’ после той же нормализации даёт шинглы {red blue, blue green}, совпадающие с D1. Точный Jaccard(D1,D4)=1.0, игрушечная подпись D4=(1,1). При пороге 0.8 пара D1/D4 проходит точную проверку. Политика хранения задана явно: сохраняем меньший ID D1, удаляем D4. Дополнительная строка вывода: D1 D4 1.0 REMOVE.

Слово REMOVE в выводе означает удаление второго ID при этой явной политике. Пара D1/D2 остаётся KEEP из-за точного значения 2/3. Положительный случай не меняет иллюстрацию ложного кандидата короткой подписи.

Порядок действий в примере: нормализовать текст, построить шинглы, посчитать точный Jaccard, построить сигнатуры MinHash, сравнить оценку с точным значением, применить порог 0.8, проверить кандидатов точным Jaccard. Этот порядок важен: порог применяется к оценке, а окончательное решение принимается по точному значению.

Копируемый код и конкретные действия проверки

Код ниже считает точный Jaccard по word bigrams и печатает решение по каждой паре. Он не требует внешних библиотек и запускается на чистом Python.

documents = {
    'D1': 'red blue green',
    'D2': 'red blue green yellow',
    'D3': 'black white',
    'D4': 'RED BLUE GREEN',
}

def shingles(text):
    words = text.lower().split()
    return set(zip(words, words[1:]))

def jaccard(left, right):
    union = left | right
    return len(left & right) / len(union) if union else 1.0

sets = {key: shingles(text) for key, text in documents.items()}

for a, b in [('D1', 'D2'), ('D1', 'D3'), ('D2', 'D3'), ('D1', 'D4')]:
    exact = jaccard(sets[a], sets[b])
    print(a, b, exact, 'REMOVE' if exact >= 0.8 else 'KEEP')

Что проверить после запуска. Первая строка вывода должна показать D1 D2 0.6666666666666666 KEEP. Вторая и третья — D1 D3 0.0 KEEP и D2 D3 0.0 KEEP. Четвёртая — D1 D4 1.0 REMOVE. Если хотя бы одна строка отличается, проверьте нормализацию: регистр приводится к нижнему до построения шинглов, иначе D4 не совпадёт с D1.

Отдельно проверьте, что шинглы строятся по словам. Символьная схема дала бы другой набор. Для D1=’red blue green’ функция shingles возвращает ровно два элемента: (‘red’, ‘blue’) и (‘blue’, ‘green’). Текст из двух слов даёт один шингл, текст из одного слова даёт пустое множество, и функция jaccard возвращает для него 1.0 при пустом объединении. Это явно выбранное поведение учебного примера. Для других задач правило обработки пустых множеств задают отдельно.

Проверка положительного случая. D4 отличается от D1 только регистром. После нормализации их множества шинглов совпадают, точный Jaccard равен 1.0, и пара проходит порог. Это ожидаемый результат: положительный дубликат удаляется.

Проверка отрицательного случая. D1 и D2 различаются одним словом, и их точный Jaccard равен 2/3. При пороге 0.8 пара остаётся. Здесь важно не подменять точное значение оценкой MinHash: игрушечная подпись даёт 1.0, и решение по ней удалило бы пару ошибочно.

Действия проверки по шагам:

1. Запустите код и сравните вывод с ручным эталоном из предыдущего раздела.
2. Замените порог 0.8 на 0.6 и убедитесь, что пара D1/D2 меняет решение на REMOVE.
3. Уберите приведение к нижнему регистру и проверьте, что пара D1/D4 перестаёт совпадать.
4. Добавьте пятый текст в documents и включите пары с его ID в явный список цикла for. Затем сравните новые строки вывода с ручным эталоном.

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

Положительный и отрицательный случаи без обещаний о выходе

Положительный случай полностью определён: D4=’RED BLUE GREEN’ после нормализации даёт те же шинглы, что D1, точный Jaccard равен 1.0, и при пороге 0.8 пара D1/D4 удаляется по явной политике хранения меньшего ID. Здесь нет вероятностной неопределённости: точное значение 1.0 превышает заданный порог 0.8.

Отрицательный случай строится на паре D1/D2. Точный Jaccard равен 2/3, что ниже порога 0.8, и пара остаётся. Оценка MinHash для этой пары равна 1.0 из-за короткой подписи. Если бы решение принималось по оценке без точной проверки, пара была бы удалена ошибочно. Это и есть отрицательная проба: она показывает, что оценка MinHash служит фильтром кандидатов, а окончательное решение требует точного значения.

Документация datasketch описывает этот разрыв как следствие шума выборки. Доля совпавших слотов оценивает сходство Жаккара, и при малом числе перестановок оценка может сильно отклоняться от истины. Увеличение num_perm повышает точность, но память, размер сериализации и стоимость операций над всей подписью растут линейно с num_perm. Время обновления менее чувствительно: применение перестановок векторизовано, и удвоение num_perm со 128 до 256 добавляет примерно 10–35% к времени update_batch по измерениям документации.

Что это значит для читателя. Оценка MinHash в этой процедуре используется для отбора кандидатов. Окончательное решение принимается после точной проверки. Порядок «оценка, затем точная проверка» защищает от ложных удалений. Решение по одной короткой подписи может привести к ложному удалению пары с умеренным точным сходством.

Документация datasketch отдельно предупреждает о высокой ошибке оценки, когда размеры множеств сильно различаются. В этом случае она советует использовать принцип включения-исключения через функции merge() и count() вместо jaccard(). Это ещё одна граница метода: сравнение множеств разного масштаба требует другой процедуры.

Статья Hugging Face о near-deduplication для BigCode описывает похожую логику на реальном конвейере. Автор перечисляет три этапа: шинглирование и отпечатки, LSH для группировки похожих документов, удаление дубликатов. Там же приведён пример с тремя документами на английском и word-level триграммами без пунктуации. Этот пример принадлежит Hugging Face и не присваивается здесь.

Учебная конвенция и настройки по умолчанию

Учебный пример использует две перестановки и порог 0.8. Это конвенция примера, выбранная для наглядности. Документация datasketch указывает, что значение по умолчанию для num_perm равно 128, а пример с num_perm=256 описан как дающий лучшую точность. Две перестановки в учебном корпусе не являются настройкой продукта и не претендуют на промышленную надёжность.

Схема по умолчанию в datasketch 2.0.0 — affine32. Она хранит хеш-значения как uint32 и даёт ту же точность, что affine64, в половине памяти для большинства рабочих нагрузок. Схема affine64 применяется, когда множества растут за десятки миллионов элементов или когда важна положительная погрешность на уровне процента. Её хеш-функция по умолчанию — datasketch.hashfunc.sha1_hash64(), и пользовательская hashfunc должна возвращать 64-битные целые.

Хеш-функция по умолчанию — SHA1 из стандартной библиотеки hashlib. Документация отмечает, что точность одинакова для SHA1, MurmurHash3, xxhash и Farmhash, а различия во времени малы, поскольку на коротких входах доминирует накладные расходы на обновление. Выбор хеш-функции заметнее на длинных входах или при массовом хешировании вне update().

GPU-режим в datasketch описан как экспериментальный. Он управляется аргументом gpu_mode со значениями ‘disable’ (по умолчанию), ‘detect’ и ‘always’. Хеширование и генерация перестановок остаются на CPU, а на GPU могут выполняться применение перестановок и минимизация. CuPy — опциональная зависимость, не устанавливаемая по умолчанию.

Документация NeMo Curator описывает собственный продукт с GPU-ускорением и требует GPU для всех трёх подходов к дедупликации. Её примеры используют RayClient, FuzzyDeduplicationWorkflow и параметры char_ngrams=24, num_bands=20, minhashes_per_band=13. Эти значения относятся к NeMo Curator и не переносятся на учебный пример с datasketch или чистым Python.

Разделение важно для читателя: учебные значения показывают механику, настройки продукта определяют поведение библиотеки, а параметры NeMo Curator относятся к конкретному GPU-конвейеру. Смешивать их в одном расчёте нельзя.

Как устроены сигнатуры и LSH на уровне шагов

Документация datasketch описывает обновление подписи как четыре шага. Хеш-функция отображает значение в хеш h шириной w бит: 32 бита для affine32, 64 бита для affine64. Затем h один раз смешивается финализатором MurmurHash3 (fmix), фиксированной биекцией, которая распределяет каждый бит входа по всему слову. Это защищает оценку, когда хеш-функция слаба относительно входа, например при последовательных целочисленных ключах с тождественной хеш-функцией.

Далее каждая из num_perm перестановок отображает смешанное значение h’ в a_k * h’ + b_k по модулю 2w, вычисляемый в w-битной беззнаковой арифметике, где переполнение играет роль модуля. Множитель a_k нечётен, поэтому отображение является биекцией на [0, 2w), и различные хеш-значения не могут столкнуться после перестановки. Каждый слот подписи хранит минимум, который видела его перестановка.

Статья Hugging Face описывает тот же процесс на своём примере. Шинглы хешируются, затем каждый хеш переставляется пять раз, и по каждому столбцу берётся минимум. Автор отмечает, что минимум — распространённый выбор, а в качестве альтернатив возможны максимум и k-е порядковые статистики.

LSH в описании Hugging Face разбивает массив отпечатков на полосы одинакового размера. Документы, совпадающие по хешам в полосе с определённым индексом, попадают в один бакет и считаются кандидатами. В примере с b=2 полосами и r=2 строками документы 0 и 1 образуют одну пару кандидатов.

Дальше автор перечисляет два пути работы с кандидатами. Первый — перепроверить фактическое сходство Жаккара по пересечению шинглов, поскольку MinHash даёт оценку. Второй — считать пары истинно положительными. Автор отмечает, что сходство Жаккара не транзитивно: A похож на B, B похож на C, а A и C могут не разделять сходство. По экспериментам на The Stack обработка всех пар как дубликатов улучшала качество итоговой модели, и этот путь экономит время. Для собственного набора данных автор советует изучить дубликаты и принять решение по данным.

Кластеризация кандидатов описана через граф с парами в качестве рёбер и поиск компонент связности. Автор перечисляет четыре варианта: обход датасета с библиотекой графов, фреймворки вроде dask, структура union find и Spark для больших наборов. Для средних наборов union find добавляет незначительные накладные расходы к обходу.

Документация NeMo Curator описывает похожий конвейер в своём продукте: генерация подписей MinHash, поиск похожих документов через LSH, затем удаление. Метаданные результата включают minhash_time, lsh_time и connected_components_pipeline_time. Эти имена относятся к NeMo Curator и приведены здесь как описание его устройства.

Частые вопросы

Что такое MinHash простыми словами?

MinHash — способ оценить сходство Жаккара между двумя множествами без полного сравнения всех элементов. Каждое множество превращается в короткую подпись из минимумов нескольких перестановок, и доля совпавших слотов служит оценкой сходства. Документация datasketch описывает метод как оценку за линейное время в небольшом фиксированном объёме памяти. Метод предложил Андрей Бродер.

Чем MinHash отличается от точного сравнения по хешу?

Точное сравнение по хешу находит документы, совпадающие посимвольно, и документация NeMo Curator относит к этому подходу MD5-хеширование. MinHash находит почти-дубликаты с небольшими правками, опечатками и различиями форматирования. NeMo Curator описывает нечёткий подход как MinHash плюс LSH и указывает сходство около 80%. Выбор зависит от того, какие дубликаты нужно поймать.

Сколько перестановок нужно для точной оценки?

Документация datasketch указывает значение по умолчанию 128 и приводит пример с num_perm=256 как дающий лучшую точность. Память, размер сериализации и стоимость операций над всей подписью растут линейно с num_perm, а время обновления менее чувствительно. Учебный пример с двумя перестановками показывает механику и иллюстрирует ошибку короткой подписи. Для рабочего набора число перестановок подбирают под требуемую точность.

Почему оценка MinHash расходится с точным Jaccard?

Оценка строится по выборке из num_perm слотов, и при малом числе перестановок шум выборки велик. В учебном примере пара D1/D2 имеет точное значение 2/3, а игрушечная подпись даёт 1.0. Документация datasketch называет источниками ошибки шум выборки и коллизии входной хеш-функции. Точная проверка кандидатов снимает этот разрыв.

Можно ли использовать MinHash для поиска парафраз?

MinHash оценивает лексическое сходство нормализованных множеств шинглов. Парафразы, переводы и пересказы другими словами меняют набор шинглов, и оценка падает. Документация NeMo Curator относит такие случаи к семантической дедупликации на эмбеддингах. Статья Hugging Face также выделяет семантическую дедупликацию в отдельное направление исследований. Для парафраз нужен другой метод.