У меня есть несколько миллионов 32-битных значений. Для каждого значения я хочу найти все другие значения в пределах расстояния Хэмминга, равного 5. В наивном подходе это требует сравнений, которых я хочу избежать.
Я понял, что если я просто обработал эти 32-битные значения как целые числа и отсортировал список один раз, то значения, которые отличались только младшими значащими битами, оказались очень близко друг к другу. Это позволяет мне иметь более короткое «окно» или диапазон чисел, в которых я могу выполнять фактические попарные сравнения для точного расстояния Хэмминга. Однако когда значения 2 изменяются только в битах более высокого порядка, они оказываются за пределами этого «окна» и появляются на противоположных концах отсортированного списка. Например
11010010101001110001111001010110
01010010101001110001111001010110
было бы очень далеко друг от друга, даже если их расстояние Хэмминга равно 1. Поскольку расстояние Хемминга между двумя значениями сохраняется при повороте обоих, я подумал, что, выполнив 32 поворота влево и затем сортируя список каждый раз, вполне вероятно, что 2 значения окажется достаточно близко в отсортированном списке хотя бы в одном из них.
Хотя этот подход дает мне хорошие результаты, я изо всех сил пытаюсь официально установить правильность этого подхода.
Учитывая, что я ищу совпадающие значения с расстоянием Хэмминга или меньше, мне действительно нужно делать все 32-битные вращения? Например, если k = 1, а размер моего окна равен 1000, мне нужно делать это при максимальных 24-битных поворотах, потому что даже если бит сбоя появился в любом из 8 младших битов, результирующие числа не будут отличаться более чем на 1000.
A[i].close
Ответы:
Как уже говорилось, ваш подход проблематичен, потому что если 2 битовых карты имеют равномерно распределенные различия, то при любом повороте будут различия в некоторых старших битах.
Дополнительная информация:
источник
Ответ Минара превосходен и, вероятно, является правильным подходом для решения этой конкретной проблемы. Однако я упомяну еще один возможный подход:
Вы можете использовать хеш-функцию, чувствительную к локальности (LSH). Чувствительная к локальности хеш-функция разработана так, что если близки на расстоянии Хэмминга, то . Если у вас есть такой хэш , вы можете сохранить все свои значения в хеш-таблице (используя хэш-функцию и открытое хеширование), и тогда вы очень быстро сможете найти все пары значений, которые находятся близко на расстоянии Хэмминга. , Существуют различные методы построения LSH; Вы можете посмотреть ссылки на эту тему, чтобы найти несколько кандидатов.x , y H ( x ) = H ( y ) H HH x,y H(x)=H(y) H H
Тем не менее, для вашей конкретной проблемы (с конкретными параметрами, которые вы упомянули), я ожидаю, что два алгоритма Минара окажутся лучше на практике, чем любая схема на основе LSH. Я упоминаю об этом только в случае, если другие читатели придут сюда на этот вопрос с похожей проблемой, но с другими параметрами, где LSH может иметь больше смысла.
источник