Сколько хэш-функций требуется в алгоритме minhash

Ответ 1

Довольно много, но 28% были бы "оценкой ошибок", то есть сообщаемые измерения часто бывают неточными на +/- 28%.

Это означает, что зарегистрированное измерение 78% может легко получить только с 50% сходства. Или что 50% сходства можно легко сообщить как 22%. Для меня это не соответствует действительности для бизнеса.

Математически, если вы сообщаете две цифры, вторая должна иметь смысл.

Почему вы хотите уменьшить количество хеш-функций до 12? "200 хеш-функций" на самом деле означает, вычисляет хэш-код приличного качества для каждой гальки/строки один раз - затем применяет 200 дешевых и быстрых преобразований, чтобы подчеркнуть определенные факторы/довести некоторые бит до фронта.

Я рекомендую комбинировать побитовые вращения (или перетасовку) и операцию XOR. Каждая хэш-функция может комбинировать вращение на некоторое количество бит, а затем XORing с помощью произвольно генерируемого целого числа.

Это и "распространяет" селективность функции min() вокруг битов, и на какое значение min() заканчивается выбором.

Обоснованием для вращения является то, что "min (Int)" будет в 255 раз превышать 256, выбирать только в пределах 8 наиболее значимых бит. Только если все верхние биты совпадают, то нижние биты имеют какой-либо эффект в сравнении. Поэтому распространение может быть полезно, чтобы избежать неоправданного акцента только на один или два символа в галерее.

Обоснование для XOR состоит в том, что по его поименному побитовое вращение (ROTR) может составлять 50% времени (когда 0 бит сдвинуты слева) сходится к нулю, и это приведет к "раздельным" хэш-функциям проявляют нежелательную тенденцию к совпадению к нулю вместе - таким образом, чрезмерная тенденция для них в конечном итоге выбирать один и тот же гальки, а не независимую черепицу.

Здесь очень интересная "поразрядная" причуда со знаком целых чисел, где MSB отрицателен, но все следующие биты положительны, что делает тенденцию вращения сходиться гораздо менее заметной для целых целых чисел - где это было бы очевидно для unsigned, Тем не менее, XOR все равно должен использоваться в этих обстоятельствах.

В Java встроены 32-битные хэш-коды. И если вы используете библиотеки Google Guava, доступны 64-битные хэш-коды.

Благодаря @BillDimm за его вклад и настойчивость, указав, что XOR необходим.

Ответ 2

Один из способов генерации 200 хеш-значений - генерировать одно значение хэша с использованием хорошего алгоритма хеширования и генерировать 199 значений дешево с помощью XORing хорошего хэш-значения с 199 наборами случайных битов, имеющих такую ​​же длину, что и хорошее хеш-значение ( т.е. если ваш хороший хэш составляет 32 бита, постройте список из 199 32-битных псевдослучайных целых чисел и XOR каждый хороший хеш с каждым из 199 случайных чисел).

Do не просто вращают биты, чтобы генерировать хэш-значения дешево, если вы используете целые числа без знака (целые числа со знаком), которые часто будут выбирать один и тот же гальки снова и снова. Поворот битов на один - это то же самое, что и деление на 2 и копирование старого младшего бита в новое место с высоким битом. Примерно 50% хороших хэш-значений будут иметь 1 в младшем разряде, поэтому они будут иметь огромные значения хэша без молитвы быть минимальным хешем, когда этот низкий бит вращается в положение с высоким бит. Остальные 50% хороших хэш-значений будут просто равны их первоначальным значениям, деленным на 2 при сдвиге на один бит. Разделение на 2 не меняет, какое значение наименьшее. Итак, если у гальки, которая дала минимальный хэш с хорошей хэш-функцией, бывает 0 в младшем бите (вероятность 50% этого), она снова даст минимальное значение хэша при сдвиге на один бит. В качестве крайнего примера, если галька с наименьшим значением хеша из хорошей хеш-функции имеет хеш-значение 0, она всегда будет иметь минимальное значение хеша, независимо от того, сколько вы вращаете биты. Эта проблема не возникает с целыми целыми числами, потому что минимальные значения хеширования имеют экстремальные отрицательные значения, поэтому они имеют наименьший бит на 1, а затем нули (100...). Таким образом, только хеш-значения с 1 в младшем бит будут иметь шанс стать новым самым низким значением хэша после поворота на один бит. Если галька с минимальным значением хэша имеет 1 в младшем бите, после поворота на один бит это будет выглядеть как 1100..., поэтому почти наверняка будет выбита другой галькой, которая имеет значение, подобное 10... после поворота, и проблема с тем же галькой, собираемой дважды подряд с вероятностью 50%, избегается.

Ответ 3

То, что вы хотите, легко получить из универсального хэширования. Популярные учебники, такие как Corman и др. как очень читаемая информация в разделе 11.3.3 стр. 265-268. Короче говоря, вы можете генерировать семейство хеш-функций, используя следующее простое уравнение:

h(x,a,b) = ((ax+b) mod p) mod m

• x - это ключ, который вы хотите использовать для хеширования
• a - любое нечетное число, которое вы можете выбрать от 1 до p-1 включительно.
• b - любое число, которое вы можете выбрать от 0 до p-1 включительно.
• p - простое число, которое больше максимально возможного значения x
• m - максимальное возможное значение для хэш-кода + 1

Выбирая разные значения a и b, вы можете генерировать много хэш-кодов, которые не зависят друг от друга.

Оптимизированный вариант этой формулы может быть реализован следующим образом в C/С++/С#/Java:

(unsigned) (a*x+b) >> (w-M)

Здесь  - w - размер машинного слова (обычно 32)  - M - размер хэш-кода, который вы хотите в битах  - a - любое нечетное целое число, которое вписывается в машинное слово  - b любое целое число меньше 2 ^ (w-M)

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

Например, скажем, вам понадобится 200 16-битных хеш-кода для строки s, затем следующий код можно записать как реализацию:

public int[] GetHashCodes(string s, int count, int seed = 0)
{
    var hashCodes = new int[count];
    var machineWordSize = sizeof(int);
    var hashCodeSize = machineWordSize / 2; 
    var hashCodeSizeDiff = machineWordSize - hashCodeSize;
    var hstart = s.GetHashCode();
    var bmax = 1 << hashCodeSizeDiff;
    var rnd = new Random(seed);     

    for(var i=0; i < count; i++) 
    {
        hashCodes[i] = ((hstart * (i*2 + 1)) + rnd.Next(0, bmax)) >>  hashCodeSizeDiff;
    }
}

Примечания:

• Я использую хэш-код в размере половины размера машинного слова, который в большинстве случаев будет 16-битным. Это не идеально и имеет гораздо больше шансов на столкновение. Это можно использовать, обновив всю арифметику до 64-разрядной версии.
• Обычно вы хотите выбрать a и b как случайным образом в пределах указанных диапазонов.

Ответ 4

Просто используйте 1 хэш-функцию! (и сохраните самые маленькие значения 1/(f ε^2).)

Проверьте эту статью о состоянии практических и теоретических границ. У этого есть хороший график (ниже), объясняющий, почему вы, вероятно, хотите использовать только одну 2-независимую хеш-функцию и сохранить k наименьших значений.

При оценке размеров набора бумага показывает, что вы можете получить относительную ошибку приблизительно ε = 1/sqrt(fk) где f - подобие jaccard, а k - количество сохраненных значений. Поэтому, если вы хотите получить ошибку ε, вам нужно k=1/(fε^2) или если ваши наборы имеют сходство около 1/3 и вы хотите относительную ошибку 10%, вы должны оставить 300 наименьших значений.

Ответ 5

Кажется, что еще один способ получить N число хороших хэшированных значений будет состоять в том же хэше с N различными значениями соли.

На практике, если применить соль второй, кажется, что вы можете хэш-данные, затем "клонировать" внутреннее состояние вашего хэшира, добавить первую соль и получить свое первое значение. Вы бы reset этот клон к чистому клонированному состоянию, добавили вторую соль и получили второе значение. Промойте и повторите для всех N элементов.

Вероятно, не так дешево, как XOR против значений N, но кажется, что есть возможность для более качественных результатов при минимальных дополнительных затратах, особенно если хэширование данных намного больше, чем значение соли.