Je cherche un générateur de famille de fonctions de hachage qui pourrait générer une famille de fonctions de hachage fournies à un ensemble de paramètres. Je n'ai trouvé aucun générateur de ce type jusqu'à présent.
Existe-t-il un moyen de le faire avec le paquet Par exemple, je voudrais faire quelque chose comme: et < code> H1 et Pour ceux d'entre vous qui en savoir plus, j'essaie de mettre en œuvre un algorithme de hachage min-hachage Un très grand jeu de données. Fondamentalement, j'ai un très grand ensemble de caractéristiques (100 millions à 1 milliard) pour un document donné et je dois créer 1000 à 10000 permutations aléatoires différentes pour cet ensemble de fonctionnalités. . Je ne veux pas construire les permutations aléatoires explicitement, donc la technique que je voudrais utiliser dans ce qui suit: Y a-t-il des bibliothèques connues que j'aurais pu manquer? Ou toute façon standard de générer des familles de fonctions de hachage avec Python que vous pourriez être au courant? hashlib H2 serait des fonctions de hachage différentes.
h et considérez que pour deux indices r et s
r apparaît avant s dans la permutation si h (r)
5 Réponses :
Je ferais juste quelque chose comme (si vous n'avez pas besoin de la sécurité thread-sécurité - pas difficile à modifier si vous avez besoin de sécurité de fil - et en supposant une version Python 32 bits):
import random
_memomask = {}
def hash_function(n):
mask = _memomask.get(n)
if mask is None:
random.seed(n)
mask = _memomask[n] = random.getrandbits(32)
def myhash(x):
return hash(x) ^ mask
return myhash
Merci pour cette réponse. Cela semble fonctionner très bien. Tout particulier à utiliser ces types de fonctions de hachage? Efficacité ? donnera des permutations approximatives très différentes dans un sens?
L'intégré hachage est décent et assez efficace - Xor'ing-le avec un nombre en fonction (mais de manière suffisamment chaotique) de l'indice de la famille semble simplement une autre façon correcte / efficace de tourner cette fonction de hachage dans une famille. Si la vitesse n'est pas un problème, vous pouvez utiliser une hachage plus forte (crypto-qualité), je suppose - qui vous donnera probablement une qualité supérieure (ni hachage ni aléatoire sont la qualité de la crypto et ne sont donc ni leur xor ;-) mais l'impact de la vitesse est vraiment Grand (ordres de magnitude ...).
Merci. En fait, je crois que la vitesse sera la clé pour moi ici. La seule "qualité" que je recherche est que les fonctions de hachage généreront des permutations aléatoires "comme différentes" que possible (je ne sais pas comment quantifier cela si ...) par le processus que j'ai décrit dans ma question initiale. Encore une fois, merci beaucoup pour votre grande réponse.
Cela ne fonctionne pas et est un très mauvais choix pour presque toutes les utilisations de familles de hachage. Si vous avez l'intention d'utiliser ceci pour les tables de hachage où vous recherchez plusieurs emplacements basés sur des hachages (coucou, hachage à 2 voies, etc.) alors c'est un extrêmement mauvais choix et pas différent de l'utilisation d'une seule fonction . L'ensemble du point d'utilisation de différentes fonctions de hachage est qu'un motif de collision différent se produira, lorsque vous XOR sur la sortie de votre hachage avec une constante, il ne modifie pas du tout les collisions, les mêmes clés qui entrent en collision de l'une.
Vous devriez envisager d'utiliser un hachage universel. Ma réponse et mon code peuvent être trouvés ici: https://stackoverflow.com/a/25104050/207661
Comme mentionné ci-dessus, vous pouvez utiliser un hachage universel pour Minhash.
Par exemple:
Essayé de modifier votre réponse, mais cela devait être plus de 6 caractères. Il y a une erreur de syntaxe, corrigez-la à: 'minhash_sim = somme ([int (m1 [i] == m2 [i]) pour i in gamme (n_hashes)]) / n_hashes'
La réponse de Alex est excellente et concise, mais les fonctions de hachage qu'il génère ne sont pas "très différentes les unes des autres".
Regardons la corrélation Pearson entre 10000 échantillons de 10000 hachages qui placent les résultats dans 100 bacs p> i.e. La médiane p_value est Utilisation de carter et wegman, vous pouvez obtenir: p> code à Reproduire: P> 1e-06 code> qui est loin d'être aléatoire. Voici un exemple s'il était vraiment aléatoire: p>
from scipy.stats.stats import pearsonr
import numpy as np
import random
_memomask = {}
def hash_function(n):
mask = _memomask.get(n)
if mask is None:
random.seed(n)
mask = _memomask[n] = random.getrandbits(32)
def myhash(x):
return hash(x) ^ mask
return myhash
class HashFamily():
r"""Universal hash family as proposed by Carter and Wegman.
.. math::
\begin{array}{ll}
h_{{a,b}}(x)=((ax+b)~{\bmod ~}p)~{\bmod ~}m \ \mid p > m\\
\end{array}
Args:
bins (int): Number of bins to hash to. Better if a prime number.
moduler (int,optional): Temporary hashing. Has to be a prime number.
"""
def __init__(self, bins, moduler=None):
if moduler and moduler <= bins:
raise ValueError("p (moduler) should be >> m (buckets)")
self.bins = bins
self.moduler = moduler if moduler else self._next_prime(np.random.randint(self.bins + 1, 2**32))
# do not allow same a and b, as it could mean shifted hashes
self.sampled_a = set()
self.sampled_b = set()
def _is_prime(self, x):
"""Naive is prime test."""
for i in range(2, int(np.sqrt(x))):
if x % i == 0:
return False
return True
def _next_prime(self, n):
"""Naively gets the next prime larger than n."""
while not self._is_prime(n):
n += 1
return n
def draw_hash(self, a=None, b=None):
"""Draws a single hash function from the family."""
if a is None:
while a is None or a in self.sampled_a:
a = np.random.randint(1, self.moduler - 1)
assert len(self.sampled_a) < self.moduler - 2, "please give a bigger moduler"
self.sampled_a.add(a)
if b is None:
while b is None or b in self.sampled_b:
b = np.random.randint(0, self.moduler - 1)
assert len(self.sampled_b) < self.moduler - 1, "please give a bigger moduler"
self.sampled_b.add(b)
return lambda x: ((a * x + b) % self.moduler) % self.bins
def draw_hashes(self, n, **kwargs):
"""Draws n hash function from the family."""
return [self.draw_hash() for i in range(n)]
def median_pvalue(hashes, buckets=100, n=1000):
p_values = []
for j in range(n-1):
a = [hashes[j](i) % buckets for i in range(n)]
b = [hashes[j+1](i) % buckets for i in range(n)]
p_values.append(pearsonr(a,b)[1])
return np.median(p_values)
Le Famille de hachage universelle est un ensemble de fonctions de hachage en fonction de la formulation de Wikipedia, l'utilisation peut utiliser le code suivant: Exemple d'utilisation: Nous pouvons créer une famille de hachage se compose de 20 fonctions de hachage, chacune de l'entrée à 100 godets. < / p> et obtenir les valeurs hachées telles que: Si vous êtes intéressé par la famille de hachage universelle pour < Strong> String Entrées, vous pouvez utiliser le code suivant. Mais veuillez noter que ce code peut ne pas être la solution optimisée pour le hachage de chaîne. h de taille m , de telle sorte que toutes les entrées de deux (district) entrent en collision avec une probabilité au plus 1 / m lorsque la fonction de hachage h est dessinée au hasard de définir h . 