sql - hamming - distancia binaria

Hamming distancia en cadenas binarias en SQL

Question

Tengo una tabla en mi base de datos donde almaceno hashes SHA256 en una columna BINARY (32). Estoy buscando una forma de calcular la distancia de Hamming de las entradas en la columna a un valor proporcionado, es decir, algo así como:

SELECT * FROM table 
  ORDER BY HAMMINGDISTANCE(hash, UNHEX(<insert supplied sha256 hash here>)) ASC 
  LIMIT 10

(en caso de que se lo pregunte, la distancia de Hamming de las cadenas A y B se define como BIT_COUNT(A^B) , donde ^ es el operador XOR bit a bit y BIT_COUNT devuelve el número de 1s en la cadena binaria).

Ahora, sé que tanto el operador ^ como la función BIT_COUNT solo funcionan en INTEGER, así que diría que probablemente la única forma de hacerlo sería dividir las cadenas binarias en subcadenas, convertir cada subcadena binaria en entero, calcular el Hamming distancia en subcadena y luego agrégalos. El problema con esto es que suena terriblemente complicado, no eficiente y definitivamente no elegante. Mi pregunta, por lo tanto, es: ¿podría sugerir alguna forma mejor? (tenga en cuenta que estoy en alojamiento compartido y, por lo tanto, no puedo modificar el servidor de bases de datos ni cargar bibliotecas)

edit (1): Obviamente, cargar toda la tabla en PHP y hacer los cálculos allí sería posible, pero preferiría evitarlo porque esta tabla probablemente crezca bastante.

editar (2): el servidor de base de datos es MySQL 5.1

editar (3): Mi respuesta a continuación contiene el código que acabo de describir arriba.

editar (4): Acabo de descubrir que usar 4 BIGINT para almacenar el hash en lugar de BINARY (32) produce mejoras de velocidad masivas (más de 100 veces más rápido). Ver los comentarios a mi respuesta a continuación.

Answer 1

Interesante pregunta, he encontrado una manera de hacer esto para un binary(3) que podría funcionar también para un binary(32) :

drop table if exists BinaryTest;
create table  BinaryTest (hash binary(3));
insert BinaryTest values (0xAAAAAA);

set @supplied = cast(0x888888 as binary);

select  length(replace(concat(
            bin(ascii(substr(hash,1,1)) ^ ascii(substr(@supplied,1,1))),
            bin(ascii(substr(hash,2,1)) ^ ascii(substr(@supplied,2,1))),
            bin(ascii(substr(hash,3,1)) ^ ascii(substr(@supplied,3,1)))
        ),''0'',''''))
from    BinaryTest;

El replace elimina todos los ceros, y la longitud del resto es el número de unos. (La conversión a binario omite ceros a la izquierda, por lo que contar los ceros no funcionaría).

Imprime 6 , que coincide con el número de unidades

0xAAAAAA ^ 0x888888 = 0x222222 = 0b1000100010001000100010

Answer 2

Parece que almacenar los datos en una columna BINARY es un enfoque destinado a funcionar mal. La única forma rápida de obtener un rendimiento decente es dividir el contenido de la columna BINARY en varias columnas BIGINT , cada una con una subcadena de 8 bytes de los datos originales.

En mi caso (32 bytes) esto significaría usar 4 columnas BIGINT y usar esta función:

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

Usar este enfoque, en mi prueba, es más de 100 veces más rápido que usar el enfoque BINARY .

FWIW, este es el código que estaba insinuando al explicar el problema. Mejores formas de lograr lo mismo son bienvenidas (especialmente no me gustan las conversiones binarias> hexadecimales):

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