问题： 我们对汉明距离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-tree（维基百科）
• 副总裁（维基百科）
• 封面树（维基百科）

您还可以查找算法一般“空间索引”，用知识武装起来，你的空间不是欧几里得，但它 是
一个度量空间。关于该主题的许多书籍都使用诸如汉明距离之类的度量标准来覆盖字符串索引。

脚注：
如果您比较固定宽度字符串的汉明距离，则可以通过使用汇编或处理器内在函数来获得显着的性能改进。例如，使用GCC（手册），您可以执行以下操作：

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

如果您随后告知GCC您正在使用SSE4a编译计算机，那么我认为应该减少到几个操作码。

编辑：
根据许多消息来源，这有时/通常比通常的遮罩/移位/添加代码慢。基准测试显示，在我的系统上，C版本的性能优于GCC的__builtin_popcount160％。

附录：
我自己对此问题很好奇，因此我介绍了三种实现：线性搜索，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树--VP树--线性-
  

  距离结果速度速度速度速度速度速度
  1 0.90 3800 0.048％4200 0.048％
  2 11 300 0.68％330 0.65％
  3130 56 3.8％63 3.4％
  4970 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％
  任何2.2 100％

在您的评论中，您提到：

我认为可以通过生成一堆具有不同根节点的BK树并将其散布来改善BK树。

我认为这正是VP树比BK树（略）更好的原因。作为“更深”而不是“更浅”，它与更多点进行比较，而不是针对更少点进行更细粒度的比较。我怀疑在高维空间中差异更大。

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