我有一个 256 位值的数组。该数组很大(数百万条记录),但它很少被修改并且适合内存。对于给定的 256 位数字,我想查找是否存在至少 N 位相等的记录。例如,10000 和 01111 有 0 位相等,1000 和 1001 有 3 位相等。总是 N > 128,或者更确切地说 N > 140。我不需要找到一个特定的数字,我只需要找到这个数字是否存在于列表中。
是否有某种数据结构或某种索引可以以某种方式加快搜索速度?
最佳答案
我可能错了,但看起来您可以按位索引您的数据 trie ,对于您的情况,它在结构上与二叉树相同,但解释不同。这是插图 ( source ):
为简单起见,让我们将 256 位数字视为具有 256 个数字(当然也是二进制)的向量。有了像上面这样的树,您只需沿着树走下去并测试后续分支(“0”或“1”)是否存在,就可以在 256 步或更短的时间内找到数据集中是否存在特定向量。像这样的东西(代码很原始,但你应该有一个想法):
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结合起来首先过滤绝对不在集合中的数字,然后用上面的树检查其余的。
关于algorithm - 加快搜索最佳二进制匹配数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21340484/