pybbhash

这是一个Python（Cython）包装器，用于构建BBHash代码库，用于构建最小完美哈希函数。

目前，这个库支持来自spacegraphcats的k-mer哈希需求，使用（主要是）murmurhash生成的哈希值，例如来自khmer的Nodetable和sourmash哈希。因此，我专注于构建64位哈希的MPHF，并仅包装该接口的一部分；其余部分应该是相当直接的（哈哈！）。

我还在bbhash_table模块中添加了一个Python可访问的“值表”，BBHashTable。这是一个支持字典样式的功能表，您可以关联一个哈希值与一个值，然后使用哈希值查询表以检索该值。这里唯一棘手的地方是，与bbhash模块不同，此表支持使用不在MPHF中的哈希值进行查询。

进一步改进的想法。

• 我希望能够在PyMPHF构建中使用通用的Python迭代器。目前，存在一轮内存效率低下的哈希值复制，当您有很多k-mer时，这很糟糕！

• 我希望能够将数据保存到/从字符串加载，而不仅仅是文件。

我还需要调查线程安全性。

用法

核心bbhash功能用法

import bbhash

# some collection of 64-bit (or smaller) hashes
uint_hashes = [10, 20, 50, 80]

num_threads = 1 # hopefully self-explanatory :)
gamma = 1.0     # internal gamma parameter for BBHash

mph = bbhash.PyMPHF(uint_hashes, len(uint_hashes), num_threads, gamma)

for val in uint_hashes:
    print('{} now hashes to {}'.format(val, mph.lookup(val)))

# can also use 'mph.save(filename)' and 'mph = bbhash.load_mphf(filename)'.

BBHashTable用法

import random
from collections import defaultdict
from bbhash_table import BBHashTable

all_hashes = [ random.randint(100, 2**32) for i in range(200) ]
half_hashes = all_hashes[:100]

table = BBHashTable()

# hash the first 100 of the hashes
table.initialize(half_hashes)

# store associated values
for hashval, value in zip(half_hashes, [ 1, 2, 3, 4, 5 ] *20):
   table[hashval] = value
   
# retrieve & count for all (which will include hashes not in MPHF)
d = defaultdict(int)
for hashval in all_hashes:
   value = table[hashval]
   d[value] += 1

assert d[1] == 20
assert d[None] == 100

最后一个for循环可以使用Cython快速完成

d = table.get_unique_values(all_hashes)

动机：该表是存储从k-mer到紧凑的De Bruijn图节点ID映射的有用方式。（我们在spacegraphcats的几个地方使用了这个！)

CTB 2020年10月