Bonne façon de hacher un vecteur de flotteur?

Question

Je connais bien tous les problèmes liés à la comparaison des flotteurs. C'est exactement la raison de cette question.
Je cherche à créer une table de hachage rapide pour les valeurs qui sont des vecteurs 3D (3 flottants - x, y, z). On peut supposer que la longueur du vecteur est toujours 1.0 (est 1.0)

Essentiellement, cela signifie que je cherche une fonction de hachage qui prend des valeurs qui sont presque égales à la même valeur int non signée et un correspondant opérateur d'égalité qui est vrai si les valeurs de hachage sont égales (non pas nécessairement seulement si elles sont égales)

Modifier -
faux positifs (c.-à-vecteurs qui sont différents, mais tracent le même seau) sont une donnée depuis c'est une table de hachage.
Les faux négatifs (c'est-à-dire les vecteurs rapprochés mais mappés à des godets différents) ne sont pas souhaitables, mais il semble qu'il n'y ait aucun moyen de les éviter. Dans mon cas, ils ne provoqueront pas de bris total, juste une duplication de données qui est quelque chose que je vais devoir vivre avec.

Answer 1

je convertir les valeurs flottantes en entiers comme celui-ci:

unsigned int IntValue = (int)(floatValue * MULT) + MULT; 

si vous obtenez quelques-uns des premiers chiffres, puis utiliser

const MULT1 = (MULT << 1) + 1; 
unsigned long long HashValue = (xIntValue * MULT1 * MULT1) + (yIntValue * MULT1) + zIntValue; 

comme une valeur de hachage (en utilisant (MULT * 2) + 1 car les IntValues ​​seront compris entre 0 et MULT * 2 inclus).

La mémoire nécessaire dépendra du multiplicateur MULT. Par exemple, en utilisant 32, vous obtiendrez une table de hachage en utilisant 64 * 64 * 64 * (Taille de l'élément de hachage) = 262144 * (Taille de l'élément de hachage) octets.

Answer 2

Je pense que ce que vous cherchez n'est pas directement possible. Une propriété importante de l'égalité est qu'elle est transitive. (c'est-à-dire si a == b et b == c, alors a == c). Avec une mesure de distance, cependant, vous ne voulez vraiment pas cette propriété. Exemple:

Prenez un seul flotteur (pour plus de simplicité). Supposons que nous voulions hacher chaque flotteur de sorte que les flottants de moins de 1e-3 soient de même valeur. Maintenant, supposons que nous ajoutons à cette table de hachage 1000 valeurs flottantes toutes séparées par 1e-4. Toutes les valeurs 2 voisines doivent hacher le même flottant, puisqu'elles sont plus proches que 1e-3. Cependant, à cause de la transitivité, les voisins de ces valeurs devraient également avoir la même valeur, et leurs voisins et ainsi de suite. Par conséquent, toutes les 1000 valeurs, y compris les paires distantes de plus de 1e-3, devraient avoir le même nombre entier. Si vous deviez dessiner ces points sur une image:

A B C D E F G H ... Y Z 

Supposons que toutes les lacunes sont < 1E-3 à part, mais A et Z sont> 1E-3 à part (pas à l'échelle!). Cela ne peut pas être satisfait car si hash (A) == hash (B) et hash (B) == hash (C) et ainsi de suite pour toutes les paires, (puisqu'ils sont < 1e-3 apart) que hash (A) doit == hacher (Z). Une option possible consiste à définir des régions de votre espace vectoriel dans lesquelles tous les vecteurs auraient la même valeur (ie les arrondir avant de les hacher), mais vous pouvez toujours obtenir 2 vecteurs sur les bords de leurs espaces respectifs qui sont rapprocher mais hacher à une valeur différente. Vous pouvez contourner cela en recherchant un vecteur dans tous les espaces voisins. (ie dans le cas 1-d ci-dessus, vous arrondissez tous les vecteurs au multiple de 1e-3 le plus proche, puis recherchez les voisins, donc 5.3e-3 cherchera 5e-3, 4e-3 et 6-e3. Dans les cas de dimension supérieure, vous devez rechercher des voisins dans toutes les dimensions.

Answer 3

Certaines langues (C, Java 5) vous permettent d'accéder à la valeur binaire de vos flottants. De cette façon, vous pouvez extraire les N premiers bits de la mantisse (en ignorant les derniers bits qui causent le problème pendant la comparaison) et calculer le hachage à partir de cela.

Answer 4

Pouvez-vous élaguer votre problème? En supposant que vous utilisiez une hashmap pour mapper des données supplémentaires à des vecteurs spécifiques, vous pouvez simplement utiliser le XOR des représentations binaires des composants (si cela est possible dans la langue de votre choix). Utilisez ensuite autant de LSB (pour réduire les collisions) que nécessaire pour la carte de hachage. Cela aurait bien entendu la propriété que deux vecteurs égaux (par comparaison à virgule flottante) pourraient ne pas avoir le même hachage (par exemple, le point flottant IEEE 0 est égal à -0, mais ils ont un bit de signe différent). Toutefois, si vous envisagez d'utiliser des vecteurs résultant de différents calculs pour effectuer une recherche de hachage, vous vous préparez à ne pas avoir de codes de hachage correspondants en raison d'erreurs d'arrondi et vous devriez probablement utiliser autre chose en tous cas.

Answer 5

ne sais pas à quelle vitesse cela pourrait être, mais comme vous avez des vecteurs unitaires, ils se trouvent tous à la surface d'une sphère. convertir en http://en.wikipedia.org/wiki/Spherical_coordinate_system. puis utilisez phi et thêta pour choisir un seau. il n'y aura pas de faux positifs. vous pouvez regarder dans les cellules voisines pour les faux négatifs.

Answer 6

Avez-vous besoin d'une table de hachage rapide ou d'une structure en arbre?

Il me semble qu'il serait plus facile de rechercher des flottants correspondants dans un arbre de recherche de type . Un B-Tree minimise le nombre d'échecs de cache, en supposant que vous choisissez la bonne taille de nœud. Cela devrait le rendre assez rapide dans la pratique.

Answer 7

Je pense que vous essayez effectivement de résoudre le problème K le plus proche. Je crois que ce que vous cherchez est locality sensitive hashing. Vous pouvez également utiliser des structures à quatre arbres pour obtenir le même résultat.