I may be wrong, but it looks like you can index your data as bitwise trie, which for your case is identical to binary tree in structure, but is interpreted differently. Here's illustration (source):
For the sake of simplicity, let's think about your 256-bit numbers as about vectors with 256 numbers (also binary, of course). Having a tree like above, you can find whether particular vector exists in your dataset in 256 steps or less by just walking down the tree and testing if subsequent branch (either "0" or "1") exists. Something like this (code's quite raw, but you should get an idea):
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
At each step we decide where to go left or right branch based on current value element of v
. But you also need to process up to K different elements. Ok, so why not to use error count and process both branches?
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
Running time of this algorithm heavily depends on your settings. In worst case (K = 256) it is still O(n) (you need to check each branch), but this time falls quickly as K decreases (with small K it is almost O(log n)). With K ~ 128 it's somewhere in the middle.
You may also want to rewrite function so that it checked good-day (no errors) scenarios first (e.g. if you expect number of errors be small on average).
Trie compressed data in a certain sense, but if you have issues with memory, try to use table representation instead of objects and pointers.
Finally, you can combine it with bloom filters to filter numbers that definitely are not in a set first, and then check the rest with above tree.