1

ローリングハッシュラビン-カープアルゴリズムで大きなハッシュコード値を処理するにはどうすればよいですか？負の数を避けるためにモジュラー演算を使用していますが、ハッシュコードがモジュロ数（N = 83559671）を超えると問題が発生します。基数を素数（ハッシュコードを計算するための数）とモジュロ数（本当に大きい）に設定しましたが、長い文字列では機能しません。誰かが問題を見ることができますか？

これが私のコードです。

   public static void main(String [] args){

       int P = 13;         // base
       long M = 83559671;
       long iHash = 0;    
       String word = "abcbadccaaaabbbb";
       int WINDOW = 9;

       for(int i = 0; i < WINDOW; i++){
            iHash = int_mod(int_mod(iHash*P, M) + word[i], M);
       }

       for(int i = WINDOW; i < word.length; i++){
            iHash = int_mod(iHash - word[i-WINDOW] * get_pow(P, WINDOW-1, M), M);
            iHash = int_mod(iHash * P, M);
            iHash = int_mod(iHash + word[i], M);
       }

   }
   public static long get_pow(int p, int t, long M){
        long a = 1;
        for(int i = 0 ; i < t; i++){
              a = int_mod(a * p, M);
        }
        return a;
   }

   public static long int_mod(long a, long b){
        return (a % b+ b) % b;
   }

問題は、文字列の長さが8より長い場合、その文字列のハッシュコードがモジュロ数83559671を超え、比較すると間違った答えが返されることです。短い文字列は適切に機能します。

4

2 に答える 2

4

モジュラスを実行する必要はまったくありません。ここにデモがあります：

public class Foo {
  private static int hash(String s) {
    int hash = 0;
    for (int i = 0; i < s.length(); i++) {
      hash *= 31;
      hash += s.charAt(i);
    }
    return hash;
  }

  public static void main(String[] args) {
    String s1 = "abcdefghij";
    String s2 = s1.substring(1) + "k";
    int pow = 1;
    for (int i = 0; i < s1.length(); i++) {
      pow *= 31;
    }
    System.out.printf("hash(%s) = %d%n", s1, hash(s1));
    System.out.printf("hash(%s) = %d%n31 * hash(%s) - (31^%d * %s) + %s = %s%n",
        s2,
        hash(s2),
        s1,
        s1.length(),
        s1.charAt(0),
        s2.charAt(s2.length() - 1),
        31 * hash(s1) - (pow * s1.charAt(0)) + s2.charAt(s2.length() - 1));
  }
}

これは（正しく）出力されます：

hash(abcdefghij) = -634317659
hash(bcdefghijk) = 21611845
31 * hash(abcdefghij) - (31^10 * a) + k = 21611845
于 2012-09-19T17:23:01.800 に答える
1

文字列を多項式として扱わないのはなぜですか? S長さの文字列があるとしますn。次の関数を見てみましょうF(x) = S[0]*x^(n-1) + S[1]*x^(n-2) + ... + S[i]*x^(n-i-1) + ... + S[n - 2]*x + S[n-1]。を計算しようとするとどうなりますか? コード スニペットのベースはF(P)どこPですか? まあ、string の Rabin-Karp ハッシュを正確に取得できますS。しかし、F(x)は多項式であるため、ホーナーの法則を使用して を計算できますF(P)。結果の値は非常に大きくなる可能性があるため、剰余算術を使用します。

static final long M = 83559671;
static final int Base = 13;

static long hash(String s, int from, int to) {
    int iHash = 0;
    for(int i = from; i < to; i++) {
        iHash *= Base;
        iHash += s.charAt(i);
        iHash %= M;
    }
    return iHash;
}

この関数を使用して、テキスト内にある文字列のハッシュを取得できます。そして、テキストの最初のウィンドウ。次に、ウィンドウをシフトしてハッシュを再計算できます。

static void find(String pattern, String text) {
    if(text.length() < pattern.length()) return;
    int len = pattern.length();
    long ph = hash(pattern, 0, len);
    long h = hash(text, 0, len);
    long basePower = mpow(Base, len);

    if(h == ph) System.out.println("match at 0");
    for(int i = len; i < text.length(); i++) {
        h *= Base;
        h += text.charAt(i);
        h -= basePower * text.charAt(i - len);
        h = mod(h);
        if(h == ph) System.out.println("match at " + (i - len + 1));
    }
}

static long mod(long a) {
    a %= M;
    if(a < 0) {
        a += M;
    }
    return a;
}

static long mpow(long x, int k) {
    long result = 1;
    for(; k > 0; k >>= 1) {
        if(k % 2 == 1) {
            result = mod(result * x);
        }
        x = mod(x * x);
    }
    return result;
}

public static void main(String[] args) {
    find("abracadabra", "abracadabracadabra");
}

このアプローチの詳細については、CLRSを参照することをお勧めします。

于 2012-09-17T12:39:59.950 に答える