hash fonctions générateur de famille en python

Question

Je cherche un générateur de famille de fonctions de hachage qui pourrait générer une famille de fonctions de hachage étant donné 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 package hashlib?

Par exemple, je voudrais faire quelque chose comme:

h1 = hash_function(1) 
h2 = hash_function(2) 
... 

et h1 et h2 seraient différentes fonctions de hachage. Pour ceux d'entre vous qui pourraient le savoir, j'essaie d'implémenter un algorithme de min-hachage sur un ensemble de données très volumineux. Fondamentalement, j'ai un très grand ensemble de fonctionnalités (100 millions à 1 milliard) pour un document donné, et j'ai besoin de 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 la technique que je souhaite utiliser dans les domaines suivants:

1. générer une fonction de hachage h et considérer que, pour deux indices r et s
2. r apparaît avant s dans la permutation si h(r) < h(s) et le faire pour 100 à 1000 fonctions de hachage différentes.

Y a-t-il des bibliothèques connues que j'ai pu manquer? Ou n'importe quel moyen standard de générer des familles de fonctions de hachage avec python que vous pourriez être au courant?

Answer 1

je venais de faire quelque chose comme (si vous n'avez pas besoin de fil de sécurité - pas difficile de 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 

Answer 2

Vous devriez envisager d'utiliser un hachage universel. Ma réponse et le code peuvent être trouvés ici: https://stackoverflow.com/a/25104050/207661

Answer 3

Comme mentionné ci-dessus, vous pouvez utiliser le hachage universel pour minhash. Par exemple:

import random 



def minhash(): 
    d1 = set(random.randint(0, 2000) for _ in range(1000)) 
    d2 = set(random.randint(0, 2000) for _ in range(1000)) 
    jacc_sim = len(d1.intersection(d2))/len(d1.union(d2)) 
    print("jaccard similarity: {}".format(jacc_sim)) 

    N_HASHES = 200 
    hash_funcs = [] 
    for i in range(N_HASHES): 
     hash_funcs.append(universal_hashing()) 

    m1 = [min([h(e) for e in d1]) for h in hash_funcs] 
    m2 = [min([h(e) for e in d2]) for h in hash_funcs] 
    minhash_sim = sum(int(m1[i] == m2[i]) for i in range(N_HASHES))/N_HASHES 
    print("min-hash similarity: {}".format(minhash_sim)) 



def universal_hashing(): 
    def rand_prime(): 
     while True: 
      p = random.randrange(2 ** 32, 2 ** 34, 2) 
      if all(p % n != 0 for n in range(3, int((p ** 0.5) + 1), 2)): 
       return p 
    m = 2 ** 32 - 1 
    p = rand_prime() 
    a = random.randint(0, p) 
    if a % 2 == 0: 
     a += 1 
    b = random.randint(0, p) 
    def h(x): 
     return ((a * x + b) % p) % m 
    return h 

Reference