Ich habe eine relativ einfache Sache, die ich tun möchte:

Wenn eine Abfragenummer Q, eine Abfragedistanz d und eine Menge von Zahlen S angegeben werden, bestimmen Sie, ob S @ enthält oder nichirgendei Zahlen mit einer Hamming-Distanz kleiner oder gleich d.

Die einfachste Lösung besteht darin, S zu einer Liste zu machen und die Entfernungen zu berechnen. Wenn ein Abstand berechnet wird, der kleiner oder gleich d ist, ist die Rückgabe WAHR.

Aber wenn ich bedenke, dass ich nur nach einer Existenz suchen möchte, sollte etwas schneller als eine lineare Zeitlösung möglich sein.

Eine Sache, die ich versucht habe, ist ein M-Baum. Unter Bezugnahme auf einige andere Fragen zum Stackoverflow enthält der Wikipedia-Artikel https: //en.wikipedia.org/wiki/M-tre) und zwei bereits vorhandene Implementierungen, ich habe gestern mehrere Stunden damit verbracht, eine benutzerdefinierte Lösung zu implementieren. Das Schöne an diesem Problem ist, dass es tatsächlich billiger ist, Popcount über das XOR von zwei Zahlen zu berechnen (mithilfe eines SSE-Befehls), als Zahlen zu speichern, mit denen die Berechnung der Metrik vermieden werden kann könnte vereinfacht und auf Geschwindigkeit optimiert werden.

Die Ergebnisse waren sehr enttäuschend. Es stellt sich heraus, dass der metrische Radius, mit dem ich zu tun habe, im Vergleich zur minimalen Hamming-Distanz klein ist. Beispielsweise beträgt der maximale Hamming-Abstand im Bereich von 12-Bit-Zahlen 12. Wenn der von mir gesuchte Mindestwert 4 ist, bleibt nicht viel Platz für eine gute, nicht überlappende Partitionierung. Tatsächlich habe ich genau das versucht, indem ich mit Brute Force einen Satz von 12-Bit-Zahlen mit einer Hamming-Distanz von mindestens 4 erstellt und dann (mit Brute Force) eine optimale binäre Baumpartitionierung gefunden habe, sodass ein Suchalgorithmus eine minimale Anzahl von Knoten besuchen konnte. Wenn ich willAnzahei der Anzahl festgelegter Elemente innerhalb von d der Abfrage kann ich die Anzahl der Knotenbesuche nicht unter 30% der Gesamtzahl reduzieren. Wenn ich feststelle, dass der erste Knotenbesuch bei 4% liegt, wird der Vorgang abgebrochen. Das bedeutet, dass ich mehr oder weniger eine Lösung mit linearer Zeit erstellt habe, bei der der Aufwand für den ausgefeilten Baumsuchalgorithmus in etwa dem Ersparnis entspricht, dass nicht so viele gesetzte Elemente überprüft werden müssen.

Aber was ich machen will ist sehr begrenzt. Ich möchte nicht einmal die Anzahl der gesetzten Mitglieder mit einem Abfragedistanz <= d zählen, geschweige denn sie aufzählen. Ich möchte nur auf Existenz prüfen. Das lässt mich über Dinge wie Bloom-Filter und Hashes nachdenken.

Ich habe auch darüber nachgedacht, eine Diagrammstruktur zu erstellen, bei der festgelegte Elemente durch Kanten mit Gewichten verbunden sind. Ausgehend von der Tatsache, dass die Hamming-Distanz die Dreieck-Ungleichung berücksichtigt, scheint es mir eine Möglichkeit zu geben, dieses Diagramm so zu durchsuchen, dass Kantenquerungen in eine Richtung führen, die wahrscheinlich kleiner ist als die der Abfrage, aber ich weiß nicht einmal wirklich, wo ich anfangen soll Hier

Hat jemand andere Vorschläge für eine Lösung, die die Leistung eines einfachen Iterierens eines Arrays übertreffen könnte?

EDIT und MOTIVATION:

Letztendlich stammt dies aus einer Frage der Codierungstheorie. Wie viele Codes mit einem minimalen Hamming-Abstand d kann ich für eine bestimmte gerade Zahl d und Wortgröße N in eine N-Bit-Zahl einpassen? Dies ermöglicht die Erzeugung eines Codes, der Fehler von d / 2 Bits erkennen und Fehler von bis zu d / 2-1 Bits korrigieren kann. Wir kennen Shannon-Limit-Codes wie LDPC, aber das ist für lange Codes mit nebulöser Hamming-Distanz, und es dauert ewig, bis sie dekodiert werden. Es gibt auch Multi-Bit-Fehlercodes wie OLSC, die sich schnell dekodieren lassen, aber alles andere als platzsparend sind. Andererseits sind erweiterte Hamming-Codes (SECDED-Codes) für d = 4 optimal kompakt. Ich habe BCH-basierte Methoden zur Erstellung eines DECTED-Codes gesehen, weiß aber nicht, ob sie optimal sind. Um die optimalen Codierungen zu untersuchen, wollte ich alternative Sätze von Codes mit N Bits und einem willkürlichen d erzeugen und Schaltungen erzeugen, um sie zu codieren und zu decodieren, wobei die kompaktesten ausgewählt wurden. Ich hatte auch gehofft, einige Muster zu finden, die wir für längere Codes ausnutzen könnten.

Wenn dies (a) noch nicht geschehen ist, (b) machbar ist und (c) jemand eine Arbeit mitschreiben möchte, lassen Sie es mich bitte wissen. :)