Hamming Distancia en cadenas binarias en SQL

Question

Tengo una mesa en mi DB donde almaceno sha256 hash en una columna binaria (32). Estoy buscando una forma de calcular la distancia de hamming de las entradas en la columna a un valor suministrado, es decir, algo así:

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 cuerdas A y B se define como BIT_COUNT(A^B), donde ^ está el operador XOR bitwise y bit_count devuelve el número de 1 en la cadena binaria).

Ahora, sé que tanto la función ^ operador y bit_count solo funcionan en enteros y, por lo tanto, diría que probablemente la única forma de hacerlo sería romper las cuerdas binarias en subcadenas, lanzar cada subcadena binaria a entero, calcular el Hamming Distancia en cuanto a la subcadena y luego agrégalos. El problema con esto es que suena terriblemente complicado, no eficiente y definitivamente no elegante. Por lo tanto, mi pregunta es: ¿podrías sugerir algo mejor? (Tenga en cuenta que estoy en alojamiento compartido y, por lo tanto, no puedo modificar el servidor DB o las bibliotecas de carga)

Editar (1): Obviamente, cargando toda la tabla en PHP y hacer los cálculos allí sería posible, pero prefiero evitarlo porque esta tabla probablemente crecerá bastante grande.

editar (2): el servidor DB es mysql 5.1

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

Editar (4): Acabo de descubrir que usar 4 bigints para almacenar el hash en lugar de un binario (32) produce mejoras de velocidad masivas (más de 100 veces más rápida). Vea los comentarios a mi respuesta a continuación.

Answer 1

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

En mi caso (32 bytes) esto significaría usar 4 BIGINT columnas y usando 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);

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

---

FWIW, este es el código al que estaba insinuando mientras explicaba el problema. Las mejores formas de lograr lo mismo son bienvenidos (especialmente no me gustan las conversiones binarias> hex / decimales):

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

Answer 2

Pregunta interesante, he encontrado una manera de hacer esto para un binary(3) Eso podría funcionar tan bien 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;

los replace Elimina todos los ceros, y la longitud del resto es el número de otros. (La conversión a binaria omite los ceros liderados, por lo que contar los ceros no funcionaría).

Esto imprime 6, que coincide con el número de otros en

0xAAAAAA ^ 0x888888 = 0x222222 = 0b1000100010001000100010