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