क्या मुर्मूरशैश का शुद्ध पायथन कार्यान्वयन है?

Question

मुझे MurmurHash के शुद्ध पायथन (कोई सी ++) कार्यान्वयन की आवश्यकता नहीं है (और नहीं मिल सकती), और मैं खुद को लिखने के लिए बहुत नौसिखिया हूं। गति या स्मृति उपयोग मेरी परियोजना पर कोई फर्क नहीं पड़ता।

मुझे here का प्रयास मिलता है, लेकिन यह 31 बिट हैश तक सीमित है और मुझे वास्तव में 64 बिट हैश की आवश्यकता है।

नोट: जो लोग एक तेजी से कार्यान्वयन की जरूरत के लिए, वहाँ एक MurmurHash2 पुस्तकालय here और एक MurmurHash3 पुस्तकालय here

Answer 1

MurmurHash3 का एक और शुद्ध अजगर कार्यान्वयन कि पूरी तरह से संगत और mmh3 आवरण से बदली है, लेकिन अभी भी 32-बिट तक ही सीमित है Murmur3: https://github.com/wc-duck/pymmh3

Answer 2

इस अपरीक्षित है (! खेद) है, लेकिन यहाँ एक संस्करण मैं के साथ आया है। पायथन मनमाने ढंग से बड़े पूर्णांक की अनुमति देता है, इसलिए मैंने पहले 8 बाइट्स (या 64 बिट्स) के लिए एक मुखौटा बनाया है जिसे मैं तब लागू करता हूं (बिटवॉइड के माध्यम से) और सभी अंकगणितीय परिणामों के लिए जो 64 बिट्स से बड़े पूर्णांक उत्पन्न कर सकते हैं। हो सकता है कि किसी और को, आदि सामान्य दृष्टिकोण और endianness को ठीक करने पर टिप्पणी कर सकता है

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

यहाँ MurmurHash3 32 का एक शुद्ध अजगर कार्यान्वयन चला जाता है, यह तार केवल हैश लेकिन आसानी बजाय बाइट सरणियों लेने के लिए अनुकूलित किया जा सकता। यह एल्गोरिदम के 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

निकोलस के संस्करण में कीड़े को ठीक

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