Это 6-й день моего участия в ноябрьском испытании обновлений.Подробности о событии:Вызов последнего обновления 2021 г.
Супер подробное и простое для понимания введение в алгоритм min-hash [1]
Супер подробное и простое для понимания введение в алгоритм min-hash [2]
Супер подробное и простое для понимания введение в алгоритм min-hash [3]
Супер подробное и простое для понимания введение в алгоритм min-hash [4]
Практический алгоритм минимального хеширования
В предыдущем разделе мы упоминали, что перетасовка матрицы по строкам — операция, требующая значительных вычислительных ресурсов. Следовательно, если мы хотим применить алгоритм min-hash на практике, мы должныНайдите другую хеш-функцию, чтобы заменить операцию перетасовки, как новая минимальная хеш-операция для получения хеш-подписи. Итак, какие методы используются в практических приложениях? Это то, что мы собираемся рассмотреть в этом разделе.
В практических приложениях обычно используетсяОдна группаХэш-функция случайной карты с хорошей однородностью на исходном наборекаждый элементДля хэш-операции после использования каждой хэш-функции для выполнения хэш-операции над всем набором выбирается минимальное значение в результирующем наборе и добавляется к новому набору. После хеширования всего набора хеш-функций новый полученный набор является нашей хеш-подписью.
Например, у нас есть набор хеш-функцийhi(xj),hiпредставляет собой набор хеш-функций (при условииkКусок),xjПредставляет элемент в коллекции, для которого нам нужно вычислить хеш-подпись. Сначала хешируйте все элементы в наборе, используя h1, затемВыберите наименьшее значение и добавьте его в новый набор. Далее с помощью h2 повторите описанную выше операцию, а также добавьте к этому новому набору минимальное значение в результате.До конца hk наш новый набор состоит из k элементов, и этот новый набор является нашимхеш-подпись, вышеуказанная операция является нашей новойминимальная хэш-операция.
Вышеизложенное является лишь кратким описанием идей в практических приложениях, но нам еще предстоит решить следующие задачи:
- Сходство между хэш-подписями исходного набора после этой новой операции минимального хэширования остается таким же, как и у исходного набора?
- Как выбрать такой набор хеш-функций?
Теперь давайте сначала разберемся с первым вопросом.
Предположим, у нас есть два множества C1 и C2, которым нужно вычислить сходство, тогда они соответственно записываются какоднаждыМинимальная операция хеширования, полученное значение записывается как min-hash (C1) и min-hash (C2). В силу равновероятности случайности вероятность того, что min-хеш (C1) равна min-хэшу (C2), равна
Вы можете понять приведенную выше формулу с этой точки зрения.Используйте ту же хеш-функцию для выполнения минимальной хеш-операции над множествами C1 и C2 (обратите внимание, что это операция, а не операция), и все полученные результаты являются множествами C1 и С2 в комплекте.КоллекцияизминимумВероятность того, что соответствующий элемент принадлежит пересечению двух множеств, равна.
Что ж, после доказательства первой проблемы, давайте решим вторую проблему: как выбрать такой набор хеш-функций.
На самом деле, исходя из опыта, мы обычно используем следующую формулу, чтобы получить необходимое количество хеш-функций путем прямого изменения коэффициентов:
В практических приложениях мы можем получить бесконечное количество хэш-функций, регулируя два коэффициента coe и mod, всего три параметра.
На этом знакомство с алгоритмом min-hash действительно закончено, и в следующем разделе мы приведем реальный пример кода, чтобы вы лучше его поняли.