Comment puis-je calculer efficacement la distance de Hamming entre les chaînes binaires en SQL ?

Calcul de la distance de Hamming sur les chaînes binaires en SQL

Énoncé du problème :

Les tables de base de données stockent souvent les hachages SHA256 sous forme de valeurs binaires. La distance de Hamming, qui représente le nombre de différences au niveau du bit entre deux hachages, est une mesure cruciale pour l'analyse de similarité. Cet article vise à fournir une solution SQL pour calculer la distance de Hamming entre une valeur donnée et chaque hachage dans une colonne spécifiée.

Approche inefficace existante :

Décomposer les chaînes binaires en morceaux entiers plus petits, calculer la distance de Hamming pour chaque morceau, puis additionner les résultats est une méthode lourde et limitée en performances.

Approche améliorée :

Le stockage des hachages dans plusieurs colonnes BIGINT au lieu d'une seule colonne BINARY s'améliore considérablement performance. Cela permet la création de fonctions personnalisées capables de calculer efficacement la distance de Hamming entre plusieurs valeurs BIGINT.

Fonction de distance de Hamming pour les BIGINT :

La fonction personnalisée suivante peut être créée pour calculer la distance de Hamming entre quatre BIGINT :

<code class="sql">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);</code>

Exemple d'utilisation :

Avec cette fonction, vous pouvez trier les entrées de table en fonction de leur distance de Hamming jusqu'à une valeur fournie à l'aide de la requête suivante :

<code class="sql">SELECT * FROM table 
  ORDER BY HAMMINGDISTANCE(col0, col1, col2, col3, UNHEX(<insert supplied sha256 hash here>)) ASC 
  LIMIT 10</code>

Conclusion :

Diviser les hachages SHA256 en quatre colonnes BIGINT et utiliser une fonction personnalisée est une approche très efficace pour calculer la distance de Hamming en SQL. Cette méthode améliore considérablement les performances par rapport au stockage des hachages sous forme de valeurs BINAIRES et à l'utilisation de calculs conventionnels basés sur des nombres entiers.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!