4

问题

假设您有 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)。有没有更好的数据结构或算法？由于没有单个查询整数，因此无法使用有效地在大集合中找到具有低汉明距离的二进制字符串的想法。

4

1 回答 1

6

最近的论文“ The Closest Pair Problem under the Hamming Metric ”只有涉及 n^2 因子的算法（除非 K 非常大）。即使只找到一对。因此，除非您对实例的结构做出进一步的假设，否则似乎很难改进这一点。例如，假设汉明距离不是很大，则可以在假设这些列完全匹配的情况下，对几列进行采样，将字符串散列到桶中，然后分别在每个桶中进行成对比较。对另一组随机列重复此操作，以最小化您错过某些对的概率。

于 2011-08-17T07:07:05.510 回答