Có thực hiện python tinh khiết của MurmurHash không?

Question

Tôi cần (và không thể tìm thấy) một con trăn thuần túy (không C++) thực hiện MurmurHash, và tôi quá mới để tự viết. Tốc độ hoặc sử dụng bộ nhớ không quan trọng trong dự án của tôi.

Tôi tìm một nỗ lực here, nhưng giới hạn ở mức băm 31bits và tôi thực sự cần một băm 64 bit.

Lưu ý: đối với những người cần một việc thực hiện nhanh chóng, có một thư viện MurmurHash2 here và thư viện MurmurHash3 here

Answer 1

Một python thực hiện tinh khiết của MurmurHash3 đó là hoàn toàn tương thích và có thể thay thế bởi các wrapper mmh3, nhưng vẫn còn hạn chế đến 32-bit Murmur3: https://github.com/wc-duck/pymmh3

Answer 2

này là chưa được kiểm tra (xin lỗi!), Nhưng đây là một phiên bản tôi đã đưa ra. Python cho phép các số nguyên lớn tùy ý, vì vậy tôi tạo một mặt nạ cho 8 byte đầu tiên (hoặc 64 bit) mà sau đó tôi áp dụng (thông qua bitwise AND) cho tất cả các kết quả số học có thể tạo ra số nguyên lớn hơn 64 bit. Có lẽ ai đó có thể nhận xét về cách tiếp cận chung và các vấn đề có thể với endianness vv

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

Ở đây đi một thực hiện Python tinh khiết của MurmurHash3 32, nó chỉ băm chuỗi nhưng có thể dễ dàng thích nghi với lấy mảng byte để thay thế. Đây là một cổng từ số Java version của thuật toán.

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

sửa chữa các lỗi trong phiên bản Nikolas của

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