álculo rápido de pares com a menor distância possív
Problem
Suponha que você tenha N (~ 100k-1m) números inteiros / cadeias de bits com cada K (por exemplo, 256) bits. O algoritmo deve retornar os pares k com a menor distância Hamming em pare
ExemplN = 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
Para k = 1, ele deve retornar o pairlist {(i3, i4)}. Para k = 3, ele deve retornar {(i1, i2), (i1, i4), (i3, i4)}. E assim por diante
AlgoritmA implementação ingênua calcula todas as distâncias aos pares, classifica os pares e retorna k com a menor distância: O (N ^ 2). Existem estruturas de dados ou algoritmos melhores? Parece que as idéias de Encontre cordas binárias com baixa distância de Hamming em conjunto grande não pode ser usado, pois não há um inteiro inteiro de consult