Как работает Shingleprinting на практике?

Question

Я пытаюсь использовать shingleprinting для измерения подобия документа. Процесс включает в себя следующие этапы:

1. Создать 5-shingling из двух документов D1, D2
2. Hash каждая гальки с 64-битовой хэш
3. Pick случайную перестановку чисел от 0 до 2^64-1 и применить к гальке хэши
4. для каждого документа найти наименьшее из полученных значений
5. Если они совпадают считать это как положительный пример, если не считать его в качестве отрицательного примера
6. Repeat 3. 5 . немного раз
7. Использование positive_examples/total examples в качестве меры подобия

Шаг 3 включает в себя генерирование случайную перестановку очень длинной последовательности. Не может быть и речи об использовании Knuth-shuffle. Есть ли для этого сокращение? Заметим, что в конце нам нужен только один элемент полученной перестановки.

Answer 1

Предупреждение: я не уверен на 100%, но я прочитал некоторые из статей, и я считаю, что так оно и работает. Например, в «Небольшом, примерно, минимальном независимом семействе хэш-функций» Петра Индыка он пишет: «В реализации, интегрированной с Altavista, множество H выбрано как попарно независимое семейство хеш-функций».

На шаге 3 вам действительно не нужна случайная перестановка на [n] (целые числа от 1 до n). Оказывается, что на практике действует парически независимая хеш-функция. Итак, что вы делаете, выбираете парную независимую хэш-функцию h. А затем примените h к каждому из хешей. Вы можете взять min этих значений на этапе 4.

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

Литература: http://www.cs.princeton.edu/courses/archive/fall08/cos521/hash.pdf и http://people.csail.mit.edu/indyk/minwise99.ps