Wie kann ich den Hamming-Abstand zwischen Binärzeichenfolgen in SQL effizient berechnen?

Hamming-Distanzberechnung für Binärzeichenfolgen in SQL

Problemstellung:

Datenbanktabellen speichern SHA256-Hashes häufig als Binärwerte. Die Hamming-Distanz, die die Anzahl der bitweisen Unterschiede zwischen zwei Hashes darstellt, ist eine entscheidende Metrik für die Ähnlichkeitsanalyse. Ziel dieses Artikels ist es, eine SQL-Lösung zur Berechnung der Hamming-Distanz zwischen einem gegebenen Wert und jedem Hash in einer bestimmten Spalte bereitzustellen.

Bestehender ineffizienter Ansatz:

Binärzeichenfolgen in kleinere Ganzzahlblöcke zerlegen, Das Berechnen der Hamming-Distanz für jeden Block und das anschließende Summieren der Ergebnisse ist eine umständliche und leistungsbeschränkte Methode.

Verbesserter Ansatz:

Das Speichern von Hashes in mehreren BIGINT-Spalten anstelle einer einzelnen BINARY-Spalte führt zu erheblichen Verbesserungen Leistung. Dies ermöglicht die Erstellung benutzerdefinierter Funktionen, mit denen die Hamming-Distanz zwischen mehreren BIGINT-Werten effizient berechnet werden kann.

Hamming-Distanzfunktion für BIGINTs:

Die folgende benutzerdefinierte Funktion kann erstellt werden, um die Hamming-Distanz zwischen mehreren BIGINT-Werten zu berechnen vier BIGINTs:

<code class="sql">CREATE FUNCTION HAMMINGDISTANCE(
  A0 BIGINT, A1 BIGINT, A2 BIGINT, A3 BIGINT, 
  B0 BIGINT, B1 BIGINT, B2 BIGINT, B3 BIGINT
)
RETURNS INT DETERMINISTIC
RETURN 
  BIT_COUNT(A0 ^ B0) +
  BIT_COUNT(A1 ^ B1) +
  BIT_COUNT(A2 ^ B2) +
  BIT_COUNT(A3 ^ B3);</code>

Verwendungsbeispiel:

Mit dieser Funktion können Sie Tabelleneinträge nach ihrer Hamming-Distanz zu einem bereitgestellten Wert sortieren, indem Sie die folgende Abfrage verwenden:

<code class="sql">SELECT * FROM table 
  ORDER BY HAMMINGDISTANCE(col0, col1, col2, col3, UNHEX(<insert supplied sha256 hash here>)) ASC 
  LIMIT 10</code>

Fazit:

Das Aufteilen von SHA256-Hashes in vier BIGINT-Spalten und die Verwendung einer benutzerdefinierten Funktion ist ein äußerst effizienter Ansatz zur Berechnung der Hamming-Distanz in SQL. Diese Methode verbessert die Leistung erheblich gegenüber der Speicherung von Hashes als BINÄR-Werte und der Verwendung herkömmlicher ganzzahlbasierter Berechnungen.

Das obige ist der detaillierte Inhalt vonWie kann ich den Hamming-Abstand zwischen Binärzeichenfolgen in SQL effizient berechnen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!