Hamming Distancia en cadenas binarias en SQL
-
23-10-2019 - |
Pregunta
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.
Solución
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)
);
Otros consejos
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