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

Question

Problème:

Une grande (~100 m) liste des entiers 32 bits non signés, un entier 32 bits non signé valeur d'entrée, et un maximum de Hamming Distance, le retour de tous les membres de la liste qui sont au sein de la Distance de Hamming de la valeur d'entrée.

Réelle structure de données pour contenir la liste est ouverte, les exigences de performance de dicter une solution de mémoire, le coût pour construire la structure de données est secondaire, à faible coût, à la requête de la structure des 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é de Hamming Distance de 0, il suffit d'utiliser une liste triée et faire une recherche binaire pour la valeur d'entrée.

Si la Distance de Hamming-ci ne serait jamais 1, j'ai pu flip chaque bit de l'entrée d'origine et répétez l'32 fois.

Comment puis-je efficacement (sans la numérisation de l'ensemble de la liste) découvrir les membres de la liste avec une Distance de Hamming > 1.

Answer 1

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

Réponse:

1. Il est non-négative: d(x,y) ≥ 0
2. Elle est nulle pour les mêmes entrées: d(x,y) = 0 ⇔ x = y
3. Elle est symétrique: d(x,y) = d(y,x)
4. Elle obéit, le triangle de l'inégalité, d(x,z) ≤ d(x,y) + d(y,z)

Question: Pourquoi avons-nous des soins?

Réponse: Parce que cela signifie que la distance de Hamming est une métrique d'un espace métrique. Il existe des algorithmes pour l'indexation des espaces métriques.

• Métrique de l'arbre (Wikipedia)
• BK-arbre (Wikipedia)
• M-arbre (Wikipedia)
• VP-arbre (Wikipedia)
• La couverture de l'arbre (Wikipedia)

Vous pouvez également rechercher des algorithmes pour "indexation spatiale" en général, armé avec la connaissance que votre espace n'est pas Euclidien mais il est un espace métrique. De nombreux livres sur ce sujet couvercle de la chaîne de l'indexation à l'aide d'une métrique telle que la distance de Hamming.

Note de bas de page: Si vous comparez la distance de Hamming de longueur fixe chaînes, vous pouvez être en mesure d'obtenir une amélioration significative de la performance en utilisant de l'assemblée ou du processeur intrinsèques. Par exemple, avec GCC (manuel) pour ce faire:

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

Si vous informera alors de GCC que vous compilation pour un ordinateur avec SSE4a, alors je pense que cela doit réduire à seulement quelques opcodes.

Edit: Selon un certain nombre de sources, c'est parfois/souvent plus lent que d'habitude le masque/shift/add code. L'analyse comparative montre que sur mon système, une version en C surperformer est du CCG __builtin_popcount environ de 160%.

Addendum: j'étais curieux de connaître le problème moi-même, donc je profilé trois implémentations: recherche linéaire, BK arbre, et vice-président de l'arbre. Notez que VP et BK arbres sont très similaires. Les enfants d'un nœud dans un arbre BK sont des "coquilles" d'arbres contenant des points qui sont à une distance fixe de l'arbre du centre. Un nœud dans un VP arbre a deux enfants, l'un contenant tous les points à l'intérieur d'une sphère centrée sur le nœud du centre et de l'autre enfant contenant tous les points de l'extérieur. Si vous pouvez penser à un VP nœud comme un BK nœud avec deux très épais "coquilles" au lieu de beaucoup plus fin.

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

• Base de données: 100M pseudo-aléatoires entiers
• Nombre de tests: 1000 pour une distance de 1..5, 100 pour une distance de 6..10 et linéaire
• Résultats: Moyenne nombre de requête de frappe (très approximative)
• Vitesse: Nombre de requêtes par seconde
• Couverture: pourcentage Moyen de la base de données examinées par requête

 -- BK Arbre -- -- VP Arbre -- -- Linéaire --
Dist Résultats De La Vitesse De Cov Vitesse De Cov Vitesse De Cov
1 0.90 3800 0.048% 4200 0.048%
2 11 300 0.68% 330 0.65%
3 130 56 de 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 91 2.3% 2.4 90%
toute 2.2 100%

Dans votre commentaire, vous avez mentionné:

Je pense que BK-arbres pourrait être améliorée par la génération d'un tas de BK-arbres avec différents nœuds racine, et leur diffusion.

Je pense que c'est exactement la raison pour laquelle le vice-président arbre effectue (un peu) mieux que le BK arbre. Être "plus en profondeur" plutôt que de "profondes", il compare contre plus de points plutôt que d'utiliser des grains plus fins de comparaison moins de points. Je soupçonne que les différences sont de plus en plus extrêmes, en plus des espaces de dimension.

Un dernier conseil: les nœuds feuilles de l'arbre devrait être à plat les tableaux d'entiers pour une analyse linéaire. Pour de petits ensembles (peut-être 1000 points ou moins) ce sera plus rapide et plus efficace en terme de mémoire.

Answer 2

Vous pourriez pré-calculer toutes les variations possibles de votre liste d'origine au sein de la distance de hamming, et de le stocker dans un filtre de bloom. Cela vous donne un rapide "NON", mais pas nécessairement une réponse claire sur "OUI".

Pour OUI, de stocker une liste de toutes les valeurs d'origine associé à chaque position dans la fleur de filtre, et de les parcourir une à la fois. Optimiser la taille de votre filtre de bloom pour la vitesse de la mémoire et du compromis.

Vous ne savez pas si tout cela fonctionne exactement, mais semble être une bonne approche si vous avez de l'exécution de la RAM à brûler et sont prêts à dépenser beaucoup de temps dans la pré-calcul.

Answer 3

Pourquoi ne pas trier la liste puis faire une recherche binaire dans cette liste triée sur les différentes valeurs possibles dans votre Distance de Hamming?