相关疑难解决方法(0)

我有一个256位值的数组.该数组是巨大的(数百万条记录),但它很少被修改,它适合内存.对于给定的256位数,我想查找是否存在至少N位相等的记录.例如,10000和01111的0位相等,1000和1001的3位相等.总是N> 128,或者更确切地说N> 140.我不需要找到特定的数字,我只需要查找列表中是否存在这样的数字.

是否有一种数据结构或某种索引可以某种方式加速搜索？

我有一组位串：（{'0011', '1100', '1110'}一组中的所有位串都具有相同的长度）。

我想快速找到与集合最大相似度最小的相同长度的位串。最大相似度可以这样计算：

def max_similarity(bitstring, set):
    max = 0
    for item in set:
        temp = 0
        for i in range(len(bitstring)):
            if bitstring[i] == item[i]:
                temp += 1
        if temp > max:
            max = temp
    return max

我知道我可以遍历该长度的所有可能的位串，计算每个位的最大相似度，最后保留这些迭代中的最小者。但这解决了O（2 ^ n）中的问题。我想知道是否有人看到任何更快的选择。

我一直在玩Pythons XOR：

def int2bin(integer, digits):
    if integer >= 0:
        return bin(integer)[2:].zfill(digits)
    else:
        return bin(2**digits + integer)[2:]


def XOR(bitset):  
    intset = [int('{}'.format(bitstring), 2) for bitstring in bitset]

    digits = len(bitset.pop())

    if len(intset) == 1:
        return int2bin(~intset.pop(), digits)        
    else:
        curr …

给定位串数组(所有相同长度)和查询字符串Q找到top-k与Q最相似的字符串,其中字符串A和B之间的相似性被定义为A和B中的数字1,(操作并按位应用) .

我认为这个问题应该有一个经典的结果.

k很小,数百,而数亿的矢量数和矢量的长度是512或1024

我有一个过程,类似于生成感知哈希的tineye,这些是32位整数.

我打算将来存储在一个sql数据库(也许是一个nosql db)中

但是,我很难理解如何根据哈希的相似性检索记录.

有任何想法吗？

问题

假设你有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中找到大集合中具有低汉明距离的二进制字符串的想法.