Trouvez efficacement des chaînes binaires avec une faible distance de Hamming dans un grand ensemble

Question

< gagnantProblème :

Étant donné une longue liste (~ 100 millions) d'entiers 32 bits non signés, une valeur d'entrée d'entiers 32 bits non signés et un maximum Hamming Distance , renvoie tous les membres de la liste qui se trouvent dans la distance de Hamming spécifiée de la valeur d'entrée.

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

<₹Example:

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 triée et effectuez une recherche binaire pour la valeur d'entrée spécifique.

Si la distance de Hamming n'était jamais 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 découvrir efficacement (sans parcourir la liste entière) les membres de la liste avec une distance de Hamming> 1.

Answer 1

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

< gagnantRéponse :

1. Il 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étrique: d (x, y)= d (y, x)
4. Il obéit à l ' inégalité triangulaire , d (x, z) ≤ d (x, y ) + d (y, z)

Question: Pourquoi nous soucions-nous?

Réponse: parce que cela signifie que la distance de Hamming est une métrique pour un espace métrique . Il existe des algorithmes pour indexer les espaces métriques.

• Arbre métrique (Wikipedia)
• BK-tree (Wikipédia)
• M-tree (Wikipédia)
• VP-tree (Wikipédia)
• Arbre de couverture (Wikipedia)

Vous pouvez également rechercher des algorithmes pour "l'indexation spatiale" en général, en sachant que votre espace n'est pas euclidien mais qu'il est un espace métrique. De nombreux livres sur ce sujet couvrent l'indexation des chaînes en utilisant une métrique telle que la distance de Hamming.

Note de bas de page: Si vous comparez la distance de Hamming de chaînes de largeur fixe, vous pourrez peut-être obtenir une amélioration significative des performances en utilisant l'assemblage ou le processeur intrinsèque. 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 compilez pour un ordinateur avec SSE4a, alors je pense que cela devrait se réduire à quelques opcodes.

Edit: Selon un certain nombre de sources, c'est parfois / souvent plus lent que le code habituel de masque / décalage / ajout. L'analyse comparative montre que sur mon système, une version C surpasse d'environ 160% le __builtin_popcount de GCC.

Addendum: J'étais moi-même curieux de connaître le problème, j'ai donc profilé trois implémentations: recherche linéaire, arbre BK et arbre VP. Notez que les arbres VP et BK sont très similaires. 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 enfant contenant tous les points à l'extérieur. Vous pouvez donc considérer un nœud VP comme un nœud BK avec deux "coquilles" très épaisses au lieu de beaucoup plus fines.

Les résultats ont été capturés sur mon PC 3,2 GHz, et les algorithmes n'essaient pas d'utiliser plusieurs cœurs (ce qui devrait être facile). J'ai choisi une taille de base de données 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: 100 millions d'entiers pseudo-aléatoires
• Nombre de tests: 1000 pour la distance 1..5, 100 pour la distance 6..10 et linéaire
• Résultats: nombre moyen de résultats de requêtes (très approximatifs)
• Vitesse: nombre de requêtes par seconde
• Couverture: pourcentage moyen de la base de données examinée par requête

                -- BK Tree --   -- VP Tree --   -- Linear --
Dist    Results Speed   Cov     Speed   Cov     Speed   Cov
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%
any                                             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 groupe d'arbres BK avec différents nœuds racines et en les étalant.

Je pense que c'est exactement la raison pour laquelle l'arbre VP fonctionne (légèrement) mieux que l'arbre BK. Étant "plus profond" plutôt que "moins profond", il compare avec plus de points plutôt que d'utiliser des comparaisons plus fines avec moins de points. Je soupçonne que les différences sont plus extrêmes dans des dimensi plus élevés

espaces onaux.

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

Answer 2

J'ai écrit une solution où je représente les nombres d'entrée dans un ensemble de bits de 2 ³² bits, donc 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 de manière récursive tous les nombres à l'intérieur de cette distance et les compare avec l'ensemble de bits.

Par exemple, pour la distance maximale 5, il s'agit de 242825 nombres ( somme _{d= 0 à 5} {32 choisissez d} ). A titre de comparaison, la solution VP-tree de Dietrich Epp passe par exemple par 22% des 100 millions de nombres, c'est-à-dire par 22 millions de nombres.

J'ai utilisé le code / les solutions de Dietrich comme base pour ajouter ma solution et la comparer avec la sienne. Voici les vitesses, en requêtes par seconde, pour des distances maximales 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 du jeu de bits 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 jeu de bits devient plus lente pour de plus grandes distances, encore plus lente que la recherche linéaire (pour la distance 32, elle passerait par 2 nombres ³² ). Mais pour la distance 9, il mène toujours facilement.

J'ai également modifié les tests de Dietrich. 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 tours avec des requêtes 1, 2, 4, 8, 16, etc., jusqu'à ce qu'au moins 10 secondes aient passé au total). C'est assez stable, j'obtiens même des nombres similaires pendant seulement 1 seconde.

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

Une mise en garde: les résultats de ma requête contiennent des nombres une seule fois, donc si la liste d'entrée contient des nombres en double, cela peut ou non être souhaité. Dans le cas de l'auteur de la question Eric, il n'y avait pas de doublons (voir commentaire ci-dessous). Dans tous les cas, cette solution pourrait être bonne pour les personnes qui n'ont pas de doublons dans l'entrée ou qui ne veulent pas ou n'ont pas besoin de doublons dans les résultats de la requête (je pense qu'il est probable que les résultats de la requête pure ne soient qu'un moyen pour une fin, puis un autre code transforme les nombres en autre chose, par exemple une carte mappant un nombre à une liste de fichiers dont le hachage est ce nombre).

Answer 3

Une approche courante (au moins commune à moi) consiste à diviser votre chaîne de bits en plusieurs morceaux et à effectuer une requête sur ces morceaux pour une correspondance exacte comme étape de pré-filtrage. Si vous travaillez avec des fichiers, vous créez autant de fichiers que vous avez de morceaux (par exemple 4 ici) avec chaque morceau permuté à l'avant, puis triez les fichiers. Vous pouvez utiliser une recherche binaire et vous pouvez même élargir votre recherche au-dessus et en dessous d'un morceau correspondant pour le bonus.

Vous pouvez ensuite effectuer un calcul de distance de martelage au niveau du bit sur les résultats renvoyés qui ne devraient être qu'un sous-ensemble plus petit de votre ensemble de données global. Cela peut être fait à l'aide de fichiers de données ou de tables SQL.

Pour récapituler: disons que vous avez un groupe de chaînes de 32 bits dans une base de données ou des fichiers et que vous voulez trouver chaque hachage qui se trouve à moins de 3 bits de votre chaîne de bits de "requête": >

1. créer une table avec quatre colonnes: chacune contiendra une tranche de 8 bits (sous forme de chaîne ou int) des hachages 32 bits, tranche 1 à 4. Ou si vous utilisez des fichiers, créez quatre fichiers, chacun étant une permutation des tranches ayant une "islice" à l'avant de chaque "ligne"

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

3. interrogez cette table de telle sorte que l'un des qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4. Cela vous donne toutes les chaînes situées à moins de 7 bits (8 - 1) de la chaîne de requête. Si vous utilisez un fichier, effectuez une recherche binaire 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 martelage exacte par paire avec votre chaîne de bits de requête (en reconstruisant les chaînes de bits côté index à partir des quatre tranches à partir de la base de données ou d'un fichier permuté)

Le nombre d'opérations à l'étape 4 devrait être bien inférieur à un calcul complet de martelage par paires de toute votre table et est très efficace en pratique. De plus, il est facile de fragmenter les fichiers dans des fichiers plus petits pour plus de vitesse en utilisant le parallélisme.

Maintenant, bien sûr, dans votre cas, vous recherchez une sorte d'auto-jointure, 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 étendre de haut en bas à partir d'un point de départ pour les permutations (à l'aide de fichiers ou de listes) qui partagent le morceau de départ et de calculer la distance de martelage pour le cluster résultant.

Si vous exécutez en mémoire au lieu de fichiers, votre ensemble de données de chaînes 100M 32 bits serait de l'ordre de 4 Go. Par conséquent, les quatre listes permutées peuvent nécessiter environ 16 Go + de RAM. Même si j'obtiens d'excellents résultats avec des fichiers mappés en mémoire à la place et que je dois moins de RAM pour des ensembles de données de taille similaire.

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

Cette approche à distance heurtée bornée a été décrite pour la première fois en AFAIK par Moses Charikar dans son "simhash" article et le document Google correspondant brevet :

5. RECHERCHE APPROXIMATIVE DU VOISIN LE PLUS PROCHE DANS L'ESPACE DE MARTE

[...]

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

Pour chaque permutation σ, nous effectuons une recherche binaire sur O σ pour localiser le deux vecteurs de bits les plus proches de q (dans l'ordre lexicographique obtenu par bits par

assourdie par σ). Nous recherchons maintenant dans chacun des les ordres triés O σ examinant les éléments ci-dessus et ci-dessous la position retournée par la recherche binaire dans l'ordre du longueur du plus long préfixe correspondant à q.

Monika Henziger a développé ce sujet dans son article " Recherche de 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 non- chevauchant des morceaux de 4 octets, créant des morceaux de 20B et calculant la similitude C de toutes les pages qui avaient au moins un pièce en commun. Cette approche est garantie de trouver tous paires de pages avec une différence jusqu'à 11, c'est-à-dire C-similarité 373, mais pourrait en manquer pour des différences plus importantes.

Ceci est également expliqué dans l'article Détection des quasi-doublons pour l'exploration Web par Gurmeet Singh Manku, Arvind Jain et Anish Das Sarma:

3. LE PROBLÈME DE DISTANCE DE HAMMING

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

[...]

Intuition: considérons un tableau trié d'empreintes digitales vraiment aléatoires sur 2 d f bits. Concentrez-vous uniquement sur les bits d les plus significatifs dans la table. Une liste de ces nombres d-bit équivaut à «Presque un compteur» dans le sens où (a) un certain nombre de bits 2d- il existe des combinaisons, et (b) très peu de combinaisons d bits sont dupliqué. En revanche, le f - d le moins significatif les bits sont «presque aléatoires».

Choisissez maintenant d tel que | d - d | est un petit entier. Puisque la table est triée, une seule sonde suffit pour identifier toutes les empreintes digitales qui correspondent à F dans les d positions binaires les plus significatives. Puisque | d - d | est petit, le nombre de ces correspondances est également devrait être petit. Pour chaque empreinte digitale correspondante, nous pouvons déterminer facilement s'il diffère de F dans la plupart des k positions binaires ou non (ces différences se limiteraient naturellement à f - d positions binaires les moins significatives).

La procédure décrite ci-dessus nous aide à localiser un empreinte digitale qui diffère de F en k positions binaires, toutes sont limités à être parmi les bits f - d les moins significatifs de F. Cela prend en charge un bon nombre de cas. Pour couvrir tout les cas, il suffit de construire un petit nombre de tableaux triés, comme indiqué formellement dans la section suivante.

Remarque: J'ai publié une réponse similaire à une question relative à la base de données uniquement

Answer 4

You could pre-compute every possible variation of your original list within the specified hamming distance, and store it in a bloom filter. This gives you a fast "NO" but not necessarily a clear answer about "YES."

For YES, store a list of all the original values associated with each position in the bloom filter, and go through them one at a time. Optimize the size of your bloom filter for speed / memory trade-offs.

Not sure if it all works exactly, but seems like a good approach if you've got runtime RAM to burn and are willing to spend a very long time in pre-computation.

Answer 5

How about sorting the list and then doing a binary search in that sorted list on the different possible values within you Hamming Distance?

Answer 6

One possible approach to solve this problem is using a Disjoint-set data structure. The idea is merge list members with Hamming distance <= k in the same set. Here is the outline of the algorithm:

• For each list member calculate every possible value with Hamming distance <= k. For k=1, there are 32 values (for 32-bit values). For k=2, 32 + 32*31/2 values.

  • For each calculated value, test if it is in the original input. You can use an array with size 2^32 or a hash map to do this check.

  • If the value is in the original input, do a "union" operation with the list member.

  • Keep the number of union operations executed in a variable.

You start the algorithm with N disjoint sets (where N is the number of elements in the input). Each time you execute an union operation, you decrease by 1 the number of disjoint sets. When the algorithm terminates, the disjoint-set data structure will have all the values with Hamming distance <= k grouped in disjoint sets. This disjoint-set data structure can be calculated in almost linear time.