Trouver toutes les paires de valeurs proches sous la distance de Hamming

J'ai quelques millions de valeurs 32 bits. Pour chaque valeur, je veux trouver toutes les autres valeurs dans une distance de 5 brouillage. Dans l'approche naïve, cela nécessite des comparaisons $O(N^2)$ , que je veux éviter.

J'ai réalisé que si je traitais simplement ces valeurs 32 bits comme des entiers et triais la liste une fois, alors les valeurs qui ne différaient que dans les bits les moins significatifs se retrouvaient très proches les unes des autres. Cela me permet d'avoir une "fenêtre" ou une plage de nombres plus courte à l'intérieur de laquelle je peux effectuer des comparaisons par paires réelles pour la distance exacte de brouillage. Cependant, lorsque 2 valeurs varient uniquement dans les bits d'ordre supérieur, elles se retrouvent en dehors de cette "fenêtre" et apparaissent aux extrémités opposées de la liste triée. Par exemple

11010010101001110001111001010110

01010010101001110001111001010110

serait très éloigné, même si leur distance de hamming est 1. Puisque, la distance de hamming entre 2 valeurs est préservée lorsque les deux sont tournées, je me suis dit qu'en faisant 32 rotations à gauche puis en triant la liste à chaque fois, il est probable que 2 valeurs finira assez près dans la liste triée dans au moins l'un d'entre eux.

1. Bien que cette approche me donne de bons résultats, j'ai du mal à établir officiellement l'exactitude de cette approche.

2. Étant donné que je recherche des valeurs correspondantes ayant une distance de brouillage $k$ ou moins, ai-je vraiment besoin de faire toutes les rotations 32 bits? Par exemple, si $k=1$ et que la taille de ma fenêtre est de 1000, je dois le faire à des rotations de 24 bits maximum car même si le bit errant est apparu dans l'un des 8 bits d'ordre inférieur, les nombres résultants ne différeront pas de plus de 1000.

Comme indiqué, votre approche est problématique, car si 2 bitmaps ont des différences régulièrement espacées, alors dans toute rotation, il y aura des différences sur certains bits de poids fort.

$5$$1/50$$64\cdot N$$N\approx 2^{22}$

$4$$5$$529\cdot N$$4960\cdot N$

Information additionnelle:

1. $5$$16$$32$ $$\frac{\binom{16}{5}}{\binom{32}{5}}\approx 0.0217$$
2. Construction des listes, pour chaque élément de la liste d'origine, mis dans la liste augmentée: l'élément lui-même, tous les éléments différant dans une position et tous les éléments différant dans deux positions (en conservant les informations sur l'élément d'origine). Le nombre de copies pour chaque élément estToute collision à l'intérieur de cette liste (détectée après tri) correspond à deux éléments d'origine à distance au plus . Notez que chaque paire peut être détectée plusieurs fois, vous devrez donc supprimer les doublons (mais c'était déjà le cas avec votre algorithme initial).$1+32+\binom{32}{2}=529.$$4$
3. Pour la passe finale, il est préférable d'élaguer la liste augmentée des éléments pour ne garder que ceux à la distance exacte de leur élément d'origine. Ensuite, pour chaque élément d'origine, créez les éléments à la distance et recherchez-les dans la liste augmentée. Encore une fois, vous devez supprimer les doublons car chaque paire va être détectée fois. [Avec un soin supplémentaire, vous pouvez probablement anticiper / éviter la plupart des doublons, mais je ne sais pas si cela en vaut la peine.]$2$$\binom{32}{3}=4960$$3$$\binom{5}{3}=10$

La réponse de minar est excellente et est probablement la bonne approche pour ce problème particulier. Cependant, je mentionnerai une autre approche possible:

Vous pouvez utiliser une fonction de hachage sensible à la localité (LSH). Une fonction de hachage sensible à la localité est conçue de telle sorte que si sont proches dans la distance de Hamming, alors . Si vous avez un tel hachage , vous pouvez stocker toutes vos valeurs dans une table de hachage (en utilisant la fonction de hachage et le hachage ouvert), puis vous pourrez très rapidement trouver toutes les paires de valeurs proches à distance de Hamming . Il existe différentes techniques pour construire un LSH; vous pouvez consulter les références sur ce sujet pour trouver plusieurs candidats.$H$$x,y$$H(x)=H(y)$$H$$H$

Cela dit, pour votre problème particulier (avec les paramètres spécifiques que vous avez mentionnés), je m'attends à ce que les deux algorithmes de minar se révèlent meilleurs en pratique que n'importe quel schéma basé sur LSH. Je mentionne cela uniquement au cas où d'autres lecteurs viendraient ici à cette question avec un problème similaire, mais avec des paramètres différents où LSH pourrait avoir plus de sens.