Hachage de vecteurs binaires clairsemés

Est-ce que quelqu'un a une bonne intuition pour une bonne fonction de hachage pour un vecteur binaire clairsemé? Pour donner un exemple concret, disons que je veux hacher un entier de 4096 bits où la probabilité que chaque bit soit 1 est de 10%.Hachage de vecteurs binaires clairsemés

Je veux obtenir une compression dans le hachage. Par exemple, 4096 bits et 32 bits. Ceci est juste un exemple pour illustrer ce que je cherche. Bien sûr, toutes les réponses sont très appréciées.

Source

2009-03-14 Himadri Choudhury

Veuillez indiquer le type de hachage que vous recherchez. En Java et .NET, les codes de hachage (pour les tables de hachage, etc.) sont des entiers de 32 bits - la réponse évidente serait donc de retourner la valeur d'origine. Je suppose que ce n'est pas ce que vous voulez, alors plus de clarté serait la bienvenue. –

Peut-être que 32 bits était un exemple trop petit. Disons que c'est 1024 bits, ou une autre valeur plus grande. Je veux avoir de la compression. Donc 32 bits -> 32 bits n'est pas ce que je cherche. –

Est-ce qu'un Bloom filter peut aider?

Si le vecteur binaire est de 2^32 bits, pourquoi ne pas utiliser un entier de 32 bits?

Source

2009-03-14 21:42:00

Vous pouvez modifier votre instruction "si le vecteur de bits est 2^32 bits";] –

Intéressant. Avez-vous une idée de ce qu'il faut utiliser pour les fonctions de hachage pour le filtre Bloom? –

Dites pour un entier de 32 bits (selon l'édition originale), vous pourriez avoir un vecteur de taille 2^16 bits, et définir le bit n si l'entier n/(2^16) est défini. Ensuite, si vous voulez savoir si x est dans vos données d'origine, vous savez "oui ou peut-être" (jamais "non") si le bit x/(2^16) est défini. Fonctionne si l'ensemble est clairsemé et cher à rechercher. –

Je voudrais juste les bits de hachage, comme d'habitude en appelant

hash<vector<bool>>(...)

si vous utilisez C++ 0x, ou bien voir boost :: hachage.

Source

2010-04-07 06:31:27

Répondre

Questions connexes