Реализация Minhash, как найти хеш-функции для перестановок

Question

У меня проблема с реализацией minhashing. На бумаге и после прочтения я понимаю концепцию, но моя проблема заключается в "фокусе" перестановки. Вместо того, чтобы переставлять матрицу множеств и значений, предложение для реализации: "выбрать k (например, 100) независимых хеш-функций", а затем алгоритм говорит:

for each row r 
    for each column c 
        if c has 1 in row r 
           for each hash function h_i  do
            if h_i(r) is a smaller value than M (i, c) then
            M(i, c) := h_i(r)

В разных небольших примерах и учебниках они используют только две или три хеш-функции в виде (h = a*x + b mod p). Это легко найти, но как это сделать на практике, как я могу найти 100 таких независимых функций.

В примере Java здесь генерируются хеш-значения только из одной хеш-функции вместо нескольких хеш-функций, независимо от индекса строки. В чем разница? Теперь у меня вопрос, как найти эти независимые хеш-функции или, если есть подход только с одной хеш-функцией, как обрабатывать эти значения в алгоритме?

Answer 1

Одним простым способом является использование параметрического семейства хэшей, такого как функции хэширования таблиц ( http://en.wikipedia.org/wiki/Tabulation_hashing)

В примере книги (a*x+b mod p), выбрав разные наборы (a, b, p), вы можете иметь разные хеш-функции. Один из способов иметь независимые хеш-функции - это выбрать (a, b, p) простое / взаимно простое число и предпочтительно большие числа

Answer 2

Согласно ответу iampat, вы можете использовать хэширование таблиц ( http://en.wikipedia.org/wiki/Tabulation_hashing).

Другой очень эффективный вариант, который дает хорошие результаты, - это использовать одну хэш-функцию хорошего качества (например, FNV_1a) для создания главного хэша, а затем изменить его, используя 100 различных комбинаций XOR и битролла.

Чтобы сгенерировать каждый хеш, вы берете главный хеш, разбиваете его на заданное расстояние, затем XOR с заданным значением. Значения bitroll и XOR выбираются случайным образом для каждой из 100 хеш-функций. Смотрите это обсуждение для получения дополнительной информации.

Некоторые люди рекомендуют умножение вместо XOR, в этом случае вы можете выбрать простые числа.