MinHash и LSH

В исходниках Go 3093 файла, если не считать тестов и совсем маленьких. Пар из них — 4 781 778. Какие файлы почти одинаковы? Сравнить каждую пару честно — миллионы пересечений множеств по тысяче элементов. Ниже — то же самое меньше чем за две тысячи сравнений. Каждый файл — точка на круге, в порядке путей; хорда соединяет пару, которую алгоритм счёл подозрительной. Цвет — насколько файлы похожи на самом деле.

При 12 полосах по 4 строки подозрительных пар 1848 — четыре сотых процента всех. Среди них 1384 из 1537 пар, которые совпадают хотя бы наполовину. Короткие хорды у края — семейства файлов одного каталога: syscall и вендоренный x/sys/unix хранят по файлу на каждую пару «система, процессор», и эти файлы порождены генераторами. Длинные хорды — копии через всё дерево. Типизатор Go живёт дважды: в go/types для инструментов и в cmd/compile/internal/types2 для компилятора, и 39 файлов первого начинаются со слов «Code generated… Source: ../../cmd/compile/internal/types2». А cmd/gofmt/internal.go и go/format/internal.go совпадают на 0,994, и в обоих написано: эти файлы одинаковы, кроме комментария и имени пакета, — не меняйте один без другого.

Идея

Сходство двух документов меряют по шинглам — кусочкам из нескольких токенов подряд, как черепица на крыше. Здесь шингл — пять токенов Go подряд, а комментарии выброшены. Сходство Жаккара — доля общих шинглов среди всех: J(A, B) = |A ∩ B| / |A ∪ B|. Как к этому пришли и при чём тут сочинения о дубе, — в главе курса «Иголка в стоге». Здесь вопрос другой: как найти похожие пары, когда пар миллионы.

Два шага. MinHash сжимает каждое множество шинглов в подпись из K чисел: i-е число — наименьший хеш шинглов документа по i-й хеш-функции. У двух документов i-е числа совпадают с вероятностью, в точности равной J, и доля совпавших позиций оценивает сходство без самих множеств. LSH режет подпись на b полос по r чисел и раскладывает документы по корзинам по каждой полосе. Пара становится кандидатом, если хоть одна её полоса совпала целиком. Похожие документы почти наверняка встретятся, непохожие — почти никогда, и точно проверять нужно только кандидатов.

Почему минимум

Проверьте это руками на двух настоящих файлах. bytes/reader.go и strings/reader.go — читатели из байтового среза и из строки, написанные по одному образцу. У первого 601 шингл, у второго 578, общих 495, и J = 495/684 ≈ 0,724. Каждая перестановка выбирает первый шингл объединения; если он общий, это «совпадение минимумов».

Одна перестановка — бросок монетки, которая выпадает «общим» с вероятностью J. K перестановок дают долю совпадений со стандартным отклонением √(J(1 − J)/K): при K = 48 и J = 0,72 это 0,065. Листинг ниже получает для этой пары оценку 0,792 — на одно отклонение выше правды, а для bytes/iter.go и strings/iter.go — 0,562 при настоящих 0,648. Точности хватает, чтобы отличить почти одинаковое от разного, а не чтобы мерить сходство до сотых. Настоящих перестановок, конечно, никто не делает: вместо K перестановок берут K хеш-функций — здесь одну и ту же перемешивающую функцию с K разными затравками.

Подпись из 48 чисел заменяет файл в среднем из 2255 шинглов. Можно хранить не всё число, а несколько его младших бит: совпадение минимумов они сохраняют, а случайное совпадение бит добавляет к оценке 2^−w для w бит. Сцена выше хранит по 16 бит — поправка меньше двух стотысячных. Этот приём — b-битный MinHash Пина Ли и Арнда Кристиана Кёнига, 2010 год; они хранили и по одному биту, расплачиваясь более длинной подписью.

Полосы и S-кривая

Подписи сократили каждое сравнение до 48 чисел, но пар по-прежнему 4,8 миллиона. Второй шаг убирает сами пары. Режем подпись на b полос по r чисел. Для каждой полосы раскладываем документы по корзинам — в одну корзину попадают документы с одинаковой полосой. Кандидаты — пары, оказавшиеся вместе хоть в одной корзине.

Вероятность легко посчитать. Пусть сходство пары s. Одна полоса совпадает целиком с вероятностью s^r — все r минимумов должны совпасть. Не совпадает — 1 − s^r, ни одна из b полос — (1 − s^r)^b. Значит, кандидатом пара становится с вероятностью

$$P(s) = 1 - \left(1 - s^{r}\right)^{b}.$$

Это S-образная кривая: почти ноль при малых s, почти единица при больших и крутой подъём около порога s ≈ (1/b)^1/r. Чем длиннее полоса, тем правее порог; чем больше полос, тем он левее. При 12 полосах по 4 строки пара со сходством 0,8 становится кандидатом с вероятностью 0,998, а пара со сходством 0,2 — с вероятностью 0,019. Точки на графике — настоящие пары файлов Go: видно, что кривая честно предсказывает долю найденных.

Полоса из одной строки бесполезна: два файла Go почти всегда делят какой-нибудь частый шингл вроде if err != nil {, и 48 попыток совпасть хоть раз дают 388 тысяч кандидатов. Длинные полосы режут шум, но теряют пары у порога: при 4 × 12 остаются только почти точные копии. Выбирают так, чтобы порог стоял чуть ниже нужного сходства: потерянную пару уже не вернуть, а лишнего кандидата отсеет точная проверка. Здесь 16 × 3 находит 99 % пар от 0,5 ценой 3133 проверок — в полторы тысячи раз меньше, чем все пары.

Когда нужен точный ответ

LSH иногда теряет пары — это плата за скорость. Если терять нельзя, есть точный способ для того же вопроса «все пары со сходством не меньше t», и он опирается на два простых неравенства.

Размер. J(A, B) ≤ min(|A|, |B|) / max(|A|, |B|): общих шинглов не больше, чем в меньшем, а в объединении не меньше, чем в большем. Пары, где одно множество вдвое больше другого, до 0,5 не дотянут — их не надо даже открывать. Этим фильтром пользуется листинг ниже, когда для проверки считает все пары.

Префикс. Упорядочим все шинглы одним общим порядком — удобнее всего от редких к частым — и запишем каждое множество в этом порядке. Если J(A, B) ≥ t, у A и B не меньше ⌈t·|A|⌉ общих элементов. Тогда среди первых |A| − ⌈t·|A|⌉ + 1 элементов A хотя бы один общий: иначе все общие поместились бы в оставшиеся ⌈t·|A|⌉ − 1 мест. То же верно для B, а общий элемент, который стоит раньше всех, лежит в префиксах обоих. Значит, достаточно построить инвертированный индекс только по префиксам и брать в кандидаты пары, у которых префиксы пересеклись. Редкие элементы в начале делают списки индекса короткими. Это префиксный фильтр Сураджита Чаудхури, Венкатеша Ганти и Рагхава Каушика, 2006 год; Роберто Байардо, Иминь Ма и Рамакришнан Шрикант в 2007-м показали, как с ним перебирать все пары в больших коллекциях. Попробуйте в задаче о похожих паролях.

Точный способ хорош, пока множества короткие или порог высокий. На длинных документах с порогом 0,5 префикс — половина множества, и выигрыш тает; тогда остаётся MinHash.

Код

Листинг делает всё то же на шести каталогах — bytes, strings, обе версии math/rand, go/types и types2: шинглы, подписи из 48 минимумов, LSH 12 × 4 и для сравнения — честный перебор всех пар с фильтром по размеру. Файлы читаются прямо из исходников Go, которые лежат в песочнице вместе с компилятором.

Из 9591 пары кандидатами стали 59, и это ровно все 59 пар со сходством от 0,5. В Python подпись считает numpy: 48 хеш-функций сразу над всеми шинглами файла — одна операция над матрицей. В Go то же самое — два вложенных цикла. Хеш-функции — перемешивание splitmix64 с разными затравками; шингл перед этим сворачивается в 32 бита CRC-32.

Сколько это стоит

Подписи — O(K·S), где S — всего шинглов во всех документах: в дереве Go их почти семь миллионов, и это самая дорогая часть. Корзины — O(n·b) с хеш-таблицей на каждую полосу. Кандидатов — сколько получится: в среднем по P(s) на каждую пару со сходством s, и при удачных b и r это немногим больше числа настоящих пар. Проверка — точное сходство для каждого кандидата. Память — K чисел на документ, в сцене по 16 бит: 96 байт вместо в среднем 23 КБ исходника.

Где ломается. Сходство Жаккара по шинглам видит совпадение текста, а не смысла: переименуйте все переменные — и шинглы станут другими. Огромные корзины разгоняют число кандидатов квадратично: у файлов из одних шаблонных строк одна и та же полоса, и корзина на тысячу файлов — это полмиллиона пар. Поэтому пустые и почти пустые документы, например файлы doc.go из одних комментариев, лучше убирать заранее: их подписи совпадают случайно.

Где работает

Поисковики. Андрей Бродер с коллегами в 1997 году кластеризовали так страницы, собранные пауком AltaVista: шинглы, сходство и выборка минимумов. Гурмит Манку, Арвинд Джайн и Аниш Дас Сарма в 2007 году описали, как Google отсеивает почти одинаковые страницы при обходе веба другим отпечатком того же рода — SimHash Мозеса Чарикара, где близость меряют числом различающихся бит.

Данные. В Apache Spark с версии 2.1 есть MinHashLSH — подписи и полосы над столбцом таблицы. Большие наборы текстов, в том числе для обучения языковых моделей, чистят от почти одинаковых документов MinHash с LSH: один и тот же текст, скопированный на тысячу сайтов, иначе весит в тысячу раз больше.

Код и тексты. Поиск клонов в коде, заимствований в студенческих работах, похожих объявлений и товаров в каталоге — везде, где нужно найти «почти то же самое» среди многих тысяч.

История

Меру сходства множеств ввёл ботаник Поль Жаккар в 1901 году. Андрей Бродер в 1997 году предложил сравнивать документы через минимумы хешей их шинглов и вместе со Стивеном Глассманом, Марком Манассом и Джеффри Цвейгом применил это ко всему, что собрал паук AltaVista. В 1998 году Бродер, Мозес Чарикар, Алан Фриз и Майкл Митценмахер разобрали, какие семейства перестановок для этого годятся. Тогда же Пётр Индык и Раджив Мотвани предложили хеширование с учётом близости — LSH — для поиска ближайших соседей. Разбиение подписи на полосы и S-кривая подробно разобраны в учебнике Ананда Раджарамана и Джеффри Ульмана «Mining of Massive Datasets».

Задачи