Генерация случайных хеш-функций для алгоритма LSH Minhash
Я программирую алгоритм хеширования в Java, который требует от меня генерирования произвольного числа случайных хеш-функций (в моем случае 240 хеш-функций) и запускаю любое количество целых чисел через него (в настоящий момент 2000).
Для этого я генерировал случайные числа a, b и c (от 1 до 2001) для каждой из 240 хеш-функций. Затем моя хеш-функция возвращает h = ((a*x) + b) % c, где h - возвращаемое значение, а x - одно из целых чисел, проходящих через него.
Является ли это эффективной реализацией случайного хеширования или есть более распространенный / приемлемый способ сделать это?
В этом посте был задан похожий вопрос, но я все еще несколько озадачен формулировкой ответа: реализация Minhash, как найти хеш-функции для перестановок
2 ответа
Когда я работал с фильтрами Блума несколько лет назад, я наткнулся на статью, в которой описано, как очень просто сгенерировать несколько хеш-функций с минимумом кода. Метод, который он описывает, работает очень хорошо. См. Меньше хеширования, та же производительность: создание лучшего фильтра Блума.
Основная идея состоит в том, чтобы создать две хеш-функции, вызвать их h1 а также h2, с помощью которого вы можете затем имитировать несколько хэш-функций, g1 через gkпо формуле:
gi = h1(x) + i*h2(x)
i варьируется от 1 до k (количество хеш-функций, которые вы хотите).
Документ стоит прочитать, даже если вы решите не реализовывать свою идею. Хотя после прочтения я не могу представить, что не хочу это реализовывать. Это сделало мой код фильтра Bloom намного более гибким и не оказало негативного влияния на производительность.
Таким образом, метод, который я описал выше, был почти правильным. Числа a и b должны генерироваться случайным образом. Однако c должно быть простым числом, которое немного больше максимально возможного значения x. После того, как эти числа были выбраны, поиск значения хеша h с использованием h = ((a*x)+b) % c является стандартным, принятым способом генерации хеш-функций.
Кроме того, a и b должны быть случайными числами в диапазоне от 1 до c-1.