Finden Sie alle Wertepaare, die nahe unter der Hamming-Distanz liegen

Ich habe ein paar Millionen 32-Bit-Werte. Für jeden Wert möchte ich alle anderen Werte innerhalb eines Hamming-Abstands von 5 finden. Beim naiven Ansatz erfordert dies $O(N^2)$ -Vergleiche, die ich vermeiden möchte.

Ich erkannte, dass, wenn ich diese 32-Bit-Werte nur als Ganzzahlen behandelte und die Liste einmal sortierte, Werte, die sich nur in den niedrigstwertigen Bits unterschieden, sehr nahe beieinander lagen. Dies ermöglicht mir ein kürzeres "Fenster" oder einen kürzeren Zahlenbereich, in dem ich tatsächliche paarweise Vergleiche für die genaue Hamming-Entfernung durchführen kann. Wenn jedoch 2 Werte nur in den Bits höherer Ordnung variieren, landen sie außerhalb dieses "Fensters" und erscheinen an entgegengesetzten Enden der sortierten Liste. Z.B

11010010101001110001111001010110

01010010101001110001111001010110

wäre sehr weit voneinander entfernt, obwohl ihre Hamming-Distanz 1 beträgt. Da die Hamming-Distanz zwischen 2 Werten erhalten bleibt, wenn beide gedreht werden, habe ich herausgefunden, dass es wahrscheinlich 32 Werte sind, wenn man 32 Linksdrehungen macht und dann die Liste jedes Mal sortiert wird in mindestens einer von ihnen nah genug in der sortierten Liste landen.

1. Obwohl dieser Ansatz gute Ergebnisse liefert, bemühe ich mich, die Richtigkeit dieses Ansatzes formal festzustellen.

2. Muss ich wirklich alle 32-Bit-Rotationen ausführen, da ich nach übereinstimmenden Werten mit einem Hamming-Abstand von oder weniger suche ? Wenn beispielsweise und meine Fenstergröße 1000 beträgt, muss ich maximal 24 Bit drehen, denn selbst wenn das Streubit in einem der 8 Bits niedrigerer Ordnung erscheint, unterscheiden sich die resultierenden Zahlen nicht um mehr als 1000.$k$$k=1$

Wie bereits erwähnt, ist Ihr Ansatz problematisch, denn wenn 2 Bitmaps gleichmäßig verteilte Unterschiede aufweisen, gibt es bei jeder Drehung Unterschiede bei einigen höherwertigen Bits.

Sie können Ihren Ansatz verallgemeinern, indem Sie die Bitposition auf komplexere Weise permutieren. Wenn Sie eine zufällige Permutation von Bits auswählen, werden alle Unterschiede zwischen 2 Bitmaps mit Abstand in den 16 niederwertigen Bits mit einer Wahrscheinlichkeit von besser als . Wenn Sie also einige hundert Mal wiederholen, sollten Sie einen sehr großen Anteil Ihrer Bitmap-Paare finden. Für jeden Versuch liegt die Anzahl der zu testenden Paare (mit denselben 16 hohen Bits) nahe bei (für ).$5$$1/50$$64\cdot N$$N\approx 2^{22}$

Ich würde jedoch auch den folgenden Ansatz versuchen. Erstellen Sie eine Liste Ihrer Bitmaps, die an höchstens 2 Bitpositionen geändert wurden, und sortieren Sie diese Liste. Wenn diese Liste Kollisionen enthält, befinden sich zwei Bitmaps in der Entfernung$4$ . Zählen Sie dann alle Werte Ihrer anfänglichen Bitmaps auf, die an drei Positionen geändert wurden, und durchsuchen Sie sie in der Liste, um Bitmap-Paare in Abstand . Die Speicherkosten dieser Ansatz erfordert die Speicherung Elemente und die Anzahl der Elemente in der zweiten Phase zu suchen , ist .$5$$529\cdot N$$4960\cdot N$

Zusätzliche Information:

1. Die Wahrscheinlichkeit, dass$5$$16$$32$ $$\frac{\binom{16}{5}}{\binom{32}{5}}\approx 0.0217$$
2. Aufbau der Listen für jedes Element in der ursprünglichen Liste in die erweiterte Liste aufgenommen: das Element selbst, wobei sich alle Elemente an einer Position und alle Elemente an zwei Positionen unterscheiden (wobei die Informationen über das ursprüngliche Element erhalten bleiben). Die Anzahl der Kopien für jedes Element beträgtJede Kollision innerhalb dieser Liste (nach dem Sortieren erkannt) entspricht höchstens zwei ursprünglichen Elementen in der Entfernung . Beachten Sie, dass jedes Paar mehrmals erkannt werden kann, sodass Sie Duplikate entfernen müssen (dies war jedoch bereits bei Ihrem ursprünglichen Algorithmus der Fall).$1+32+\binom{32}{2}=529.$$4$
3. Für den letzten Durchgang ist es vorzuziehen, die erweiterte Liste der Elemente zu beschneiden, um nur diejenigen im exakten Abstand von ihrem ursprünglichen Element zu halten. Erstellen Sie dann für jedes Originalelement die Elemente in Abstand und suchen Sie sie in der erweiterten Liste. Sie müssen erneut Duplikate entfernen, da jedes Paar Mal erkannt wird . [Mit besonderer Sorgfalt können Sie wahrscheinlich die meisten Duplikate antizipieren / vermeiden, aber ich bin mir nicht sicher, ob sich die Mühe lohnt.]$2$$\binom{32}{3}=4960$$3$$\binom{5}{3}=10$

Die Antwort von minar ist ausgezeichnet und wahrscheinlich der richtige Ansatz für dieses spezielle Problem. Ich werde jedoch noch einen möglichen Ansatz erwähnen:

Sie können eine lokalitätssensitive Hash-Funktion (LSH) verwenden. Eine ortsempfindliche Hash-Funktion ist so ausgelegt, dass ist, wenn in Hamming-Entfernung nahe beieinander liegen . Wenn Sie einen solchen Hash , können Sie alle Ihre Werte in einer Hash-Tabelle speichern (mit der Hash-Funktion und offenem Hashing), und dann können Sie sehr schnell alle Wertepaare finden, die sich in Hamming-Entfernung befinden . Es gibt verschiedene Techniken zum Aufbau eines LSH; In den Referenzen zu diesem Thema finden Sie mehrere Kandidaten.$H$$x,y$$H(x)=H(y)$$H$$H$

Für Ihr spezielles Problem (mit den von Ihnen genannten spezifischen Parametern) erwarte ich jedoch, dass sich die beiden Algorithmen von minar in der Praxis als besser erweisen als jedes LSH-basierte Schema. Ich erwähne dies nur für den Fall, dass andere Leser mit einem ähnlichen Problem zu dieser Frage kommen, aber mit anderen Parametern, bei denen LSH möglicherweise sinnvoller ist.