相关疑难解决方法(0)

问题

假设你有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,它应该返回pairlist {(i3,i4)}.对于k = 3,它应该返回{(i1,i2),(i1,i4),(i3,i4)}.等等.

算法

天真的实现计算所有成对距离,对对进行排序并返回具有最小距离的k:O(N ^ 2).有没有更好的数据结构或算法？由于没有单个查询整数,因此无法使用Efficiently中找到大集合中具有低汉明距离的二进制字符串的想法.