13

非常に大きな文字列の n-gram のハッシュを取得できるように、ローリング ハッシュ関数を使用しようとしています。

例えば：

「stackoverflow」を 5 グラムに分割すると、次のようになります。

「stack」、「tacko」、「ackov」、「ckove」、「kover」、「overf」、「verfl」、「erflo」、「rflow」

これはローリング ハッシュ関数に最適です。最初の n グラム ハッシュを計算した後、最初のハッシュの最初の文字を削除し、2 番目のハッシュの新しい最後の文字を追加するだけで済むため、次のハッシュは比較的安価に計算できます。 .

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

H = c 1 a k − 1 + c 2 a k − 2 + c 3 a k − 3 + ... + c k a 0 a は定数、c1,...,ck は入力文字です。

Rabin-Karp string search algorithmでこのリンクをたどると、「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 を使用しています。ハッシュがオーバーフローしても問題ありませんか? これは望ましいと思いますが、よくわかりません。

これはこれを行う正しい方法のように思えますか?

4

3 に答える 3

1

私は、sedgewick のアルゴリズムの本の 1 つからのものと思われる、わずかに異なる実装を覚えています (サンプル コードも含まれています - 調べてみてください)。32 ビット整数に調整された要約を次に示します。

モジュロ演算を使用して、各操作の後に整数がオーバーフローするのを防ぎます。

初期設定:

  • c = テキスト (「スタックオーバーフロー」)
  • M = 「n グラム」の長さ
  • d = アルファベットのサイズ (256)
  • q = (d+1)*q がオーバーフローしないように大きな素数 (8355967 が適切な選択かもしれません)
  • dM = d M-1 mod q

まず、最初の n-gram のハッシュ値を計算します。

h = 0
for i from 1 to M:
  h = (h*d + c[i]) mod q

そして、次のすべての n-gram に対して:

for i from 1 to lenght(c)-M:
  // first subtract the oldest character
  h = (h + d*q - c[i]*dM) mod q

  // then add the next character
  h = (h*d + c[i+M]) mod q

最も古い文字を減算する前に d*q を追加する必要がある理由は、前のモジュロ演算によって引き起こされた小さな値のために負の値に遭遇する可能性があるためです。

エラーが含まれていますが、アイデアを得る必要があると思います。詳細、エラーの少ない、より良い説明については、sedgewick のアルゴリズムの本を探してみてください。:)

于 2010-02-22T23:44:04.500 に答える
0

私が理解しているように、それは次の関数の最小化です。

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

どこでmaxchar = 62（のためにA-Za-z0-9）。Excelで計算したところです（OO Calc、正確に）:)そして、見つかった最大Aは素数の76、またはです。73

于 2010-02-22T21:43:42.053 に答える
0

ここで何を目指しているのかわかりませんが、パフォーマンスを改善しようとしている場合、math.pow を使用すると、ローリング ハッシュ値を計算して節約するよりもはるかに多くのコストがかかります。

シンプルで効率的なものを維持することから始めることをお勧めします。十分に高速であることがわかるでしょう。

于 2010-02-24T21:14:00.917 に答える