加快搜索最佳二进制匹配数

Question

我有一个256位值的数组.该数组是巨大的(数百万条记录),但它很少被修改,它适合内存.对于给定的256位数,我想查找是否存在至少N位相等的记录.例如,10000和01111的0位相等,1000和1001的3位相等.总是N> 128,或者更确切地说N> 140.我不需要找到特定的数字,我只需要查找列表中是否存在这样的数字.

是否有一种数据结构或某种索引可以某种方式加速搜索？

Answer 1

我可能是错的，但看起来您可以将数据索引为按位trie，对于您的情况，它在结构上与二叉树相同，但解释不同。这是插图（来源）：

为了简单起见，让我们将 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 处于中间位置。

您可能还想重写函数，以便它首先检查良好（无错误）场景（例如，如果您预计错误数量平均较小）。

在某种意义上尝试压缩数据，但如果您遇到内存问题，请尝试使用表表示而不是对象和指针。

最后，你可以将它与布隆过滤器结合起来，先过滤掉绝对不在集合中的数字，然后用上面的树检查其余的数字。