快速计算汉明距离最小的一对元素

Question

问题

假设您有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）。是否有更好的数据结构或算法？看起来无法使用在大型集合中高效地查找具有低汉明距离的二进制字符串的思想，因为没有单个查询整数。

- rfalke

---

你知道最接近的一对会有多接近吗？ - Rob Neuhaus

通常有一对距离为零或一位的比特。 - rfalke

你能发布一个代表性的数据集吗？如果最接近的一对之间的距离大于2（或5，或...），你是否可以接受没有匹配结果？ - Rob Neuhaus

Answer 1

最近的论文 "汉明度量下的最近对问题" 只有涉及 n^2 的算法（除非 K 非常大），即使只是查找单个对。所以看起来如果不对实例的结构作进一步假设，很难改进这一点。例如，如果您假设汉明距离不是很大，您可以抽样几列，在这些列完全匹配的假设下将字符串哈希到桶中，然后在每个桶中分别进行成对比较。为了最小化错过某些对的概率，请重复此过程另一个随机列集。

- Falk Hüffner