найти ближайшее расстояние Хемминга

Question

У меня есть N <2 ^ n случайно сгенерированных n-битных чисел, хранящихся в файле, поиск которого дорогой.Учитывая число Y, я должен искать число в файле, которое не больше k хэммингового расст.от Y. Теперь это требует поиска C (n 1) + C (n 2) + C (n 3) ... + C (n, k) в худшем случае, что в моем случае неосуществимо.Я попытался сохранить распределение 1 и 0 в каждой позиции бита в памяти и расставил приоритеты в моих поисках.Итак, я сохранил вероятность того, что бит i будет 0/1: </p>

Pr(bi=0), Pr(bi=1) for all i from 0 to n-1.

Но это не сильно помогло, так как N слишком велико и имеет почти равное распределение 1/0 в каждой позиции бита.Есть ли способ, которым это можно сделать более эффективно.Пока что вы можете принять n = 32, N = 2 ^ 24.

Answer 1

Google дает решение этой проблемы для k = 3, n = 64, N = 2 ^ 34 (гораздо больший корпус, меньшее количество битов, большие отпечатки пальцев) в этой статье . Основная идея заключается в том, что для малых k n / k достаточно велико, и, следовательно, вы ожидаете, что у близких отпечатков пальцев должны быть относительно длинные общие префиксы, если вы сформировали несколько таблиц с переставленными порядками битов. Однако я не уверен, что это сработает, потому что ваш n / k немного меньше.

Answer 2

Вы можете использовать квантовые вычисления для ускорения процесса поиска и в то же время минимизировать необходимое количество шагов. Я думаю, что алгоритм поиска Гровера будет вам полезен, поскольку он обеспечивает квадратичную скорость до задачи поиска .....

Answer 3

Если под «поиском» вы имеете в виду поиск всего файла по указанному номеру, а затем повторение «поиска» для каждого возможного совпадения, то должно быть быстрее просто один раз прочитать весь файл, проверяя каждую записьрасстояние Хемминга до указанного числа, как вы идете.Таким образом, вы читаете файл только один раз вместо C (n 1) + C (n 2) + C (n 3) ... + C (n, k) раз.

Answer 4

Если ваше приложение может позволить себе выполнить некоторую расширенную предварительную обработку, вы можете, поскольку вы генерируете n-битные числа, вычислить все остальные числа, которые не более чем на k от этого числа, и сохранить их в справочной таблице.Это было бы что-то вроде карты>.riri утверждает, что вы можете разместить его в памяти, поэтому хеш-таблицы могут хорошо работать, но в противном случае вам, вероятно, понадобится дерево B + для карты.Конечно, это дорого, как вы упоминали ранее, но если вы можете сделать это заранее, у вас будет быстрый поиск позже, либо O (1), либо O (log (N) + log (2 ^ k)).

Answer 5

Возможно, вы могли бы сохранить его в виде графика со ссылками на следующие ближайшие номера в наборе, используя расстояние Хэмминга, тогда все, что вам нужно сделать, - это перейти по одной из ссылок на другой номер, чтобы найти следующий ближайший. Затем используйте индекс, чтобы отслеживать, где находятся числа по смещению файла, чтобы вам не приходилось искать на графике Y, когда вам нужно найти соседних с ним соседей.

Вы также говорите, что у вас есть 2 ^ 24 числа, которые согласно wolfram alpha (http://www.wolframalpha.com/input/?i=2^24+*+32+bits) всего 64 МБ. Не могли бы вы просто поместить все это в оперативную память, чтобы ускорить доступ? Возможно, это произойдет автоматически с кэшированием на вашей машине.