performance - Shingleprinting 在实践中是如何工作的？

Question

我正在尝试使用 shingleprinting 来衡量文档相似性。该过程包括以下步骤:

1. 创建 5-shingling两个文件 D1, D2
2. 用 64 位散列对每个 shingle 进行散列
3. 选择从 0 到 2^64-1 的数字的随机排列并应用于 shingle hashes
4. 为每个文档找到最小的结果值
5. 匹配的算正例，不匹配的算负例
6. 重复 3. 到 5. 几次
7. 使用positive_examples/total examples作为相似度度量

第 3 步涉及生成一个非常长的序列的随机排列。使用 Knuth-shuffle 似乎是不可能的。这有什么捷径吗？请注意，最后我们只需要生成排列的单个元素。

Answer 1

警告:我对此不是 100% 肯定，但我已经阅读了一些论文并且我相信这就是它的工作原理。例如，在 Piotr Indyk 的“A small approximately min-wise independent family of hash functions”中，他写道“在与 Altavista 集成的实现中，集合 H 被选择为成对独立的哈希函数族。”

在第 3 步中，您实际上不需要对 [n](从 1 到 n 的整数)进行随机排列。事实证明，成对独立的哈希函数在实践中有效。所以你要做的是选择一个成对独立的哈希函数 h。然后将 h 应用于每个 shingle 哈希。您可以在第 4 步中取这些值的最小值。

标准的成对独立哈希函数是 h(x) = ax + b (mod p)，其中 a 和 b 是随机选择的，p 是素数。

引用文献:http://www.cs.princeton.edu/courses/archive/fall08/cos521/hash.pdf和 http://people.csail.mit.edu/indyk/minwise99.ps