问题
假设您有N个整数/位串,每个整数/位串都有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)}的pairlist。对于k=3,它应该返回{(i1,i2),(i1,i4),(i3,i4)}等。以此类推。
算法
朴素实现计算所有成对距离,对成对进行排序并返回具有最低距离的k:O(N ^ 2)。是否有更好的数据结构或算法?看起来无法使用在大型集合中高效地查找具有低汉明距离的二进制字符串的思想,因为没有单个查询整数。