Использование битовой выборки для построения minhash
Я использовал эту прекрасную статью о хешировании, чувствительном к локальности, чтобы построить свою собственную схему хеширования, чувствительной к локальности, которая разветвляется в знании предметной области - я имею в виду мое знание только того, что хешируется, чтобы, надеюсь, обеспечить более надежные локальные совпадения сходства.
Одна из идей, обсуждаемых в этой статье, которая действительно привлекает меня, - использование битовой выборки для ускорения и упрощения процесса мини-хэшей. Цитировать из этой статьи
Чтобы уменьшить временную сложность сравнения minHashes друг с другом, мы можем добиться большего успеха с помощью метода, известного как битовая выборка. Основная идея заключается в том, что нам не нужно знать точное значение каждого хеша, а только то, что хеш-коды равны в своих соответствующих позициях в каждом хеш-векторе. С этим пониманием давайте рассмотрим только младший значащий бит (LSB) каждого хеш-значения. Еще псевдокод:
для которого автор предоставляет относительно простой псевдокод
def bitSampling(hashes):
N = 100
bits = 0
for each i = 1 to N:
hash = hashes[i]
bits = (bits << 1) | (hash & 1)
return bits
Ниже автор продолжает замечание
Конечно, два разных хэша будут иметь один и тот же младший бит 50% времени; чтобы увеличить нашу эффективность, мы бы изначально выбрали большой N
Я не вижу, как использовать большее значение N сделает результат более надежным - все-таки можно ожидать, что половина генерируемых хэшей будет нечетными числами. Разве не имеет смысла выбирать несколько большее количество бит?
Например, почему бы не сэмплировать биты 0, 3 и 16? т.е. hash & 41,
Возможно, существует лучший форум по Stack Exchange для этого вопроса, но я не смог это установить.