14

ウェブサイトのフォーラムでこの Rabin Karp 文字列マッチング アルゴリズムを見たことがあり、それを実装することに興味がありますが、変数 ulong Q と ulong D がそれぞれ 100007 と 256 である理由を誰かが教えてくれるかどうか疑問に思っていました :S ? これらの価値観にはどのような意味がありますか?

static void Main(string[] args)
{
    string A = "String that contains a pattern.";
    string B = "pattern";
    ulong siga = 0;
    ulong sigb = 0;
    ulong Q = 100007;
    ulong D = 256;
    for (int i = 0; i < B.Length; i++)
    {
        siga = (siga * D + (ulong)A[i]) % Q;
        sigb = (sigb * D + (ulong)B[i]) % Q;
    }
    if (siga == sigb)
    {
        Console.WriteLine(string.Format(">>{0}<<{1}", A.Substring(0, B.Length), A.Substring(B.Length)));
        return;
    }
    ulong pow = 1;
    for (int k = 1; k <= B.Length - 1; k++)
        pow = (pow * D) % Q;

    for (int j = 1; j <= A.Length - B.Length; j++)
    {
        siga = (siga + Q - pow * (ulong)A[j - 1] % Q) % Q;
        siga = (siga * D + (ulong)A[j + B.Length - 1]) % Q;
        if (siga == sigb)
        {
            if (A.Substring(j, B.Length) == B)
            {
                Console.WriteLine(string.Format("{0}>>{1}<<{2}", A.Substring(0, j),
                                                                    A.Substring(j, B.Length),
                                                                    A.Substring(j + B.Length)));
                return;
            }
        }
    }
    Console.WriteLine("Not copied!");
}
4

2 に答える 2

7

マジックナンバーについて、ポールの答えはかなり明確です。

コードに関する限り、Rabin Karp の主なアイデアは、文字列のスライド部分とパターンの間でハッシュ比較を実行することです。

部分文字列全体で毎回ハッシュを計算することはできません。そうしないと、計算の複雑さがO(n^2)線形ではなく二次になりますO(n)。

したがって、ローリング ハッシュ関数が適用されます。たとえば、反復ごとに 1 文字だけで部分文字列のハッシュ値が更新されます。

それでは、コードにコメントしてみましょう。

for (int i = 0; i < B.Length; i++)
{
    siga = (siga * D + (ulong)A[i]) % Q;
    sigb = (sigb * D + (ulong)B[i]) % Q;
}
if (siga == sigb)
{
    Console.WriteLine(string.Format(">>{0}<<{1}", A.Substring(0, B.Length), A.Substring(B.Length)));
    return;
}

^このピースは、パターンB( ) のハッシュと、同じ長さの のsigb最初の部分文字列のハッシュコードを計算します。ハッシュが衝突する可能性があるため、実際には完全に正しいわけではありません¹。そのため、if ステートメントを変更する必要があります : 。ABif (siga == sigb && A.Substring(0, B.Length) == B)

ulong pow = 1;
for (int k = 1; k <= B.Length - 1; k++)
    pow = (pow * D) % Q;

^powローリング ハッシュを実行するために必要な計算は次のとおりです。

for (int j = 1; j <= A.Length - B.Length; j++)
{
    siga = (siga + Q - pow * (ulong)A[j - 1] % Q) % Q;
    siga = (siga * D + (ulong)A[j + B.Length - 1]) % Q;
    if (siga == sigb)
    {
        if (A.Substring(j, B.Length) == B)
        {
            Console.WriteLine(string.Format("{0}>>{1}<<{2}", A.Substring(0, j),
                                                                A.Substring(j, B.Length),
                                                                A.Substring(j + B.Length)));
            return;
        }
    }
}

^最後に、残りの文字列 (つまり、2 番目の文字から末尾まで) がスキャンされ、A 部分文字列のハッシュ値が更新され、B のハッシュ値 (最初に計算されたもの) と比較されます。

2 つのハッシュが等しい場合、部分文字列とパターンが比較され¹、実際に等しい場合はメッセージが返されます。

¹ハッシュ値は衝突する可能性があります。したがって、2 つの文字列のハッシュ値が異なる場合、それらは明らかに異なりますが、2 つのハッシュが等しい場合は、等しいかどうかはわかりません。

于 2012-04-26T18:11:00.640 に答える
6

このアルゴリズムでは、ハッシュを使用して文字列を高速に比較します。Q と D は、コーダーがおそらく少し試行錯誤して到達した魔法の数であり、この特定のアルゴリズムのハッシュ値の適切な分布を示します。

多くの場所のハッシュに使用されるこれらのタイプのマジック ナンバーを見ることができます。以下の例は、.NET 2.0 文字列型の GetHashCode 関数の逆コンパイルされた定義です。

[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail)]
public override unsafe int GetHashCode()
{
    char* chrPointer = null;
    int num1;
    int num2;
    fixed (string str = (string)this)
    {
        num1 = 352654597;
        num2 = num1;
        int* numPointer = chrPointer;
        for (int i = this.Length; i > 0; i = i - 4)
        {
            num1 = (num1 << 5) + num1 + (num1 >> 27) ^ numPointer;
            if (i <= 2)
            {
                break;
            }
            num2 = (num2 << 5) + num2 + (num2 >> 27) ^ numPointer + (void*)4;
            numPointer = numPointer + (void*)8;
        }
    }
    return num1 + num2 * 1566083941;
}

以下は、R# で生成されたサンプル型の GetHashcode オーバーライド関数の別の例です。

    public override int GetHashCode()
    {
        unchecked
        {
            int result = (SomeStrId != null ? SomeStrId.GetHashCode() : 0);
            result = (result*397) ^ (Desc != null ? Desc.GetHashCode() : 0);
            result = (result*397) ^ (AnotherId != null ? AnotherId.GetHashCode() : 0);
            return result;
        }
    }
于 2012-04-26T17:43:27.903 に答える