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

Question

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

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

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

Answer 1

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

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

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

Ссылки: http://www.cs.princeton.edu/courses/archive/fall08/cos521/hash.pdf и http://people.csail.mit.edu/indyk/minwise99.ps