问如何高效地找到大集合中Hamming距离较低的二进制字符串？

EN

问题：我们对Hamming距离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）

问题：为什么我们关心？

答：因为这意味着Hamming距离是度量的度量空间。有度量空间索引的算法。

• 度量树（Wikipedia）
• BK树（维基百科）
• M-tree（维基百科）
• VP-tree（维基百科）
• 封面树（维基百科）

一般来说，你也可以查找“空间索引”算法，知道你的空间不是欧几里得，但它是一个度量空间。

脚注：如果你正在比较固定宽度字符串的汉明距离，则可以使用装配体或处理器内在函数获得显着的性能改进。例如，使用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伪随机整数
• 测试次数：距离1..5为1000，距离为6..10为100，线性为100
• 结果：查询命中的平均数量（非常近似）
• 速度：每秒查询次数
• 覆盖率：每个查询检查的数据库的平均百分比

                -  BK树 -   -  VP树 -   - 线性 - 
Dist结果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％

我认为这正是VP树比BK树更好（稍好）的原因。“更深”而不是“更浅”，它比较多点而不是使用更细的比较来反对更少的点。我怀疑这种差异在高维空间中更为极端。

最后的提示：树中的叶节点应该是用于线性扫描的平整整数数组。对于小组（可能小于或等于1000分），这将更快，更高效地存储内存。

我写了一个解决方案，我用2 32位的位集表示输入数字，所以我可以检查O（1）中是否有输入数字。然后，对于查询的数字和最大距离，我递归地生成该距离内的所有数字，并检查它们是否与位集对照。

例如，对于最大距离5，这是242825个数字（总和d = 0到5 {32选择d}）。为了比较，Dietrich Epp的VP-tree解决方案例如通过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)

对于小距离来说，比特解决方案是迄今为止最快的解决方案。

我的CPU是i7-6700。我的代码在这里（至少现在忽略文档，不知道该怎么做，但tree.c包含所有的代码和我的test.bat演示如何编译和运行（我使用迪特里希的标志Makefile）） 。