0

我有一个包含 n 个字符串（n > 100 万）的数据库，每个字符串有 100 个字符，每个字符是a,或.bcd

我想为每个字符串找到最接近的字符串，最接近的定义为具有最小的汉明距离。我想为每个字符串找到 k 最近的字符串（k < 5）。

例子

N = 5
i1 = aacbdbbb
i2 = abcbdbbb
i3 = bbcadabd
i4 = bbcadabb

HammingDistance(i1,i2) = 1
HammingDistance(i1,i3) = 5
HammingDistance(i1,i4) = 4
HammingDistance(i2,i3) = 4
HammingDistance(i2,i4) = 3
HammingDistance(i3,i4) = 1

对于 k=1，它应该返回 {(i1,i2),(i2,i1),(i3,i4),(i4,i3)}。对于 k=2，它应该返回 { (i1,{i2,i4}),(i2,{i1,i4}),(i3,{i4,i2}),(i4,{i3,i2})}。等等。对于每个字符串都应该找到k-最近的字符串。

朴素的解决方案具有 O(n^2) 时间复杂度。我想找到更复杂的解决方案。我找到了一些其他的解决方案，但没有一个比天真的更好。

如何以最佳方式将此类字符串分配到集群中？一个字符串可以在两个或多个簇中。解决方案可能是确定性的或概率性的。

4

0 回答 0