0

Cormenなどによるアルゴリズムの概要で文字列アルゴリズムについて読んでいます

以下は、いくつかの基本的な数論的表記法に関するテキストです。

注：以下のテキストでは、==をモジュロ等価として参照します。

ある整数を別の整数で割ったときの余りの概念が明確に定義されている場合、余りが等しいことを示すために特別な表記法を提供すると便利です。（a mod n）=（b mod n）の場合、a == b（mod n）と記述し、aはnを法とするbと同等であると言います。言い換えると、aとbの余りがnで割ったときに同じ余りがある場合、a == b（mod n）になります。同様に、n |の場合に限り、a == b（mod n）（b-a）。たとえば、61 == 6（mod 11）です。また、-13 == 22 == 2 ==（mod 5）。

整数は、nを法とする剰余に従ってn個の同値類に分割できます。整数aを含むnを法とする同値類は

[a] n = {a + kn：kZ}。

たとえば、[3] 7={。。。、-11、-4、3、10、17 、。。。}; このセットの他の表示は[-4]7と[10]7です。

[b] nに属するaを書くことは、a == b（mod n）を書くことと同じです。そのようなすべての同値類のセットは

Zn = {[a] n：0 <= a <= n-1} .----------> Eq 1

上記のテキストでの私の質問は、式1で、「a」は0からn-1の間にあるべきであると述べられていますが、たとえば、0から6の間にない-4として与えられているのはなぜですか？

上記に加えて、ラビン-カープアルゴリズムでは、3番目の数を法として2つの数の等価性を使用することが述べられていますか？これは何を意味するのでしょうか？

4

2 に答える 2

1

プログラミングではありませんが、私はあなたを正しい方向に動かそうとします。

-4が含まれている例は、同値類の例です。これは、特定の数に相当するすべての数のセットです。したがって、[3] 7では、すべての数値は3と同等（モジュロ7）であり、これには-4、17、710、およびその他の無限大が含まれます。

同じクラスに[10]7という名前を付けることもできます。これは、3に相当する（モジュロ7）すべての数値が同時に10に相当する（モジュロ7）ためです。

最後の定義は、すべての異なる同値類のセットを示し、モジュロ7の場合、それらは正確に7つあり、0から6までの数で生成できると述べています。

Zn = {[a]n : n <= a < 2 * n}

[0]7は[7]7と同じものであり、[6]7は[13]7と同じものであるため、意味は同じままです。

于 2011-12-29T09:01:46.323 に答える
0

これはプログラミングの問題ではありませんが、気にしないでください...

「a」は0からn-1の間にあるべきであると述べられていますが、例えば、0から6の間にない-4として与えられているのはなぜですか？

[-4] nは、0 <=x<nであるようないくつかのxの[x]nと同じ同値類であるためです。したがって、式1は、この事実を利用して定義を「調整」し、すべての可能性を明確にします。

上記に加えて、ラビン-カープアルゴリズムでは、3番目の数を法として2つの数の等価性を使用することが述べられていますか？これは何を意味するのでしょうか？

Rabin-Karpアルゴリズムでは、検索している部分文字列のハッシュ値を計算する必要があります。ハッシュするときは、非常に小さな文字列であっても、使用可能なドメイン全体を使用するハッシュ関数を使用することが重要です。ハッシュが32ビット整数で、連続するUnicode値を足し合わせるだけの場合、ハッシュは通常非常に小さくなり、多くの衝突が発生します。

ですから、大きな答えを出すことができる関数が必要です。残念ながら、これは整数のオーバーフローの可能性にもさらされます。したがって、モジュロ演算を使用して、オーバーフローによって比較が台無しにならないようにします。

于 2011-12-29T09:15:44.247 に答える