Shingleprinting如何在实践中工作？

Question

我正在尝试使用shingleprinting来衡量文档的相似度。该过程涉及以下步骤：

1. 创建两个文件D1的5-shingling，D2
2. 散列具有64位散列
3. 各屋顶板拾取数字的随机置换从0到2^64-1，并适用于木瓦哈希
4. 对于每个文件找到最小的结果值的
5. 如果它们匹配指望它作为一个正面的例子，如果不把它作为一种反面教材
6. 重复3〜5 。 一些倍
7. 使用positive_examples/total examples作为相似性度量

步骤3包括产生非常长的序列的随机置换。使用Knuth-shuffle似乎是不可能的。有没有这个捷径？请注意，最终我们只需要得到的排列的单个元素。

Answer 1

警告：我对此不是100％肯定，但我已阅读了一些论文，我相信这是它的工作原理。例如，Piotr Indyk在“一个近似小的独立散列函数族”中写道：“在与Altavista集成的实现中，集合H被选择为散列函数的成对独立系列。”

在步骤3中，实际上并不需要[n]上的随机排列（从1到n的整数）。事实证明，成对独立的哈希函数在实践中起作用。所以你要做的是选择一个独立的哈希函数h。然后将h应用于每个木瓦哈希。您可以在步骤4中取这些值的最小值。

标准的成对独立散列函数是h（x）= ax + b（mod p），其中a和b是随机选择的，p是素数。

参考文献：http://www.cs.princeton.edu/courses/archive/fall08/cos521/hash.pdf and http://people.csail.mit.edu/indyk/minwise99.ps