distance de Hamming sur les chaînes binaires dans SQL

Question

J'ai une table dans mon DB où je stocke SHA256 hash dans une colonne BINARY (32). Je suis à la recherche d'un moyen de calculer la distance de Hamming des entrées de la colonne à une valeur donnée, à savoir quelque chose comme:

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

(au cas où vous vous demandez, la distance de Hamming des chaînes A et B est définie comme BIT_COUNT(A^B), où ^ est l'opérateur XOR et BIT_COUNT retourne au niveau du bit le nombre de 1 dans la chaîne binaire).

Maintenant, je sais que tant l'opérateur ^ et la fonction BIT_COUNT ne fonctionne que sur Entiers et donc je dirais que probablement la seule façon de le faire serait de briser les chaînes binaires en sous-chaînes, fonte chaque sous-chaîne binaire entier , calculer la distance de Hamming substring-sage, puis les ajouter. Le problème est que ça sonne terriblement compliqué, pas efficace et certainement pas élégant. Ma question est donc: pourriez-vous suggérer une meilleure façon? (S'il vous plaît noter que je suis sur l'hébergement mutualisé et donc je ne peux pas modifier les bibliothèques de serveur DB ou charge)

modifier (1). Il est évident que le chargement de la table tout en PHP et faire les calculs, il serait possible, mais je préfère l'éviter parce que ce tableau va probablement croître assez grand

modifier (2): Le serveur DB est MySQL 5.1

modifier (3):. Ma réponse ci-dessous contient le code que je viens de décrire ci-dessus

modifier (4): Je viens de découvrir que l'aide de 4 bigints pour stocker le hachage au lieu d'un BINARY (32), on obtient des améliorations de vitesse massives (plus de 100 fois plus rapide). Voir les commentaires à ma réponse ci-dessous.

Answer 1

Il semble que le stockage des données dans une colonne de BINARY est une approche liée à de mauvais résultats. La seule façon rapide d'obtenir des performances décentes est de diviser le contenu de la colonne de BINARY dans plusieurs colonnes de BIGINT, contenant chacun une sous-chaîne de 8 octets des données d'origine.

Dans mon cas (32 octets) cela signifierait en utilisant 4 colonnes BIGINT et en utilisant cette fonction:

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

En utilisant cette approche, dans mes tests, est plus de 100 fois plus rapide que d'utiliser l'approche BINARY.

---

FWIW, voici le code que je faisant allusion à tout en expliquant le problème. De meilleures façons de faire la même chose sont les bienvenus (je ne suis pas particulièrement comme le binaire> hex> décimal conversions):

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

Question intéressante, je l'ai trouvé un moyen de le faire pour un binary(3) que le travail pourrait aussi bien pour 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;

Le replace supprime tous les zéros, et la longueur du reste est le nombre de uns. (La conversion en binaire passe sous silence les zéros en tête, comptant pour que les zéros ne marcherait pas.)

Cette impression 6, qui correspond au nombre de ceux qui en

0xAAAAAA ^ 0x888888 = 0x222222 = 0b1000100010001000100010