generatore di famiglie di funzioni hash in python

Question

Sto cercando un generatore di famiglie di funzioni hash che possa generare una famiglia di funzioni hash data una serie di parametri. Non ho trovato nessun generatore di questo tipo finora. C'è un modo per farlo con il pacchetto hashlib?

Per esempio mi piacerebbe fare qualcosa di simile:

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

e h1 e h2 sarebbero diverse funzioni di hash.

Per quelli di voi che potrebbero saperlo, sto cercando di implementare un algoritmo min-hashing su un set di dati molto grande.

Fondamentalmente, ho un insieme molto ampio di funzionalità (da 100 milioni a 1 miliardo) per un dato documento, e ho bisogno di creare da 1000 a 10000 permutazioni casuali diverse per questo insieme di funzionalità.

Non voglio costruire le permutazioni casuali esplicitamente così la tecnica che vorrebbe utilizzare il seguente:

1. generare una funzione di hash h e considerare che per due indici r e s
2. r appare prima di s nella permutazione se h(r) < h(s) e farlo per 100 a 1000 diverse funzioni hash.

Esistono librerie note che potrei aver perso? O qualsiasi modo standard di generare famiglie di funzioni di hash con Python di cui potresti essere a conoscenza?

Answer 1

avevo appena fare qualcosa di simile (se non hai bisogno di thread-sicurezza - non è difficile da modificare Se hai bisogno di filo di sicurezza - e assumendo una versione di Python a 32 bit):

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

Si dovrebbe considerare l'utilizzo dell'hash universale. La mia risposta e il mio codice possono essere trovati qui: https://stackoverflow.com/a/25104050/207661

Answer 3

Come detto sopra, è possibile utilizzare l'hashing universale per minhash. Per esempio:

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