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

Question

问题:

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

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

例:

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. 它服从三角不等式,d(x,z)≤d(x,y)+ d(y,z)

问题:我们为什么关心？

答:因为这意味着汉明距离是度量的度量空间.存在用于索引度量空间的算法.

• 度量树(维基百科)
• BK树(维基百科)
• M树(维基百科)
• VP树(维基百科)
• 封面树(维基百科)

您还可以查找"空间索引"的算法,并且知道您的空间不是欧几里德,但它是一个度量空间.关于该主题的许多书籍使用诸如汉明距离之类的度量来覆盖字符串索引.

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

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伪随机整数
• 测试次数:1000距离1..5,100距离6..10和线性
• 结果:查询命中的平均数量(非常近似)
• 速度:每秒查询数
• 覆盖率:每个查询检查的数据库的平均百分比

                -- BK Tree --   -- VP Tree --   -- Linear --
Dist    Results Speed   Cov     Speed   Cov     Speed   Cov
1          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%

在你的评论中,你提到:

我认为可以通过生成一堆具有不同根节点的BK树并将它们展开来改进BK树.

我认为这正是VP树比BK树(稍微)表现更好的原因."更深"而不是"浅",它与更多的点进行比较,而不是使用更细粒度的比较来减少点数.我怀疑在高维空间中差异更为极端.

最后一个提示:树中的叶节点应该是平面的整数数组,用于线性扫描.对于小型设备(可能是1000点或更少),这将更快,更高效.

Answer 2

我写了一个解决方案,我在2 位³²位的位集中表示输入数字,所以我可以在O(1)中检查输入中是否有某个数字.然后,对于查询的数字和最大距离,我递归地生成该距离内的所有数字,并根据该位集检查它们.

例如,对于最大距离5,这是242825个数字(总和_{d = 0到5} {32选择d}).相比之下,Dietrich Epp的VP树解决方案例如在1亿个数字中占22%,即通过2200万个数字.

我使用Dietrich的代码/解决方案作为添加我的解决方案并与之比较的基础.以下是每秒查询的速度,最大距离为10:

Dist     BK Tree     VP Tree         Bitset   Linear

   1   10,133.83   15,773.69   1,905,202.76   4.73
   2      677.78    1,006.95     218,624.08   4.70
   3      113.14      173.15      27,022.32   4.76
   4       34.06       54.13       4,239.28   4.75
   5       15.21       23.81         932.18   4.79
   6        8.96       13.23         236.09   4.78
   7        6.52        8.37          69.18   4.77
   8        5.11        6.15          23.76   4.68
   9        4.39        4.83           9.01   4.47
  10        3.69        3.94           2.82   4.13

Prepare     4.1s       21.0s          1.52s  0.13s
times (for building the data structure before the queries)

对于小距离,bitset解决方案是迄今为止最快的解决方案.问题作者埃里克在下面评论说,最大的兴趣距离可能是4-5.当然,我的bitset解决方案对于较大的距离变得更慢,甚至比线性搜索更慢(对于距离32,它将经过2 ^32个数字).但对于距离9,它仍然很容易导致.

我还修改了迪特里希的测试.以上每个结果都是为了让算法在大约15秒内解决至少三个查询和尽可能多的查询(我会查询1,2,4,8,16等查询,直到至少10秒钟为止总共通过了).这是相当稳定的,我甚至得到类似的数字只有1秒.

我的CPU是i7-6700.我的代码(基于Dietrich的)就在这里(至少暂时忽略那里的文档,不知道该怎么做,但tree.c包含所有代码和我的test.bat节目如何编译和运行(我使用了Dietrich的标志Makefile)) .我的解决方案的捷径.

一个警告:我的查询结果只包含一次数字,因此如果输入列表包含重复的数字,则可能需要也可能不需要.在提问作者Eric的案例中,没有重复(见下面的评论).在任何情况下,这个解决方案可能对于那些在输入中没有重复或者不想要或者在查询结果中需要重复的人来说是好的(我认为纯查询结果可能只是达到目的的一种手段然后一些其他代码将数字转换为其他代码,例如将数字映射到散列为该数字的文件列表.