Mysql
 sql >> Datenbank >  >> RDS >> Mysql

Hamming-Distanz für binäre Zeichenfolgen in SQL

Es scheint, dass die Daten in einem BINARY gespeichert werden Spalte ist ein Ansatz, der zwangsläufig schlecht abschneidet. Der einzige schnelle Weg, um anständige Leistung zu erzielen, besteht darin, den Inhalt von BINARY aufzuteilen Spalte in mehreren BIGINT Spalten, die jeweils einen 8-Byte-Teilstring der Originaldaten enthalten.

In meinem Fall (32 Bytes) würde dies bedeuten, 4 BIGINT zu verwenden Spalten und mit dieser Funktion:

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);

Die Verwendung dieses Ansatzes ist in meinen Tests über 100-mal schneller als die Verwendung von BINARY Ansatz.

FWIW, das ist der Code, auf den ich bei der Erklärung des Problems hingewiesen habe. Bessere Möglichkeiten, dasselbe zu erreichen, sind willkommen (ich mag besonders die binären> hex> dezimalen Konvertierungen nicht):

CREATE FUNCTION HAMMINGDISTANCE(A BINARY(32), B BINARY(32))
RETURNS INT DETERMINISTIC
RETURN 
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 1,  8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 1,  8)), 16, 10)
  ) +
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 9,  8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 9,  8)), 16, 10)
  ) +
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 17, 8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 17, 8)), 16, 10)
  ) +
  BIT_COUNT(
    CONV(HEX(SUBSTRING(A, 25, 8)), 16, 10) ^ 
    CONV(HEX(SUBSTRING(B, 25, 8)), 16, 10)
  );