Czy istnieje czysta wersja Pythona z MurmurHash?

Question

Potrzebuję (i nie mogę znaleźć) implementacji czystego Pythona (bez C++) z MurmurHash i jestem zbyt początkujący, aby samemu pisać. Prędkość lub wykorzystanie pamięci nie ma znaczenia w moim projekcie.

Znajduje się próba here, ale jest ograniczona do hasza 31-bitowego i naprawdę potrzebuję skrótu 64-bitowego.

Uwaga: dla tych, którzy potrzebują szybkiej realizacji, istnieje biblioteka MurmurHash2 here i biblioteka MurmurHash3 here

Answer 1

Innym czysta implementacja Pythona z MurmurHash3 że jest całkowicie kompatybilne i wymienialne przez owinięcie mmh3, ale nadal ograniczona do 32-bitów Murmur3: https://github.com/wc-duck/pymmh3

Answer 2

to niesprawdzone (przepraszam!), Ale tutaj jest to wersja wymyśliłem. Python pozwala na dowolnie duże liczby całkowite, dlatego utworzyłem maskę dla pierwszych 8 bajtów (lub 64 bitów), które następnie stosuję (za pomocą bitowego AND) do wszystkich wyników arytmetycznych, które mogą tworzyć liczby całkowite większe od 64bits. Może ktoś inny mógłby wypowiedzieć się na temat ogólnego podejścia i ewentualnych problemów z endianness itp

def bytes_to_long(bytes): 
    assert len(bytes) == 8 
    return sum((b << (k * 8) for k, b in enumerate(bytes))) 


def murmur(data, seed): 

    m = 0xc6a4a7935bd1e995 
    r = 47 

    MASK = 2 ** 64 - 1 

    data_as_bytes = bytearray(data) 

    h = seed^((m * len(data_as_bytes)) & MASK) 

    for ll in range(0, len(data_as_bytes), 8): 
     k = bytes_to_long(data_as_bytes[ll:ll + 8]) 
     k = (k * m) & MASK 
     k = k^((k >> r) & MASK) 
     k = (k * m) & MASK 
     h = (h^k) 
     h = (h * m) & MASK 

    l = len(data_as_bytes) & 7 

    if l >= 7: 
     h = (h^(data_as_bytes[6] << 48)) 

    if l >= 6: 
     h = (h^(data_as_bytes[5] << 40)) 

    if l >= 5: 
     h = (h^(data_as_bytes[4] << 32)) 

    if l >= 4: 
     h = (h^(data_as_bytes[3] << 24)) 

    if l >= 3: 
     h = (h^(data_as_bytes[4] << 16)) 

    if l >= 2: 
     h = (h^(data_as_bytes[4] << 8)) 

    if l >= 1: 
     h = (h^data_as_bytes[4]) 
     h = (h * m) & MASK 

    h = h^((h >> r) & MASK) 
    h = (h * m) & MASK 
    h = h^((h >> r) & MASK) 

    return h 

Answer 3

Tu idzie czystego wdrożenie Pythona z MurmurHash3 32, sieka tylko struny, ale może być łatwo dostosowany do podjęcia tablicami bajtów zamiast. Jest to port z algorytmu Java version.

def murmur3_x86_32(data, seed = 0): 
    c1 = 0xcc9e2d51 
    c2 = 0x1b873593 

    length = len(data) 
    h1 = seed 
    roundedEnd = (length & 0xfffffffc) # round down to 4 byte block 
    for i in range(0, roundedEnd, 4): 
     # little endian load order 
     k1 = (ord(data[i]) & 0xff) | ((ord(data[i + 1]) & 0xff) << 8) | \ 
      ((ord(data[i + 2]) & 0xff) << 16) | (ord(data[i + 3]) << 24) 
     k1 *= c1 
     k1 = (k1 << 15) | ((k1 & 0xffffffff) >> 17) # ROTL32(k1,15) 
     k1 *= c2 

     h1 ^= k1 
     h1 = (h1 << 13) | ((h1 & 0xffffffff) >> 19) # ROTL32(h1,13) 
     h1 = h1 * 5 + 0xe6546b64 

    # tail 
    k1 = 0 

    val = length & 0x03 
    if val == 3: 
     k1 = (ord(data[roundedEnd + 2]) & 0xff) << 16 
    # fallthrough 
    if val in [2, 3]: 
     k1 |= (ord(data[roundedEnd + 1]) & 0xff) << 8 
    # fallthrough 
    if val in [1, 2, 3]: 
     k1 |= ord(data[roundedEnd]) & 0xff 
     k1 *= c1 
     k1 = (k1 << 15) | ((k1 & 0xffffffff) >> 17) # ROTL32(k1,15) 
     k1 *= c2 
     h1 ^= k1 

    # finalization 
    h1 ^= length 

    # fmix(h1) 
    h1 ^= ((h1 & 0xffffffff) >> 16) 
    h1 *= 0x85ebca6b 
    h1 ^= ((h1 & 0xffffffff) >> 13) 
    h1 *= 0xc2b2ae35 
    h1 ^= ((h1 & 0xffffffff) >> 16) 

    return h1 & 0xffffffff 

Answer 4

naprawić błędy w wersji Nikolas za

def bytes_to_long(bytes): 
    assert len(bytes) == 8 
    return sum((b << (k * 8) for k, b in enumerate(bytes))) 


def murmur64(data, seed = 19820125): 

    m = 0xc6a4a7935bd1e995 
    r = 47 

    MASK = 2 ** 64 - 1 

    data_as_bytes = bytearray(data) 

    h = seed^((m * len(data_as_bytes)) & MASK) 

    off = len(data_as_bytes)/8*8 
    for ll in range(0, off, 8): 
     k = bytes_to_long(data_as_bytes[ll:ll + 8]) 
     k = (k * m) & MASK 
     k = k^((k >> r) & MASK) 
     k = (k * m) & MASK 
     h = (h^k) 
     h = (h * m) & MASK 

    l = len(data_as_bytes) & 7 

    if l >= 7: 
     h = (h^(data_as_bytes[off+6] << 48)) 

    if l >= 6: 
     h = (h^(data_as_bytes[off+5] << 40)) 

    if l >= 5: 
     h = (h^(data_as_bytes[off+4] << 32)) 

    if l >= 4: 
     h = (h^(data_as_bytes[off+3] << 24)) 

    if l >= 3: 
     h = (h^(data_as_bytes[off+2] << 16)) 

    if l >= 2: 
     h = (h^(data_as_bytes[off+1] << 8)) 

    if l >= 1: 
     h = (h^data_as_bytes[off]) 
     h = (h * m) & MASK 

    h = h^((h >> r) & MASK) 
    h = (h * m) & MASK 
    h = h^((h >> r) & MASK) 

    return h