-4

我正在阅读这篇论文（第 3 页和第 8 页）：http ://acl.ldc.upenn.edu/P/P05/P05-1077.pdf其中定义了一个置换函数来生成签名的置换。签名是一串位，如“1001”

它将置换函数定义如下： 在此处输入图像描述

但是，当我应用它时，它不起作用。假设我有字符串“1001”，它的索引是 {0,1,2,3}。目的是使索引排列为例如 {2,3,0,1}。设 p = 7, a = 1 和 b = 2。现在我需要排列索引：

pi(0) = (0+2) mod 7 = 2

pi(1) = (1+2) mod 7 = 3

pi(2) = (2+2) mod 7 = 4 <<<<<< 这里问题开始了，因为它生成了一个超出索引空间的错误值

pi(3) = (3+2) mod 7 = 5 <<<<<< 这里也一样

所以我最终得到了新的索引 {2,3,4,5} 这是无效的，因为我首先没有 4 和 5 作为索引。

我的解决方案有什么问题？难道我做错了什么？

我在 stackoverflow 上看到过生成字符串所有排列的帖子。但我想使用特定的排列函数生成一个排列。因为我想对多个字符串使用相同的置换函数。然后我希望能够使用不同的参数创建另一个置换函数，并将新的置换函数应用于同一组字符串/签名。

编辑：我在python中发现这段代码应用了相同的想法，但不幸的是我以前从未使用过python，所以我希望有人能看到有什么不同：

class Permutation(object):
    def __init__(self, maximumValue): 
        if not isPrime(maximumValue): raise Exception('Maximum value should be prime')
        self.p, self.a, self.b = maximumValue, random.choice(range(maximumValue)[3::2]), random.choice(range(maximumValue))
    def applyFunction(self, x): return (self.a*x+self.b)%self.p
    def __eq__(self, other): return self.a==other.a and self.b==other.b and self.p==other.p
    def __str__(self): return 'p: %s, a: %s, b: %s'%(self.p, self.a, self.b)

代码来自这里：https ://github.com/kykamath/streaming_lsh/blob/master/streaming_lsh/classes.py

4

2 回答 2

1

您需要的是字符串的随机排列。您可以为此使用 Knuth shuffle，而不是使用论文中指定的那个。随机排列背后的想法是得到一个的概率应该是 1 / n!。这就对了。您可以使用任何满足此标准的算法。http://en.wikipedia.org/wiki/Random_permutation

好的，您的代码正在生成 0，P 范围内的索引。但是您的源数组的长度 < P。因此，它会导致超出范围。解决此问题的一种方法是使用预先确定的填充字符填充源数组以生成长度 P。在结果排列中，删除所有填充字符并缩小。始终确保 P >= 源字符串的长度。

于 2013-07-29T18:06:47.503 回答
1

给定的函数本质上是一个随机数生成器http://en.wikipedia.org/wiki/Linear_congruential_generator。要获得置换索引，您需要根据数组大小修改结果。所以1001你会使用pi(x) % 4.

编辑：再想一想，这个功能不太可能是一对一的，因为你最终会得到类似0 mod 4 = 4 mod 4but的东西0 mod 7 != 4 mod 7。

为了在您的范围内生成元素，您必须改为重复应用该函数，直到您获得范围内的数字。因此，如果您pi(0) = 6改用 try pi(6)，并且如果pi(6) = 5try pi(5)。

在您发布的代码中，作者似乎总是使用素数大小的数组进行排列，所以他没有这个问题。

于 2013-07-29T18:11:18.510 回答