相关疑难解决方法(0)

问题:

给定一个大的(~1亿)无符号32位整数列表,无符号32位整数输入值和最大汉明距离,返回在输入值的指定汉明距离内的所有列表成员.

保持列表的实际数据结构是开放的,性能要求决定了内存中的解决方案,构建数据结构的成本是次要的,查询数据结构的低成本是至关重要的.

例:

For a maximum Hamming Distance of 1 (values typically will be quite small)

And input: 
00001000100000000000000001111101

The values:
01001000100000000000000001111101 
00001000100000000010000001111101 

should match because there is only 1 position in which the bits are different.

11001000100000000010000001111101

should not match because 3 bit positions are different.

到目前为止我的想法:

对于汉明距离为0的退化情况,只需使用排序列表并对特定输入值进行二分搜索.

如果汉明距离只有1,我可以翻转原始输入中的每一位并重复上述32次.

如何有效地(不扫描整个列表)发现汉明距离> 1的列表成员.

我有一组n(~1000000)字符串(DNA序列)存储在列表trans中.我必须找到列表中所有序列的最小汉明距离.我实施了一个天真的暴力算法,它运行了一天多,还没有给出解决方案.我的代码是

dmin=len(trans[0])
for i in xrange(len(trans)):
    for j in xrange(i+1,len(trans)):
            dist=hamdist(trans[i][:-1], trans[j][:-1])
            if dist < dmin:
                    dmin = dist

有没有更有效的方法来做到这一点？Hamdist是我写的一个函数,用于查找汉明距离.它是

def hamdist(str1, str2):
    diffs = 0
    if len(str1) != len(str2):
        return max(len(str1),len(str2))
    for ch1, ch2 in zip(str1, str2):
        if ch1 != ch2:
          diffs += 1
    return diffs