-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 <<<<<< ここは同じ

したがって、そもそもインデックスとして 4 と 5 がないため、無効な {2,3,4,5} として新しいインデックスが作成されます。

私のソリューションの何が問題になっていますか? 私は何か間違ったことをしていますか？

文字列のすべての順列を生成するスタックオーバーフローの投稿を見てきました。しかし、特定の順列関数を使用して 1 つの順列を生成したいと考えています。複数の文字列に対して同じ順列関数を使用したいからです。次に、異なるパラメーターを使用して別の順列関数を作成し、同じ文字列/署名のセットに新しい順列関数を適用できるようにしたいと考えています。

編集：同じアイデアを適用する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

指定された関数は、本質的に乱数ジェネレータhttp://en.wikipedia.org/wiki/Linear_congruential_generatorです。並べ替えられたインデックスを取得するには、結果を配列サイズで変更する必要があります。だから1001あなたのために使用するでしょうpi(x) % 4。

edit : これについてもう少し考えてみると、この関数は0 mod 4 = 4 mod 4butのようなものになるため、1 対 1 である可能性は低い0 mod 7 != 4 mod 7です。

範囲内の要素を生成するには、範囲内の数値が得られるまで関数を繰り返し適用する必要があります。したがって、代わりにpi(0) = 6tryを取得した場合、およびtryを取得した場合。pi(6)pi(6) = 5pi(5)

あなたが投稿したコードでは、著者は順列に素数サイズの配列を常に使用しているように見えるため、この問題はありません。

于 2013-07-29T18:11:18.510 に答える