Schnelle Berechnung von Paaren mit geringstem Hamming-Abstand

Question

Problème

Angenommen, Sie haben N (~100k-1m) Ganzzahlen/Bitstrings, die jeweils K (z. B. 256) Bits lang sind. Der Algorithmus sollte die k Paare mit dem geringsten paarweisen Hamming-Abstand zurückgeben.

Beispiel

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

Für k=1 sollte es die Paarliste {(i3,i4)} zurückgeben. Für k=3 sollte sie {(i1,i2), (i1,i4), (i3,i4)} zurückgeben. Und so weiter.

Algorithmus

Bei der naiven Implementierung werden alle paarweisen Abstände berechnet, die Paare sortiert und das k mit dem geringsten Abstand zurückgegeben: O(N^2). Gibt es bessere Datenstrukturen oder Algorithmen? Es sieht so aus, als ob die Ideen aus Effiziente Suche nach binären Zeichenketten mit geringer Hamming-Distanz in großen Mengen kann nicht verwendet werden, da es keine einzige Abfrage-Ganzzahl gibt.

Answer 1

Die jüngste Veröffentlichung " Das Problem des engsten Paares unter der Hamming-Metrik " hat nur Algorithmen mit einem n^2-Faktor (es sei denn, K ist sehr groß). Das gilt sogar für die Suche nach nur einem einzigen Paar. Es scheint also schwer zu sein, dies zu verbessern, es sei denn, Sie machen weitere Annahmen über die Struktur Ihrer Instanzen. Wenn man zum Beispiel annimmt, dass die Hamming-Distanz nicht sehr groß ist, könnte man ein paar Spalten auswählen, die Strings entsprechend in Buckets einteilen, unter der Annahme, dass diese Spalten genau übereinstimmen, und dann den paarweisen Vergleich in jedem Bucket separat durchführen. Wiederholen Sie dies für einen weiteren Satz zufälliger Spalten, um die Wahrscheinlichkeit zu minimieren, dass Sie einige Paare übersehen.