Trouver efficacement des chaînes binarys avec une faible distance de Hamming dans un grand ensemble

Problème:

Étant donné une liste volumineuse (~ 100 millions) d’entiers non signés de 32 bits, une valeur d’entrée d’entier non signée de 32 bits et une distance de Hamming maximale, renvoyer tous les membres de liste se trouvant dans la distance de Hamming spécifiée.

La structure de données réelle à contenir de la liste est ouverte, les exigences de performance imposent une solution en mémoire, le coût de la construction de la structure de données est secondaire, le faible coût d’interrogation de la structure de données est critique.

Exemple:

For a maximum Hamming Distance of 1 (values typically will be quite small) And input: 00001000100000000000000001111101 The values: 01001000100000000000000001111101 00001000100000000010000001111101 should match because there is only 1 position in which the bits are different. 11001000100000000010000001111101 should not match because 3 bit positions are different. 

Mes pensées jusqu’à présent:

Pour le cas dégénéré d’une distance de Hamming de 0, utilisez simplement une liste sortingée et effectuez une recherche binary pour la valeur d’entrée spécifique.

Si la distance de Hamming n’était que de 1, je pourrais retourner chaque bit dans l’entrée d’origine et répéter les 32 fois ci-dessus.

Comment puis-je efficacement (sans balayer la liste entière) découvrir les membres de la liste avec une distance de Hamming> 1.

Question: Que soaps-nous de la distance de Hamming d (x, y)?

Répondre:

  1. C’est non négatif: d (x, y) ≥ 0
  2. Ce n’est que zéro pour des entrées identiques: d (x, y) = 0 ⇔ x = y
  3. Il est symésortingque: d (x, y) = d (y, x)
  4. Il obéit à l’ inégalité du sortingangle , d (x, z) ≤ d (x, y) + d (y, z)

Question: Pourquoi on s’en soucie?

Réponse: Parce que cela signifie que la distance de Hamming est une mésortingque pour un espace mésortingque . Il existe des algorithmes d’indexation des espaces mésortingques.

  • Arbre mésortingque (Wikipedia)
  • BK-tree (Wikipedia)
  • M-tree (Wikipedia)
  • Arbre VP (Wikipedia)
  • Arbre de couverture (Wikipedia)

Vous pouvez également rechercher des algorithmes pour “indexation spatiale” en général, sachant que votre espace n’est pas euclidien mais qu’il s’agit d’ un espace mésortingque. De nombreux ouvrages sur ce sujet couvrent l’indexation des chaînes à l’aide d’une mesure telle que la distance de Hamming.

Note de bas de page: Si vous comparez la distance de Hamming entre des chaînes de largeur fixe, vous pourrez peut-être obtenir une amélioration significative des performances en utilisant les valeurs insortingnsèques de l’assemblage ou du processeur. Par exemple, avec GCC ( manuel ), vous faites ceci:

 static inline int distance(unsigned x, unsigned y) { return __builtin_popcount(x^y); } 

Si vous informez ensuite GCC que vous comstackz pour un ordinateur avec SSE4a, alors je pense que cela devrait se réduire à quelques opcodes.

Edit: Selon un certain nombre de sources, ceci est parfois / souvent plus lent que le masque / shift / add habituel. L’parsing comparative montre que sur mon système, une version C surpasse d’environ 160% le __builtin_popcount de GCC.

Addendum: J’étais curieux du problème moi-même, alors j’ai présenté trois implémentations: recherche linéaire, arbre BK et arbre VP. Notez que les arbres VP et BK sont très semblables. Les enfants d’un nœud dans un arbre BK sont des “coquilles” d’arbres contenant des points qui sont chacun à une distance fixe du centre de l’arbre. Un nœud dans un arbre VP a deux enfants, l’un contenant tous les points d’une sphère centrée sur le centre du nœud et l’autre contenant tous les points extérieurs. Vous pouvez donc considérer un nœud VP comme un nœud BK avec deux “shells” très épaisses au lieu de plusieurs plus fines.

Les résultats ont été capturés sur mon PC à 3,2 GHz et les algorithmes ne tentent pas d’utiliser plusieurs cœurs (ce qui devrait être facile). J’ai choisi une taille de base de 100 millions d’entiers pseudo-aléatoires. Les résultats sont la moyenne de 1000 requêtes pour la distance 1..5 et 100 requêtes pour 6..10 et la recherche linéaire.

  • Base de données: 100M entiers pseudo-aléatoires
  • Nombre d’essais: 1000 pour la distance 1..5, 100 pour la distance 6..10 et linéaire
  • Résultats: Nombre moyen de requêtes (très approximatif)
  • Vitesse: nombre de requêtes par seconde
  • Couverture: pourcentage moyen de la firebase database examinée par requête
                 - BK Tree - - VP Tree - - Linéaire -
 Dist Dist. Vitesse Vitesse Vitesse Vitesse Cv
 1 0,90 3800 0,048% 4200 0,048%
 2 11 300 0,68% 330 0,65%
 3 130 56 3,8% 63 3,4%
 4 970 18 12% 22 10%
 5 5700 8,5 26% 10 22%
 6 2,6e4 5,2 42% 6,0 37%
 7 1,1e5 3,7 60% 4,1 54%
 8 3,5e5 3,0 74% 3,2 70%
 9 1,0e6 2,6 85% 2,7 82%
 10 2,5e6 2,3 91% 2,4 90%
 toute 2.2 100%

Dans votre commentaire, vous avez mentionné:

Je pense que les arbres BK pourraient être améliorés en générant un tas d’arbres BK avec des nœuds racine différents et en les répartissant.

Je pense que c’est exactement la raison pour laquelle l’arbre VP se comporte (légèrement) mieux que l’arbre BK. Étant plus “profond” que “moins profond”, il se compare à un plus grand nombre de points plutôt qu’à des comparaisons plus fines avec moins de points. Je soupçonne que les différences sont plus extrêmes dans les espaces de plus grande dimension.

Un dernier conseil: les nœuds feuilles dans l’arborescence doivent simplement être des tableaux plats d’entiers pour un balayage linéaire. Pour les petits ensembles (peut-être 1000 points ou moins), cela sera plus rapide et plus efficace en termes de mémoire.

J’ai écrit une solution où je représente les nombres d’entrées dans un ensemble de 2 32 bits, ainsi je peux vérifier dans O (1) si un certain nombre est dans l’entrée. Ensuite, pour un nombre interrogé et une distance maximale, je génère récursivement tous les nombres dans cette distance et les vérifie par rapport aux bits.

Par exemple, pour la distance maximale 5, il s’agit de 242825 nombres ( sum d = 0 à 5 {32 choisissez d} ). À titre de comparaison, la solution VP-Tree de Diesortingch Epp, par exemple, passe par 22% des 100 millions de numéros, soit 22 millions de numéros.

J’ai utilisé le code / les solutions de Diesortingch comme base pour append ma solution et la comparer avec la sienne. Voici les vitesses, en requêtes par seconde, pour des distances maximales allant jusqu’à 10:

 Dist BK Tree VP Tree Bitset Linear 1 10,133.83 15,773.69 1,905,202.76 4.73 2 677.78 1,006.95 218,624.08 4.70 3 113.14 173.15 27,022.32 4.76 4 34.06 54.13 4,239.28 4.75 5 15.21 23.81 932.18 4.79 6 8.96 13.23 236.09 4.78 7 6.52 8.37 69.18 4.77 8 5.11 6.15 23.76 4.68 9 4.39 4.83 9.01 4.47 10 3.69 3.94 2.82 4.13 Prepare 4.1s 21.0s 1.52s 0.13s times (for building the data structure before the queries) 

Pour les petites distances, la solution de bitset est de loin la plus rapide des quatre. L’auteur de la question Eric a commenté ci-dessous que la plus grande distance d’intérêt serait probablement 4-5. Naturellement, ma solution de bitset devient plus lente sur de plus grandes distances, même plus lente que la recherche linéaire (pour la distance 32, elle passerait par 2 32 numéros). Mais pour la distance 9, cela mène toujours facilement.

J’ai également modifié les tests de Diesortingch. Chacun des résultats ci-dessus permet à l’algorithme de résoudre au moins trois requêtes et autant de requêtes que possible en environ 15 secondes (je fais des rounds avec des requêtes 1, 2, 4, 8, 16, jusqu’à ce qu’au moins 10 secondes passé au total). C’est assez stable, j’ai même des chiffres similaires pour seulement 1 seconde.

Mon processeur est un i7-6700. Mon code (basé sur celui de Diesortingch) est là (ignorez la documentation au moins pour le moment, ne savez pas quoi faire à ce sujet, mais l’ tree.c contient tout le code et mon test.bat montre comment j’ai compilé et exécuté (j’ai utilisé les drapeaux du Makefile de Diesortingch)). Raccourci vers ma solution .

Une mise en garde: les résultats de mes requêtes ne contiennent des chiffres qu’une seule fois, donc si la liste d’entrée contient des numéros en double, cela peut ou non être souhaité. En l’occurrence l’auteur Eric, il n’y avait pas de doublons (voir commentaire ci-dessous). Dans tous les cas, cette solution peut être utile pour les personnes qui n’ont pas de doublons dans l’entrée ou ne veulent pas ou ont besoin de doublons dans les résultats de la requête (je pense que les résultats de la requête pure un autre code transforme les nombres en quelque chose d’autre, par exemple une carte mappant un nombre à une liste de fichiers dont le hash est ce nombre).

Que diriez-vous de sortinger la liste et de faire une recherche binary dans cette liste sortingée sur les différentes valeurs possibles dans votre distance de Hamming?

Vous pouvez pré-calculer chaque variation possible de votre liste d’origine dans la distance de Hamming spécifiée et la stocker dans un filtre Bloom. Cela vous donne un “NON” rapide mais pas nécessairement une réponse claire sur “OUI”.

Pour OUI, stockez une liste de toutes les valeurs d’origine associées à chaque position du filtre anti-effraction et parcourez-les une par une. Optimisez la taille de votre filtre de floraison pour les compromis vitesse / mémoire.

Vous ne savez pas si tout fonctionne exactement, mais cela semble être une bonne approche si vous avez une RAM d’exécution à graver et que vous êtes prêt à passer beaucoup de temps en pré-calcul.

Une approche possible pour résoudre ce problème consiste à utiliser une structure de données de type disjoint . L’idée est de fusionner les membres de la liste avec une distance de Hamming <= k dans le même ensemble. Voici le contour de l'algorithme:

  • Pour chaque membre de la liste, calculer chaque valeur possible avec la distance de Hamming <= k. Pour k = 1, il y a 32 valeurs (pour les valeurs 32 bits). Pour k = 2, 32 + 32 * 31/2 valeurs.

    • Pour chaque valeur calculée, testez si elle se trouve dans l’entrée d’origine. Vous pouvez utiliser un tableau de taille 2 ^ 32 ou une carte de hachage pour effectuer cette vérification.

    • Si la valeur est dans l’entrée d’origine, effectuez une opération “union” avec le membre de liste .

    • Gardez le nombre d’opérations d’union exécutées dans une variable.

Vous lancez l’algorithme avec N ensembles disjoints (où N est le nombre d’éléments dans l’entrée). Chaque fois que vous exécutez une opération d’union, vous diminuez de 1 le nombre de jeux disjoints. Lorsque l’algorithme se termine, la structure de données de l’ensemble disjoint aura toutes les valeurs avec la distance de Hamming <= k regroupées en ensembles disjoints. Cette structure de données d'ensemble disjoint peut être calculée en temps quasi linéaire .

Une approche courante (au moins commune à moi) consiste à diviser votre chaîne de bits en plusieurs morceaux et à interroger ces blocs pour obtenir une correspondance exacte en tant qu’étape de pré-filtrage. Si vous travaillez avec des fichiers, vous créez autant de fichiers que vous en avez (par exemple 4 ici), chaque fragment étant permuté en avant, puis sortingez les fichiers. Vous pouvez utiliser une recherche binary et vous pouvez même élargir votre recherche au-dessus et au-dessous d’un bloc correspondant pour obtenir un bonus.

Vous pouvez ensuite effectuer un calcul de distance au niveau des bits sur les résultats renvoyés, ce qui ne devrait être qu’un sous-ensemble plus petit de votre dataset global. Cela peut être fait en utilisant des fichiers de données ou des tables SQL.

Donc pour récapituler: Disons que vous avez un tas de chaînes de 32 bits dans un DB ou des fichiers et que vous voulez trouver tous les hash qui se trouvent dans une distance de Hamming de 3 bits ou moins de votre chaîne de bits “query”:

  1. créer une table à quatre colonnes: chacune contiendra une tranche de 8 bits (sous forme de chaîne ou int) des hachages de 32 bits, islice 1 à 4. Ou si vous utilisez des fichiers, créez quatre fichiers, chacun représentant une permutation des tranches ayant un “islice” à l’avant de chaque “rangée”

  2. découpez la chaîne de bits de votre requête de la même manière dans qslice 1 à 4.

  3. interrogez cette table de sorte que qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4 . Cela vous donne toutes les chaînes qui sont dans les 7 bits ( 8 - 1 ) de la chaîne de requête. Si vous utilisez un fichier, effectuez une recherche binary dans chacun des quatre fichiers permutés pour obtenir les mêmes résultats.

  4. pour chaque chaîne de bits renvoyée, calculez la distance de hamming exacte par paire avec votre chaîne de bits d’interrogation (en reconstruisant les chaînes de bits côté index à partir des quatre tranches à partir de la firebase database ou d’un fichier permuté)

Le nombre d’opérations à l’étape 4 devrait être beaucoup moins qu’un calcul de hamming complet par paires de votre table entière et est très efficace dans la pratique. En outre, il est facile de partager les fichiers en fichiers plus petits, ce qui nécessite plus de rapidité grâce au parallélisme.

Maintenant, bien sûr, dans votre cas, vous recherchez une auto-jointure de sorting, c’est-à-dire toutes les valeurs qui sont à une certaine distance les unes des autres. La même approche fonctionne toujours à mon humble avis, bien que vous deviez vous développer à partir d’un sharepoint départ pour les permutations (en utilisant des fichiers ou des listes) qui partagent le bloc de départ et calculent la distance de blocage pour le cluster résultant.

Si vous travaillez en mémoire au lieu de fichiers, votre dataset de chaînes 100 bits 32 bits se situera dans la plage de 4 Go. Par conséquent, les quatre listes permutées peuvent nécessiter environ 16 Go de RAM. Bien que j’obtienne d’excellents résultats avec les fichiers mappés en mémoire, il faut moins de RAM pour les jeux de données de taille similaire.

Il existe des implémentations open source disponibles. Le meilleur dans l’espace est IMHO celui fait pour Simhash par Moz , C ++ mais conçu pour les chaînes de 64 bits et non 32 bits.

Moses Charikar a d’abord décrit AFAIK dans son document séminal “simhash” et dans le brevet Google correspondant:

  1. RECHERCHE APPROXIMATIVE DU VOISIN LE PLUS PROCHE DANS L’ESPACE DE MARTEAU

[…]

Étant donné les vecteurs de bits constitués de d bits chacun, nous choisissons N = O (n 1 / (1+)) permutations aléatoires des bits. Pour chaque permutation aléatoire σ, on maintient un ordre sortingé O σ des vecteurs de bits, dans l’ordre lexicographique des bits permutés par σ. Étant donné un vecteur de bit de requête q, nous trouvons le voisin le plus proche en procédant comme suit:

Pour chaque permutation σ, nous effectuons une recherche binary sur O σ pour localiser les deux vecteurs de bits les plus proches de q (dans l’ordre lexicographique obtenu par les bits permutés par σ). Nous recherchons maintenant dans chacun des ordres sortingés O σ examinant les éléments au-dessus et au-dessous de la position renvoyée par la recherche binary dans l’ordre de la longueur du plus long préfixe correspondant à q.

Monika Henziger a développé ce point dans son article “Trouver des pages Web quasi-dupliquées: une évaluation à grande échelle des algorithmes” :

3.3 Les résultats pour l’algorithme C

Nous avons partitionné la chaîne de bits de chaque page en 12 parties de 4 octets qui ne se chevauchent pas, créant ainsi 20 parties et calculant la similarité C de toutes les pages ayant au moins une partie en commun. Cette approche est garantie pour trouver toutes les paires de pages avec une différence allant jusqu’à 11, c.-à-d. La similarité C 373, mais il est possible que certaines disparaissent pour des différences plus importantes.

Ceci est également expliqué dans l’étude Detecting Near Duplicates pour Web Crawling par Gurmeet Singh Manku, Arvind Jain et Anish Das Sarma:

  1. LE PROBLÈME DE DISTANCE DU HAMMING

Définition: Étant donné une collection d’empreintes digitales à f-bits et une empreinte de requête F, identifier si une empreinte digitale existante diffère de F pour au plus k bits. (Dans la version en mode batch du problème ci-dessus, nous avons un ensemble d’empreintes de requêtes au lieu d’une seule empreinte de requête)

[…]

Intuition: Considérons une table sortingée de 2 df -bit d’empreintes vraiment aléatoires. Concentrez-vous sur les bits les plus significatifs de la table. Une liste de ces nombres de d bits équivaut à «presque un compteur» en ce sens que (a) il existe plusieurs combinaisons de bits 2 d et (b) très peu de combinaisons de bits d sont dupliquées. Par contre, les bits f-d moins significatifs sont «presque aléatoires».

Maintenant, choisissez d tel que | d – d | est un petit entier. Comme la table est sortingée, une seule sonde suffit pour identifier toutes les empreintes digitales correspondant à F dans les positions de bits les plus significatives. Depuis | d – d | est petit, le nombre de ces matches devrait également être faible. Pour chaque empreinte digitale correspondante, nous pouvons facilement déterminer si elle diffère de F dans au plus k positions de bits ou non (ces différences seraient naturellement limitées aux positions de bits les moins significatives).

La procédure décrite ci-dessus nous aide à localiser une empreinte digitale différente de F en positions de bit k, qui sont toutes limitées aux bits de f les moins significatifs de F. Cela prend en charge un nombre non négligeable de cas. Pour couvrir tous les cas, il suffit de construire un petit nombre de tables sortingées supplémentaires, comme indiqué dans la section suivante.

Remarque: J’ai posté une réponse similaire à une question liée à la firebase database uniquement