Trouvez rapidement les chaînes binaires, avec une faible distance de Hamming dans le grand ensemble
Problème:
Donné 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 La Distance De Hamming, 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.
- Comment à propos de la mutation de l'critères attendus de hamming distance, de façon récurrente fonction peut le faire. La prochaine étape sera d'obtenir l'union de deux personnes de la liste?.
- Voici un article récent sur ce problème: Grande échelle de Hamming distance le traitement de la requête.
- Vous avez dit "Pour un maximum de Distance de Hamming de 1 (les valeurs sont en général sera assez faible)". Pouvez-vous dire ce "tout petit" signifiait?
- Aussi, ont été les ~100 millions de numéros uniques, ou il ya des doublons?
- Il n'y a pas de doublons. La plus grande distance de l'intérêt serait 4-5.
Vous devez vous connecter pour publier un commentaire.
Question: Que savons-nous à propos de la distance de Hamming d(x,y)?
Réponse:
Question: Pourquoi faisons-nous des soins?
Réponse:, Car cela signifie que la distance de Hamming est un métrique pour un espace métrique. Il existe des algorithmes pour l'indexation des espaces métriques.
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:
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 surpasser la GCC est
__builtin_popcount
d'environ 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.
Dans votre commentaire, vous avez mentionné:
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.
J'ai écrit à une solution où je représente l'entrée de chiffres dans un bitset de 232 bits, afin que je puisse vérifier en O(1) si un certain nombre est dans l'entrée. Alors, pour un interrogée nombre et de la distance maximale, je récursive de générer tous les nombres à l'intérieur de cette distance et de les vérifier à l'encontre de la bitset.
Par exemple, pour une distance maximale de 5, c'est 242825 numéros (sommed = 0 à 5 {32 choisissez d}). Pour comparaison, Dietrich Ppe VP-arbre solution par exemple passe par 22% des 100 millions de numéros, c'est à dire, par le biais de 22 millions de numéros.
J'ai utilisé de Dietrich code/solutions comme base pour ajouter ma solution et de le comparer avec le sien. Voici les vitesses, dans les requêtes par seconde, pour un maximum de distances jusqu'à 10:
Pour les petites distances, le bitset solution est de loin le plus rapide des quatre. La Question de l'auteur Eric a commenté ci-dessous, que la plus grande distance de l'intérêt serait probablement 4-5. Naturellement, mon bitset solution devient plus lent pour les grandes distances, même plus lent que la recherche linéaire (pour la distance de 32, ce serait aller à travers 232 numéros). Mais pour la distance 9-il encore conduit facilement.
J'ai aussi modifié de Dietrich tests. Chacun des résultats ci-dessus est pour permettre à l'algorithme de résoudre au moins trois requêtes et autant de requêtes qu'il peut en environ 15 secondes (ce que je fais avec des rondes de 1, 2, 4, 8, 16, etc requêtes, jusqu'à au moins 10 secondes au total). C'est assez stable, j'ai même obtenir des chiffres similaires pour seulement 1 seconde.
Mon CPU est un core i7-6700. Mon code (basé sur de Dietrich) est ici (ignorer la documentation au moins pour l'instant, vous ne savez pas quoi faire à ce sujet, mais la
tree.c
contient tout le code et montest.bat
montre comment j'ai compilé et exécuté (j'ai utilisé les indicateurs à partir de DietrichMakefile
)). Raccourci vers ma solution.Une mise en garde: Mon les résultats de la requête contiennent des nombres qu'une seule fois, de sorte que si l'entrée de la liste contient les numéros en double, qui peut ou peut ne pas être désirée. Dans la question de l'auteur Éric cas, il n'y avait pas de doublons (voir commentaire ci-dessous). Dans tous les cas, cette solution pourrait être bon pour les gens qui ont pas de doublons dans l'entrée ou ne voulez pas ou besoin de doublons dans les résultats de la requête (je pense qu'il est probable que la pure résultats de la requête sont seulement un moyen pour une fin, et puis un autre code devient l'un des numéros en autre chose, par exemple une carte de la cartographie d'un nombre à une liste de fichiers dont la valeur de hachage est un nombre).
Une approche commune (au moins pour moi) est de diviser votre chaîne de bits en plusieurs morceaux et de l'interroger sur ces morceaux exact d'un match de pré-filtre de l'étape. Si vous travaillez avec des fichiers, vous devez créer autant de fichiers que vous avez des morceaux (par exemple, 4 ici) avec chaque morceau permutées en avant et puis trier les fichiers. Vous pouvez utiliser une recherche binaire et vous pouvez même étendre votre recherche ci-dessus et ci-dessous un morceau correspondant pour les bonus.
Vous pouvez alors effectuer une opération de bits de hamming distance de calcul sur les résultats retournés qui devrait être seulement un petit sous-ensemble de l'ensemble de votre jeu de données. Cela peut être fait à l'aide de fichiers de données ou des tables SQL.
Donc pour résumer: vous avez un tas de 32 bits de chaînes de caractères dans une base de données ou des fichiers et que vous voulez trouver toutes les hachage qui sont dans les 3 bits de hamming distance ou moins de votre "requête" chaîne de bits:
créer un tableau avec quatre colonnes: chaque contiendra un 8 bits (comme un string ou int) tranche de la 32 bits de tables de hachage, islice 1 à 4. Ou si vous utilisez des fichiers, créer des quatre fichiers, chacun étant une permutation des tranches d'avoir un "islice" à l'avant de chaque "ligne"
tranche de votre requête chaîne de bits de la même manière dans qslice 1 à 4.
requête de ce tableau de manière à ce que l'un de
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, faire une recherche binaire dans chacune des quatre permutées fichiers pour les mêmes résultats.pour chaque retourné chaîne de bits, et le calcul exact de la distance de hamming de paire avec vous interrogez chaîne de bits (la reconstruction de l'index du côté des chaînes de bits de quatre tranches, soit à partir de la DB ou à partir d'une permutation de fichier)
Le nombre d'opérations à l'étape 4 devrait être beaucoup moins qu'une paire de hamming calcul de l'ensemble de votre table et est très efficace dans la pratique.
En outre, il est facile de fragment de fichiers dans des fichiers plus petits, comme le besoin de plus de vitesse à l'aide du parallélisme.
Maintenant, bien sûr, dans votre cas, vous êtes à la recherche d'une auto-jointure de sorte que toutes les valeurs qui sont à une certaine distance les uns des autres. La même approche fonctionne toujours à mon humble avis, mais vous aurez à développer et vers le bas à partir d'un point de départ pour les permutations (à l'aide de fichiers ou listes) qui se partagent le départ morceau et de calculer la distance de hamming pour la suite de la grappe.
Si en cours d'exécution dans la mémoire de fichiers, vos 100M 32 bits chaînes jeu de données dans la plage de 4 GO. D'où les quatre permutées listes peuvent avoir besoin de 16GO+ de RAM. Si j'obtiens d'excellents résultats avec les fichiers mappés en mémoire à la place, et encore moins de RAM pour les ensembles de données de taille similaire.
Il y a des implémentations open source disponibles. Le meilleur dans l'espace est à mon humble avis le seul fait pour Simhash par Moz, C++, mais conçu pour 64 bits de chaînes de caractères et non 32 bits.
Ce délimitée happing distance d'approche a été décrite pour la première autant que je sache, par Moïse Charikar dans son "simhash" séminal papier et le correspondant Google brevet:
Monika Henziger étendu sur ce sujet dans son livre "Trouver près de dupliquer des pages web: une évaluation à grande échelle des algorithmes":
C'est aussi expliqué dans le papier La détection quasi-Doublons pour l'analyse Web par Gurmeet Singh Manku, Arvind Jain, et Anish Das Sarma:
Note: j'ai posté une réponse similaire à un liées DB seule question
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.
Ne sais 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.
Comment sur le tri de la liste et ensuite de faire une recherche binaire dans cette liste triée sur les différentes valeurs possibles à l'intérieur de vous Hamming Distance?
Une approche possible pour résoudre ce problème est d'utiliser un Disjoint-définir la structure de données. L'idée est de fusionner les membres de la liste avec la distance de Hamming <= k dans le même ensemble. Ici, le contour de l'algorithme:
Pour chaque membre de la liste de calculer chaque valeur avec la distance de Hamming <= k. Pour k=1, il y a 32 valeurs (pour des valeurs de 32 bits). Pour k=2, 32 + 32*31/2 des valeurs.
Pour chaque calculé valeur, le test, il est dans l'entrée d'origine. Vous pouvez utiliser un tableau de taille 2^32 ou d'un hachage de la carte pour faire cette vérification.
Si le valeur est dans l'entrée d'origine, faire un "syndicat" de l'opération avec le membre de la liste de.
Vous démarrez 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 union, vous diminuez de 1 le nombre d'ensembles disjoints. Lorsque l'algorithme se termine, le disjoints-définir la structure de données aurez toutes les valeurs avec la distance de Hamming <= k regroupés dans des ensembles disjoints. Cette disjoints-définir la structure de données peut être calculé en presque, le temps linéaire.