algorithm - 在大型集合中有效地找到具有低汉明距离的二进制字符串

Question

问题:

给定一个大型(约 1 亿)无符号 32 位整数列表、一个无符号 32 位整数输入值和最大 Hamming Distance , 返回输入值指定汉明距离内的所有列表成员。

保存列表的实际数据结构是开放的，性能要求决定了内存中的解决方案，构建数据结构的成本是次要的，查询数据结构的低成本是关键。

示例:

For a maximum Hamming Distance of 1 (values typically will be quite small)

And input: 
00001000100000000000000001111101

The values:
01001000100000000000000001111101 
00001000100000000010000001111101 

should match because there is only 1 position in which the bits are different.

11001000100000000010000001111101

should not match because 3 bit positions are different.

到目前为止我的想法:

对于汉明距离为 0 的退化情况，只需使用排序列表并对特定输入值进行二进制搜索。

如果汉明距离永远为 1，我可以翻转原始输入中的每一位并重复上述 32 次。

我如何有效地(无需扫描整个列表)发现汉明距离 > 1 的列表成员。

Answer 1

问题:我们对汉明距离 d(x,y) 了解多少？

答案:

1. 它是非负的:d(x,y) ≥ 0
2. 对于相同的输入只有零:d(x,y) = 0 ⇔ x = y
3. 它是对称的:d(x,y) = d(y,x)
4. 它遵守 triangle inequality , d(x,z) ≤ d(x,y) + d(y,z)

问题:我们为什么关心？

答案:因为这意味着汉明距离是度量的度量空间。有索引度量空间的算法。

• Metric tree (维基百科)
• BK-tree (维基百科)
• M-tree (维基百科)
• VP-tree (维基百科)
• Cover tree (维基百科)

您还可以查找一般的“空间索引”算法，了解您的空间不是欧几里德空间，而是度量空间。许多关于此主题的书籍都介绍了使用汉明距离等度量的字符串索引。

脚注:如果您正在比较固定宽度字符串的汉明距离，您可能能够通过使用汇编或处理器内在函数来显着提高性能。例如，使用 GCC ( manual) 你可以这样做:

static inline int distance(unsigned x, unsigned y)
{
    return __builtin_popcount(x^y);
}

如果您随后通知 GCC 您正在为一台使用 SSE4a 的计算机进行编译，那么我认为应该减少到只有几个操作码。

编辑:根据许多消息来源，这有时/通常比通常的掩码/移位/添加代码慢。基准测试表明，在我的系统上，C 版本的性能优于 GCC 的 __builtin_popcount 大约 160%。

附录:我自己对这个问题很好奇，所以我分析了三种实现方式:线性搜索、BK 树和 VP 树。请注意 VP 和 BK 树非常相似。 BK 树中一个节点的子节点是树的“外壳”，其中包含与树的中心有固定距离的点。 VP 树中的一个节点有两个子节点，一个包含以节点中心为中心的球体内的所有点，另一个子节点包含外部的所有点。因此，您可以将 VP 节点视为具有两个非常厚的“壳”而不是许多更细的“壳”的 BK 节点。

结果是在我的 3.2 GHz PC 上捕获的，算法不会尝试利用多核(这应该很容易)。我选择了 100M 伪随机整数的数据库大小。结果是距离 1..5 的 1000 个查询的平均值，以及 6..10 和线性搜索的 100 个查询的平均值。

• 数据库:100M 伪随机整数
• 测试次数:距离 1..5 为 1000，距离 6..10 和线性为 100
• 结果:平均查询命中数(非常近似)
• 速度:每秒查询数
• 覆盖率:每次查询检查的数据库的平均百分比

                -- BK Tree --   -- VP Tree --   -- Linear --Dist    Results Speed   Cov     Speed   Cov     Speed   Cov1          0.90 3800     0.048% 4200     0.048%2         11     300     0.68%   330     0.65%3        130      56     3.8%     63     3.4%4        970      18    12%       22    10%5       5700       8.5  26%       10    22%6       2.6e4      5.2  42%        6.0  37%7       1.1e5      3.7  60%        4.1  54%8       3.5e5      3.0  74%        3.2  70%9       1.0e6      2.6  85%        2.7  82%10      2.5e6      2.3  91%        2.4  90%any                                             2.2     100%

在您的评论中，您提到:

I think BK-trees could be improved by generating a bunch of BK-trees with different root nodes, and spreading them out.

我认为这正是 VP 树表现(略)优于 BK 树的原因。 “更深”而不是“更浅”，它与更多的点进行比较，而不是对更少的点进行更细粒度的比较。我怀疑在高维空间中差异更为极端。

最后一个提示:树中的叶节点应该只是线性扫描的平面整数数组。对于小集合(可能 1000 个点或更少)，这会更快并且内存效率更高。