MurmurHashの純粋な python (c++ なし) 実装が必要です (そして見つけることができません) 。私のプロジェクトでは、速度やメモリ使用量は問題ではありません。
ここで試行を見つけましたが、31 ビットのハッシュに制限されており、実際には 64 ビットのハッシュが必要です。
注 : 迅速な実装が必要な場合は、MurmurHash2 ライブラリがここにあり、MurmurHash3 ライブラリがここにあります
質問する
14544 次
5 に答える
11
これはテストされていません (申し訳ありません!) が、ここに私が思いついたバージョンがあります。Python では任意に大きな整数を使用できるため、最初の 8 バイト (または 64 ビット) のマスクを作成し、それを (ビットごとの AND を介して) 64 ビットより大きい整数を生成できるすべての算術結果に適用しました。たぶん、他の誰かが一般的なアプローチとエンディアンに関する考えられる問題などについてコメントすることができます.
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
于 2013-04-02T01:50:11.860 に答える
8
ニコラスのバージョンのバグを修正
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
于 2015-01-29T05:51:29.007 に答える
6
これは MurmurHash3 32 の純粋な Python 実装です。これは文字列のみをハッシュしますが、代わりにバイト配列を取るように簡単に適応させることができます。これはアルゴリズムのJava バージョンからのポートです。
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
于 2014-05-30T14:53:22.367 に答える
6
完全に互換性があり、mmh3 ラッパーで置き換え可能な MurmurHash3 のもう 1 つの純粋な Python 実装ですが、それでも 32 ビット Murmur3 に制限されています: https://github.com/wc-duck/pymmh3
于 2015-02-27T14:27:59.300 に答える