Minhash实现如何查找用于排列的散列函数

Question

我在实现minhashing时遇到了问题。在纸上和阅读中，我理解了这个概念，但我的问题是排列“技巧”。不是排列集合和值的矩阵，而是建议实现：“选择k(例如100)个独立的散列函数”，然后算法说：

for each row r 
    for each column c 
        if c has 1 in row r 
           for each hash function h_i  do
            if h_i(r) is a smaller value than M (i, c) then
            M(i, c) := h_i(r)

在不同的小示例和教学book中，他们只使用两到三个形式的散列函数(h = a*x +b mod p)。这很容易找到，但在实践中，我如何才能找到100个这样的独立函数呢？

在Java示例here中，只有一个散列函数生成的散列值，而不是多个散列函数，独立于行索引。区别在哪里？我现在的问题是如何找到这些独立的散列函数，或者如果只有一个散列函数的方法，如何在算法中处理这些值？

Answer 1

一种简单的方法是使用参数散列族，如表散列函数(http://en.wikipedia.org/wiki/Tabulation_hashing)

在本书的示例(a*x+b mod p)中，通过选择不同的(a，b，p)集合，您可以拥有不同的散列函数。获得独立哈希函数的一种方法是选择(a，b，p)素数/联合素数，并且最好是大数字

Answer 2

根据iampat的回答，您可以使用表格散列(http://en.wikipedia.org/wiki/Tabulation_hashing)。

另一个产生良好结果的非常有效的选择是使用单个高质量的散列函数(例如FNV_1a)来生成主散列，然后使用100种不同的异或和位数组合对其进行修改。

要生成每个散列，您需要获取主散列，按给定的距离对其进行位滚动，然后将其与给定值进行异或。对于100个散列函数中的每一个，随机选择bitroll和XOR值。有关详细信息，请参阅this discussion。

有些人建议使用乘法而不是XOR，在这种情况下，您可能希望选择质数。