加快查找最佳二进制匹配数字的速度

Question

我有一个由256位值组成的数组。 数组很大（数百万条记录），但很少修改，可以放入内存。对于给定的256位数字，我想找到是否存在一个具有至少N位相等的记录。例如，10000和01111没有任何一位相等，1000和1001有3位相等。始终满足N>128，或者更准确地说是N>140。 我不需要找到特定号码，我只需要找出列表中是否存在这样的号码。

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

- smrt28

---

这个问题涉及到32位，但是答案可能仍然部分适用：https://dev59.com/C2w15IYBdhLWcg3wzO5_。 - harold

嗯，我认为公开我的问题背后的问题是公平的。我正在开发一个垃圾邮件过滤器，并发现了NILSIMCA哈希算法。http://en.wikipedia.org/wiki/Nilsimsa_Hash我想我会有许多NILSIMCA哈希，它们将是垃圾邮件样本。当电子邮件到达时，我需要遍历所有这些哈希，搜索该电子邮件是否为垃圾邮件。 - smrt28

@smrt28：你需要在线算法，还是提前给出所有查询？ - Niklas B.

我认为你不可能比线性搜索更好。然而，线性搜索可以进行很好的优化。我假设你可以在CPU上每个查询少于0.5秒的时间内完成，并且如果你有多个核心，显然可以线性加速。将工作委托给GPU并获得巨大的加速也是很直接的。你期望什么样的吞吐量？ - Niklas B.

我想我会根据收集到的垃圾邮件报告每天构建一次哈希数据库，然后我将不得不处理每秒钟许多电子邮件。因此，这将是一种在线算法。 - smrt28

Answer 1

我可能错了，但是看起来您可以将数据索引为按位 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在某种意义上压缩了数据，但如果您遇到内存问题，请尝试使用表格表示而不是对象和指针。

最后，您可以将其与布隆过滤器相结合，首先过滤绝对不在集合中的数字，然后使用上述树检查剩余部分。

- ffriend

---

有趣的想法，谢谢！ - smrt28

Answer 2

该问题的解决算法是O(n)。您唯一的选择是循环遍历数组，直到找到与目标匹配的数字。

现在，如何确定两个数字是否匹配？最有效的方法是使用位运算。例如，我编写了一段适用于64位长数字的代码：

int compare(long l1, long l2)
{
    //Use xor to get what bits are the same
    long xor = ~ (l1 ^ l2);

    //count the number of bits with value = 1
    int count = 0;
    while(xor != 0)
    {
        //check if the right bit is 1, using & operator beetween our number and 0000001
        if(xor & 1 > 0) count++;

        //shift right the bits
        xor = xor >> 1
    }

    return count;
}

这个比较可以根据你的256位数字的实现方式进行调整。一种优化方法是当达到count >= N时退出while循环。

你可以查看this question寻找更有效的计算值为1的位数的方法。

希望能帮到你！

- conca

---

你唯一的选择是循环遍历数组，直到找到与目标匹配的数字。你能证明吗？为什么没有更好的方法？ - Niklas B.

如果数组未排序且您没有任何有关项的其他信息，则必须循环遍历数组以查找匹配项。这与查找数组中的最大整数相同，在最坏的情况下，需要移动n次才能找到最大项，其中n是数组的长度。 - conca

但是你可以对数组进行排序并加快搜索速度，也可以预处理它以存储其他信息。OP正在寻找一种加速该过程的方法。 - Niklas B.

你说得对！如果你要执行多个查询，你可以进行一些预处理，这将至少需要O(n)的时间，但可以降低每个查询的复杂度。我会再次研究这个问题，它非常有趣，谢谢！ - conca