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)

在不同的小例子和教学书中,他们只使用两个或三个哈希函数的形式(h = a*x + b mod p).这很容易找到,但在实践中如何做,我怎样才能找到100个这样的独立功能.

在这里的Java示例中,仅从一个散列函数而不是多散列函数生成散列值,而与行索引无关.区别在哪里？我现在的问题是如何找到这些独立的哈希函数,或者如果只有一个哈希函数的方法如何在算法中处理这些值？

Answer 1

一种简单的方法是使用参数哈希系列，例如制表哈希函数（http://en.wikipedia.org/wiki/Tabulation_hashing）

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