问题：我们对汉明距离 d(x,y) 了解多少？
Answer:
- 它是非负数：d(x,y) ≥ 0
- 对于相同的输入，它仅为零： d(x,y) = 0 ⇔ x = y
- 它是对称的： d(x,y) = d(y,x)
- 它遵循三角不等式, d(x,z) ≤ d(x,y) + d(y,z)
问题：我们为什么关心？
Answer:因为这意味着汉明距离是metric for a 度量空间。有用于索引度量空间的算法。
-
度量树（维基百科）
-
BK-tree（维基百科）
-
M-tree（维基百科）
-
VP-tree（维基百科）
-
覆盖树（维基百科）
您还可以查找一般的“空间索引”算法，并了解您的空间不是欧几里得空间，而是它is一个度量空间。关于这个主题的许多书籍都介绍了使用汉明距离等度量标准的字符串索引。
脚注：如果您要比较固定宽度字符串的汉明距离，则可以通过使用汇编或处理器内在函数来获得显着的性能改进。例如，对于海湾合作委员会（manual） 你做这个：
static inline int distance(unsigned x, unsigned y)
{
return __builtin_popcount(x^y);
}
如果您随后通知 GCC 您正在使用 SSE4a 为计算机进行编译，那么我相信这应该减少到只有几个操作码。
Edit:根据许多消息来源，这有时/通常比通常的掩码/移位/添加代码慢。基准测试表明，在我的系统上，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 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 点或更少），这会更快且内存效率更高。
