algorithm - 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

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

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