5

我在实施 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 示例中，仅从一个哈希函数而不是多个哈希函数生成哈希值，与行索引无关。区别在哪里？我现在的问题是如何找到这些独立的散列函数，或者如果有一种只有一个散列函数的方法如何在算法中处理这些值？

4

2 回答 2

1

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

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

于 2013-10-08T20:10:33.590 回答
0

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

另一个提供良好结果的非常有效的选择是使用单个优质哈希函数（例如 FNV_1a）来生成主哈希，然后使用 100 种不同的 XOR 和 bitroll 组合对其进行修改。

要生成每个散列，您需要获取主散列，将其按给定距离进行位滚动，然后将其与给定值异或。为 100 个哈希函数中的每一个随机选择 bitroll 和 XOR 值。有关更多信息，请参阅此讨论。

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

于 2017-09-26T01:19:00.277 回答