3

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

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

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

4

1 回答 1

3

警告：我对此不是 100% 肯定，但我已经阅读了一些论文，我相信这就是它的工作原理。例如，在 Piotr Indyk 的“一个小的近似最小独立散列函数族”中，他写道“在与 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

于 2011-05-09T23:56:41.847 回答