[C#] Rabin-Karp文字列検索アルゴリズムで使用されるローリングハッシュ関数の実装実装はありますか?


Answers

私が理解するように、それは関数の最小化です:

2^31 - sum (maxchar) * A^kx

maxchar = 62A-Za-z0-9 )。 私はちょうどExcel(OO Calc、正確に)によってそれを計算しました:)そしてそれが見つかった最大Aは素数のために76または73です。

Question

私は非常に大きな文字列のnグラムのハッシュを取ることができるようにローリングハッシュ関数を使用するために探しています。

例えば:

""は、5グラムに分割されます:

"スタック"、 "タコ"、 "ackov"、 "ckove"、 "kover"、 "overf"、 "verfl"、 "erflo"、 "rflow"

最初のn-gramハッシュを計算した後は、最初のハッシュの最初の文字を削除して2番目のハッシュの新しい最後の文字を追加するだけで済むので、次のものは計算するのが比較的安いからです。

私は、一般に、このハッシュ関数は次のように生成されることを知っています:

aは定数、c1、...、ckは入力文字である。ここで、aは定数、c1、...、ckは入力文字である。

あなたがRabin-Karp文字列検索アルゴリズムでこのリンクをたどると、 "a"は通常大きな素数であると書かれています。

私は自分のハッシュを32ビットの整数に格納したいので、整数をオーバーフローさせないようにプライムの大きさを "a"にする必要がありますか?

既に使用できるこのハッシュ関数の既存の実装がどこかに存在しますか?

作成した実装は次のとおりです。

public class hash2
{

    public int prime = 101;

    public int hash(String text)
    {
        int hash = 0;

        for(int i = 0; i < text.length(); i++)
        {
            char c = text.charAt(i);
            hash += c * (int) (Math.pow(prime, text.length() - 1 - i));
        }

        return hash;
    }

    public int rollHash(int previousHash, String previousText, String currentText)
    {

        char firstChar = previousText.charAt(0);
        char lastChar = currentText.charAt(currentText.length() - 1);

        int firstCharHash = firstChar * (int) (Math.pow(prime, previousText.length() - 1));
        int hash = (previousHash - firstCharHash) * prime + lastChar;

        return hash;
    }

    public static void main(String[] args)
    {
        hash2 hashify = new hash2();

        int firstHash = hashify.hash("mydog");
        System.out.println(firstHash);
        System.out.println(hashify.hash("ydogr"));
        System.out.println(hashify.rollHash(firstHash, "mydog", "ydogr"));
    }

}

私はプライムとして101を使用しています。 私のハッシュがオーバーフローするかどうかは重要ですか? 私はこれが望ましいと思うが、わからない。

これはこれについて正しい方法のように見えますか?