代码之家 › 专栏 › 技术社区 › mdm

木瓦印刷在实践中是如何工作的?

text-mining information-retrieval permutation random performance

3

mdm · 技术社区 · 15 年前

我试着用木瓦印刷来衡量文档的相似性。该过程包括以下步骤:

步骤3涉及生成一个很长序列的随机排列。使用Knuth洗牌似乎是不可能的。有什么捷径吗?请注意,最后我们只需要一个元素的结果排列。

1 回复 | 直到 15 年前

1

3

msft-er 14 年前

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

标准的成对独立散列函数是h(x)=ax+b(mod p),其中A和b是随机选择的,p是素数。