在少于O（n ^ 2m）的时间内查找最小汉明距离

Question

如果你有长度为m的n个二进制字符串，是否有更快的方法来确定任意一对之间的最小汉明距离，而不是比较所有O(n^2)对并计算它们的汉明距离？除了其他事情和下面的评论，汉明距离是一个适当的距离函数，因此满足三角不等式，这让我觉得应该有更快的解决方案。那么，是否可以在少于O(n^2m)的时间内完成呢？

- Simd

---

有很多关于编程的论文和其他资源可以在互联网上找到。试试谷歌搜索！你已经尝试过什么了吗？ - MrSmith42

@MrSmith42 我已经尝试过在网上搜索“最小汉明距离”，但是到目前为止还没有找到。 - Simd

这是一个距离，因此它验证 d(a,c) ≤ d(a,b)+d(b,c)，这可以确保不必测试每一对。 - Jean-Baptiste Yunès

这也许会对你有所帮助（你需要找到一个好的排序）：https://dev59.com/MJnga4cB1Zd3GeqPdcQP - Jean-Baptiste Yunès

@MrSmith42：在二进制字符串中，有n个字符串，它们之间的汉明距离为(n-1)*n/2，因为汉明距离是在两个字符串之间定义的。在这样的汉明空间中进行高效的最近邻搜索并不容易。至少到目前为止，我的谷歌搜索还没有收到有效的结果。 - Axel Kemper

你可以构建一个kd-tree，并且（对于适度的m值）使用查找表来确定两个字符串之间的距离。这将导致复杂度为O(n log n)。 - Axel Kemper

Answer 1

考虑使用局部敏感哈希，这是一种通用技术，可应用于某些距离度量，包括汉明距离。摘自维基百科：

LSH将输入项哈希，以便相似的项高概率地映射到同一个“桶”中（桶的数量远小于可能的输入项的宇宙）。

简而言之，您可以使用LSH获取存储桶，在每个存储桶内暴力计算汉明距离，并输出找到的最小距离。为了更高概率地获得正确答案，您可以调整LSH算法的参数和/或多次运行LSH（以获得不同的项目分配到存储桶中）。我相信您可以通过运行时间指数级减少的失败率无限接近正确（最优）答案。（如果您的汉明距离都非常接近，则可能需要在LSH参数上进行二进制搜索，但仍会避免计算n^2个汉明距离。）

这个算法和分析非常复杂，所以我现在不认为我能写出完整的摘要（大约需要2-3小时的讲座材料）。我建议查看讲座笔记/幻灯片这里, 这里和这里；它们都涵盖了LSH（不同程度的细节）并提到了汉明距离。

- k_ssb

Answer 2

如果不进行 O(n^2m) 的全面搜索，就无法确定真正的最小值。所有更快的变体都只会产生一个“可能是最佳最小值”的结果。

证明如下：

1. Assume there would be a faster solution.
2. Then for one or more combinations the hamming distance is not computed.
3. Omitting a combination means, that there is a criteria to decide
   the combination can't be better than the current best minimum.
4. There is no know criteria.

三角不等式只能帮助缩短真正最大值的计算：

1. 计算距离Di0，排序并选择一个起始最大值。
2. 现在省略所有满足Di0 + D0j <= 当前最大值的Dij。

- bebbo

---

我也有同样的疑问，似乎很容易找到不必比较所有字符串的例子。如果“第一个”和“第二个”字符串的汉明距离==1，则只需要验证是否存在重复字符串，这应该是O（n*m）。我不知道是否可以推广到其他情况。 - Hans Olsson

如果最后一次比较的汉明距离等于1怎么办？一个幸运的例子并不是普遍规律。根据进一步的限制，可能存在更快的解决方案。但是如果没有任何限制，就无法推断出Dij的下限。这只是一个上限，只有帮助找到最大值。 - bebbo

不，事情并不是这样的。你声称不存在“这样的标准”。你有责任证明这些标准不存在。 - k_ssb

我不明白为什么对于那个已经用“有点”的方式进行了限定的内容，还要过于追求细节，从而认为这个答案是错误的。如果有人有一个实际的 O(n^2m) 答案，而不是一个“可能最佳”的答案，请发表出来。 - c z

@pkpnd 已知如果您有减法或加法+负数，就可以进行除法计算。但是只有加法... - bebbo