¿Hay una implementación de Python puro de MurmurHash?

Question

Necesito (y no puedo encontrar) una implementación pura de Python (sin c ++) de MurmurHash , y soy demasiado novato para escribirme. El uso de la velocidad o la memoria no importa en mi proyecto.

Encuentro un intento here , pero está limitado a un hash de 31 bits y realmente necesito un hash de 64 bits.

Nota: para aquellos que necesitan una implementación rápida, hay una biblioteca MurmurHash2 here y una biblioteca MurmurHash3 here

Answer 1

Aquí va una implementación Python pura de MurmurHash3 32, solo contiene cadenas, pero puede adaptarse fácilmente para tomar matrices de bytes en su lugar. Este es un puerto de la versión Java del algoritmo.

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 2

Esto no se ha probado (¡lo siento!), pero aquí hay una versión que se me ocurrió. Python permite enteros arbitrariamente grandes, así que creé una máscara para los primeros 8 bytes (o 64 bits) que luego aplico (mediante bit a AND) a todos los resultados aritméticos que podrían producir números enteros mayores a 64 bits. Tal vez alguien más pueda comentar sobre el enfoque general y los posibles problemas con el endianness, etc.

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

Otra implementación Python pura de MurmurHash3 que es totalmente compatible y reemplazable por el envoltorio mmh3, pero aún está limitada a Murmur3 de 32 bits: https://github.com/wc-duck/pymmh3

Answer 4

Propongo cambiar la función bytes_to_long para que los valores con menos de ocho bytes sean posibles:

def bytes_to_long(bytes):
length = len(bytes)
if length < 8:
extra = 8 - length
bytes = b''/000'' * extra + bytes
assert len(bytes) == 8
return sum((b << (k * 8) for k, b in enumerate(bytes)))

Esto llena el bytearray con bytes nulos para que la función de afirmación de imágenes estáticas (podría eliminarlo ahora) como está previsto, pero permita la conversión de valores más pequeños.

Answer 5

arreglar los errores en la versión de Nikolas

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