Cálculo rápido de pares con la menor distancia de hamming

Question

Aug 17, 2011, 12:58 AM

Cálculo rápido de pares con la menor distancia de hamming

Problem

Suponga que tiene N (~ 100k-1m) enteros / cadenas de bits cada K (por ejemplo, 256) bits de longitud. El algoritmo debe devolver los k pares con la distancia de Hamming por pares más baja.

Ejempl

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

Para k = 1, debería devolver la lista {{i3, i4)}. Para k = 3, debería devolver {(i1, i2), (i1, i4), (i3, i4)}. Y así

Algoritm

La implementación ingenua calcula todas las distancias por pares, ordena los pares y devuelve el k con la distancia más baja: O (N ^ 2). ¿Hay mejores estructuras de datos o algoritmos? Parece que las ideas de Encuentre eficientemente cadenas binarias con poca distancia de Hamming en un conjunto grande no se puede usar ya que no existe un único número entero de consulta.