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

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

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

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


random performance text-mining permutation information-retrieval
person mdm    schedule 09.07.2010    source источник

Ответы (1)


arrow_upward
3
arrow_downward

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

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

person msft-er    schedule 09.05.2011