最小哈希实现如何找到排列

我有实施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有生成的哈希值只能从一个散列函数，而不是多散列函数，不依赖于行索引的。区别在哪里？我的问题是现在如何找到这些独立的散列函数或者如果有一种方法只有一个哈希函数如何在算法把这些价值？

来源

2013-09-24 user2359192

使用参数散列家族如制表通过选择不同组的散列函数（http://en.wikipedia.org/wiki/Tabulation_hashing）

在书中的实施例（* X + B mod p）的一个简单的方法（A，B，P）你可以有不同的散列函数。具有独立散列函数的一种方法是选择（a，b，p）素数/共素数，并且优选大数字

来源

2013-10-08 20:10:33 iampat

根据iampat的回答，您可以使用制表哈希（http://en.wikipedia.org/wiki/Tabulation_hashing）。

提供良好结果的另一个非常有效的选项是使用一个高质量的散列函数（如FNV_1a）来生成主散列，然后使用100个不同的异或和位组合来修改该散列函数。

为了产生每个散列，则作为主散列，由给定距离bitroll它，然后用给定的值进行异或运算的。为100个散列函数中的每一个随机选择bitroll和XOR值。有关更多信息，请参阅this discussion。

有人建议乘法，而不是一个XOR，在这种情况下，你可能要选择素数。

来源

2017-09-26 01:19:00

最小哈希实现如何找到排列

回答

相关问题