Ответ 1
Я могу ошибаться, но похоже, что вы можете индексировать свои данные как побитовые trie, которые для вашего случая идентичны бинарное дерево в структуре, но интерпретируется по-разному. Здесь иллюстрация (источник):
Для простоты подумайте о своих 256-битных числах как о векторах с 256 номерами (также двоичными, конечно). Имея дерево, подобное выше, вы можете найти, существует ли конкретный вектор в вашем наборе данных в 256 шагов или меньше, просто пройдя по дереву и тестируя, если существует следующая ветвь (либо "0", либо "1" ). Что-то вроде этого (код довольно сырой, но вы должны получить представление):
def exists(node, v, i):
"""Checks if subvector of v starting from index i exists in
sub-tree defined by node
"""
if i == len(v):
return True
elif v[i] == 0 and node.left:
return exists(node.left, v, i + 1)
elif v[i] == 1 and node.right:
return exists(node.right, v, i + 1)
else:
return False
На каждом шаге мы решаем, куда идти влево или вправо, исходя из текущего элемента значения v. Но вам также нужно обработать до K различных элементов. Итак, почему бы не использовать количество ошибок и обработать обе ветки?
def exists(node, v, i, err_left=K):
"""Checks if subvector of v starting from index i exists in
sub-tree defined by node with up to err_left errors.
"""
if i == len(v):
return True
elif v[i] == 0:
if node.left:
return exists(node.left, v, i + 1, err_count)
elif node.right:
return exists(node.left, v, i + 1, err_left - 1) # proceed, but decrease
# errors left
else:
return False
elif v[i] == 1:
if node.right:
return exists(node.right, v, i + 1, err_count)
elif node.left:
return exists(node.right, v, i + 1, err_left - 1) # proceed, but decrease
# errors left
else:
return False
else:
return False
Время работы этого алгоритма сильно зависит от ваших настроек. В худшем случае (K = 256) все равно O (n) (вам нужно проверить каждую ветвь), но это время быстро падает с уменьшением K (при малом K это почти O (log n)). С K ~ 128 это где-то посередине.
Вы также можете переписать функцию так, чтобы она сначала проверяла сценарии хорошего дня (без ошибок) (например, если вы ожидаете, что число ошибок будет небольшим в среднем).
Trie сжатые данные в определенном смысле, но если у вас есть проблемы с памятью, попробуйте использовать представление таблицы вместо объектов и указателей.
Наконец, вы можете объединить его с bloom filters для фильтрации чисел, которые определенно не находятся в наборе в первую очередь, а затем проверьте остальные с помощью выше дерево.