快速计算具有最小汉明距离的对

  • Z时代
  • 2024-01-10
  • 分类：问答

回答：

假设您有N个（〜100k-1m）整数/位串，每个K个位（例如256个）长。该算法应返回成对的汉明距离最低的k对。

回答：

N = 4
K = 8
i1 = 00010011
i2 = 01010101
i3 = 11000000
i4 = 11000011
HammingDistance(i1,i2) = 3
HammingDistance(i1,i3) = 5
HammingDistance(i1,i4) = 3
HammingDistance(i2,i3) = 4
HammingDistance(i2,i4) = 4
HammingDistance(i3,i4) = 2

对于k = 1，它应该返回配对列表{（i3，i4）}。对于k = 3，它应该返回{（i1，i2），（i1，i4），（i3，i4）}。等等。

回答：

天真的实现计算所有成对的距离，对对进行排序并返回距离最小的k：O（N ^

2）。有没有更好的数据结构或算法？似乎没有有效查询大型集合中具有低汉明距离的二进制字符串的想法，因为没有单个查询整数。

回答：

最近的论文“ 汉明度量标准下的最接近对问题

”仅包含涉及n ^

2因子的算法（除非K非常大）。即使只寻找一对。因此，除非您对实例的结构做进一步的假设，否则似乎很难对此进行改进。例如，如果您假设汉明距离不是很大，则可以对几列进行采样，并在假设这些列完全匹配的情况下根据这些字符串将字符串哈希到存储桶中，然后分别在每个存储桶中进行成对比较。对另一组随机列重复此操作，以最大程度地降低错过某些对的可能性。

以上是 快速计算具有最小汉明距离的对 的全部内容， 来源链接： utcz.com/qa/428353.html

回到顶部