funkcje generatora funkcji skrótu w pytonie

Question

Poszukuję generatora funkcji funkcji skrótu, który może generować rodzinę funkcji mieszających, biorąc pod uwagę zestaw parametrów. Nie znalazłem dotąd żadnego takiego generatora. Czy można to zrobić z pakietem hashlib?

Na przykład chciałbym zrobić coś takiego:

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

i h1 i h2 byłyby różne funkcje hash.

Dla tych z Państwa, którzy mogą o tym wiedzieć, próbuję wprowadzić algorytm min-haszowania na bardzo dużym zbiorze danych.

Zasadniczo mam bardzo duży zestaw funkcji (od 100 milionów do 1 miliarda) dla danego dokumentu i muszę utworzyć od 1000 do 10000 różnych losowych permutacji dla tego zestawu funkcji.

nie chcę budować losowych permutacji wyraźnie więc technika chciałbym używać w następujących przypadkach:

1. generowania funkcji skrótu h i uważają, że dla dwóch wskaźników r i s
2. r pojawia się przed s w permutacji, jeśli h(r) < h(s) i zrobić to dla 100 do 1000 różnych funkcji skrótu.

Czy są jakieś znane biblioteki, które mogłem pominąć? Lub jakikolwiek standardowy sposób generowania rodzin funkcji skrótu z pythoniem, o którym być może wiesz?

Answer 1

Chciałbym po prostu zrobić coś jak (jeśli nie trzeba wątku bezpieczeństwa - nie trudno zmienić, jeśli potrzebują bezpieczeństwa wątku - i zakładając 32-bitowej wersji Pythona):

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

Powinieneś rozważyć użycie uniwersalnego skrótu. Moja odpowiedź i kod można znaleźć tutaj: https://stackoverflow.com/a/25104050/207661

Answer 3

Jak wspomniano powyżej, możesz użyć uniwersalnego skrótu do minhash. Na przykład:

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