多項式ハッシュとその応用

こんにちは、Habr。 今日は、さまざまなアルゴリズムの問​​題を解決する際に多項式ハッシュを使用する方法（以下、単にハッシュ）を書きます。

はじめに

定義から始めましょう。 文字列s _{0..n-1があるとし}ます。 この行の多項式ハッシュは、数h = hash（s _0..n-1 ）= s ₀ + ps ₁ + p ² s ₂ + ... + p ^n-1 s _n-1です 。ここで、 pは自然数です（後でどちらかと言われます_。siは文字列sの i番目の文字のコードです（ほとんどすべての現代言語ではs[i]



と書かれていs[i]



）。



ハッシュには、同じ文字列のハッシュが必ず等しいという特性があります。 したがって、ハッシュで許可される主な操作は、2つの部分文字列の等価性をすばやく比較することです。 もちろん、2行を比較するために、同様の関数を書くことができます（行sとt の長さが一致し、 nに等しいと仮定します）：

 boolean equals(char[] s, char[] t) { for (int i = 0; i < n; i++) if (s[i] != t[i]) { return false; } } return true; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ただし、最悪の場合、この関数はすべての文字をチェックする必要があり、これによりO（n）の漸近的な動作が得られます。

文字列とハッシュの比較

ハッシュがこれをどのように行うかを見てみましょう。 ハッシュは単なる数字であるため、それらを比較するにはO（1）時間が必要です。 確かに、1つの部分文字列のハッシュを単純な方法で計算するには、 O（n）時間が必要です。 したがって、数式を少しいじり、 O（n） のすべての部分文字列のハッシュを一度に見つけることを学ぶ必要があります。 部分文字列s _L..Rとt _X..Y （同じ長さ）を比較してみましょう。 ハッシュ定義を使用して、次のように記述できます。



s _L + ps _{L + 1} + ... + p ^RL-1 s _R-1 + p ^RL s _R = t _X + pt _{X + 1} + ... + p ^YX-1 t _Y-1 + p ^YX t _Y



左側で小さな変換を実行します（右側ではすべてが同様に行われます）。 部分文字列s _0..Rのハッシュを記述します、それが必要です：



ハッシュ（s _0..R ）= s ₀ + ps ₁ + ... + p ^L-1 s _L-1 + p ^L s _L + p ^{L + 1} s _{L + 1} + ... + p ^R-1 s _R-1 + p ^R s _R



この式を2つの部分に分割します...



ハッシュ（s _0..R ）=（s ₀ + ps ₁ + ... + p ^L-1 s _L-1 ）+（p ^L s _L + p ^{L + 1} s _{L + 1} + ... + p ^R-1 s _R-1 + p ^R s _R ）



... 2番目のブラケットから係数p ^Lを抽出します。



ハッシュ（s _0..R ）=（s ₀ + ps ₁ + ... + p ^L-1 s _L-1 ）+ p ^L （s _L + ps _{L + 1} + ... + p ^RL-1 s _R-1 + p ^RL s _R ）



最初の括弧内の式は、部分文字列s _0..L-1のハッシュにすぎず、2番目の式には、部分文字列s _L..Rのハッシュが_必要です。 だから、私たちはそれを得ました：



ハッシュ（s _0..R ）=ハッシュ（s _0..L-1 ）+ p ^Lハッシュ（s _L..R ）



これは、 ハッシュ（s _L..R ）の次の式を意味します。



ハッシュ（s _L..R ）=（1 / p ^L ）（ハッシュ（s _0..R ）-ハッシュ（s _0..L-1 ））



同様に、2番目のサブストリングでは、等式ハッシュ（t _X..Y ）=（1 / p ^X ）（ハッシュ（t _0..Y ）-ハッシュ（t _0..X-1 ））が満たされます。



これらの式を注意深く見ると、部分文字列のハッシュを計算するには、この文字列のプレフィックスのハッシュs _0..0 、 s _0..1 、...、 s _0..n-2 、 s ₀のみを知る必要があることがわかります_{。 .n-1} また、後続の各プレフィックスのハッシュは前のプレフィックスのハッシュを介して表されるため、それらを線に沿った線形の通過としてカウントするのは簡単です。 O（n）時間で一度にすべて。 pのべき乗も事前に計算し、配列に保存する必要があります。



コード例：

 //      p,     pow[0] = 1; for (int i = 1; i <= MAX; i++) { pow[i] = pow[i - 1] * p; } //     s hs[0] = s[0]; for (int i = 1; i < n; i++) { hs[i] = hs[i - 1] + pow[i] * s[i]; } //     t ht[0] = t[0]; for (int i = 1; i < m; i++) { ht[i] = ht[i - 1] + pow[i] * t[i]; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで完全に武装し、 O（1）の部分文字列2を比較できるようになります。 しかし、すべてがそれほど単純なわけではありません。数式にはいくらかの改良が必要です。 たとえば、同様のコード：

 if ((hs[R] - hs[L - 1]) / pow[L] == (ht[Y] - ht[X - 1]) / pow[X]) { ... }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

動作しません。

• 最初のコメント： L （またはX ）はゼロになることがあり、 hs[L - 1]
  
  
  
  計算すると、配列は境界を越えます。 ただし、 Lがゼロの場合、対象の部分文字列s _L..Rのハッシュは、正確にhs[R]
  
  
  
  格納されます。 したがって、 hs[L - 1]
  
  
  
  代わりに次のように記述する方がより正確hs[L - 1]
  
  
  
  。
  
  

   L == 0 ? 0 : hs[L - 1]
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

  。
• 2番目の注意： long
  
  
  
  型でさえ64ビットしか含まず（私はJavaを使用しています）、行は数千の長さになる可能性があり、ハッシュを計算するとき、必然的にオーバーフローが発生します。 この問題を解決する最も簡単な方法は、目を閉じることです。 まあ、またはほぼ近い：実際には、ハッシュはモジュロ2 ⁶⁴と見なされます（したがって、分割の残りの部分を取得する操作を実行する必要はありません-美！）。 計算の数値pは、まず、行の最大文字のコードより大きく、次にモジュールと相互に単純でなければなりません（この場合、2 ^64で 、つまり奇数でなければなりません）。 なぜそうなのか、私はここで話さない-これは代数の本で見つけることができる。 もちろん、衝突の可能性は避けられませんが、それは非常に小さいため、オリンピックの問題を解決するときは、単に無視することができます。
• 3番目のコメント：すべての演算をモジュロで実行するため、除算は使用できません（より正確には、除算は使用可能ですが 、これを書くのはかなり非効率的です）。 したがって、それを取り除く必要があります。 これは、学校が「割合」と呼ぶ方法で非常に簡単に行われます。式は共通分母に縮小され、除算の代わりに乗算が使用されます。
  
  

   if ((hs[R] - (L == 0 ? 0 : hs[L - 1])) * pow[X] == (ht[Y] - (X == 0 ? 0 : ht[X - 1])) * pow[L]) { ... }
        
        
  
          
          
          
        
  
      
          
          
          
        
        
  
          
          
          
        
  
      
       

次に、ハッシュを適用できるタスクを詳しく見ていきます。

ハッシュタスク

1.部分文字列の比較

すでに述べたように、最初の、そして最も重要なアプリケーションは、2つのサブストリングの迅速な比較です。ハッシュを使用する他のすべてのアルゴリズムはそれに基づいています。 最後のセクションのコードはやや面倒なので、今後使用するより便利なコードを作成します。

次の関数は、部分文字列s _L..Rにp ^Lを掛けたハッシュを計算します。

 long getHash(long[] h, int L, int R) { long result = h[R]; if (L > 0) result -= h[L - 1]; return result; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、2つの部分文字列を次の行と比較します。

 if (getHash(hs, L, R) * pow[X] == getHash(ht, X, Y) * pow[L]) { ... }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

pの累乗による乗算は、「1つの累乗への縮小」と呼ばれます。 最初のハッシュはp ^Lで乗算され、2番目のハッシュはp ^Xで乗算されます。これは、比較が正しいことを意味します。欠落している係数を乗算する必要があります。

注：部分文字列の長さが一致しているかどうかを最初に確認することは理にかなっています。 そうでない場合、原則として行を等しくすることはできず、上記の条件を確認することはできません。

2. O（n + m）の文字列で部分文字列を検索します

ハッシュを使用すると、文字列内の部分文字列を漸近的に最小限の時間で検索できます。 これは、いわゆるRabin-Karpアルゴリズムによって行われます。

長さmの文字列tのすべての出現を検索する長さnの文字列sがあるとします。 文字列tのハッシュ（文字列全体）と文字列sのすべての接頭辞のハッシュを_{見つけたら} 、部分文字列s _{i..i + m-1を}比較して、長さmのウィンドウで文字列sに沿って移動します。

コード：

 //    t long ht = t[0]; for (int i = 1; i < m; i++) { ht += pow[i] * t[i]; } //    for (int i = 0; i + m <= n; i++) { if (getHash(h, i, i + m - 1) == ht * pow[i]) { //     i } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

3. O（n log n）でz関数を見つける

文字列s のz関数は 、 i番目の要素が文字列sの位置iから始まる部分文字列の最長プレフィックスに等しい配列zであり、これは文字列s全体のプレフィックスでもあります。 ゼロの位置にあるz関数の値は、文字列sの長さと等しいと見なされますが、一部のソースではゼロと見なされます（ただし、これは重要ではありません）。



もちろん、 O（n）の z関数を見つけるアルゴリズムがあります 。 しかし、あなたが知らない、または覚えていない（そしてアルゴリズムがやや面倒な）場合、ハッシュが助けになります。



アイデアは次のとおりです。各i = 0、1、...、n-1に対して_、バイナリ検索_によって z _iを検索します。 各反復で、可能な値の範囲を半分にします。 等式s _0..k-1 = s _{i..i + k-1}は、 z _i未満のすべてのkに対して必然的に成り立ち、大きなkに対しては成り立ちません。



コード：

 int[] z = new int[n]; for (int i = 0; i < n; i++) { int left = 1, right = n - i; //    while (left <= right) { //  middle -   int middle = (left + right) / 2; //  ,    s[0..middle-1]  s[i..i+middle-1] if (getHash(h, 0, middle - 1) * pow[i] == getHash(h, i, i + middle - 1)) { //  ,      middle,      z[i] = middle; left = middle + 1; } else { //   ,     right = middle - 1; } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

4. O（n log n）で辞書編集的に最小の循環改行を検索します 。

O（n）でこの問題を解決できるDuvalアルゴリズムがありますが、それを理解していないかなり強力なOlympiadプログラマを知っています。 彼らがそれを理解している限り、再びハッシュを使用します。



アルゴリズムは次のとおりです。 まず、最良の（辞書編集的に最小限の）答えを得るためにstringを使用します。 次に、各巡回シフトについて、バイナリ検索を使用して、このシフトの最大共通プレフィックスの長さと現在のベストアンサーを見つけます。 その後、このプレフィックスに続く文字を比較し、必要に応じて回答を更新するだけで十分です。

また、便宜上、文字列sをそれ自体に帰属させることをお勧めします。文字列sの文字にアクセスするときにモジュロ演算を行う必要はありません。 これはすでに行われていると想定しています。



コード：

 int bestPos = 0; for (int i = 1; i < n; i++) { int left = 1, right = n, length = 0; //  length -     while (left <= right) { int middle = (left + right) / 2; if (getHash(h, bestPos, bestPos + middle - 1) * pow[i] == getHash(h, i, i + middle - 1) * pow[bestPos]) { length = middle; left = middle + 1; } else { right = middle - 1; } } //          //      n, //       , //      if (length < n && s[i + length] < s[bestPos + length]) { bestPos = i; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

注：実際、コンパレータは辞書式に2つの循環シフトを比較するfor



ループ内に記述されてfor



ます。 これを使用すると、 O（n log ² n）のすべての巡回シフトをソートできます 。

5. O（n log n）の行ですべての回文を検索します 。

繰り返しますが、この問題の解決策はO（n）にあります。 そして再び、ハッシュでそれを解決します。



部分文字列s _L..Rは、 s _L = s _R 、 s _{L + 1} = s _R-1などの場合、回文と呼ばれます。 ロシア語で言えば、左から右へ、右から左へ同じように読まれることを意味します。



おそらく、ハッシュがそれと何の関係があるのか​​をすでに知っているか、推測しているでしょう。 部分文字列s _0..0 、 s _0..1 、...、 s _0..n-2 、 s _0..n-1のハッシュを含む配列h[]



加えて、2番目の配列rh[]



（ 「反転」線）、これを右から左に移動します。 それに応じて、ハッシュs _0..n-1 、 s _1..n-1 、...、 s _n-2..n-1 、 s _{n-1..n-1が含まれ}ます。

 rh[n - 1] = s[n - 1]; for (int i = n - 2, j = 1; i >= 0; i--, j++) { rh[i] = rh[i + 1] + pow[j] * s[i]; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

O（1）の後の文字列が回文であるかどうかを判断する方法はすでに明確になっているはずです。 getHash（）と同様のgetRevHash（）関数を作成し、必要な比較条件を指定します。 この式の正確性は、記事の冒頭で示したものと同様の数学的計算を行うことで独立して検証できます。

 long getRevHash(long[] rh, int L, int R) { long result = rh[L]; if (R < n - 1) result -= rh[R + 1]; return result; } boolean isPalindrome(long[] h, long[] rh, long[] pow, int L, int R) { return getHash(h, L, R) * pow[n - R - 1] == getRevHash(rh, L, R) * pow[L]; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

次に、行のiの位置を検討します。 位置iを中心とする奇数の長さdのパリンドロームがあるとします（偶数の場合、位置i-1とiの間を中心とします）。 1つのキャラクターを端から切り取ると、パリンドロームのままになります。 そして、その長さがゼロになるまで継続できます。

したがって、各位置に2つの値を格納するだけで十分です。位置iに中心を持つ奇数長のパリンドロームがいくつ存在するか、位置i-1とiの間に中心がある偶数長のパリンドロームがいくつあります。 これら2つの値は互いに完全に独立しているため、別々に処理する必要があることに注意してください。



前と同様に、バイナリ検索を適用します。

 int[] oddCount = new int[n]; for (int i = 0; i < n; i++) { int left = 1, right = min(i + 1, n - i); while (left <= right) { int middle = (left + right) / 2; if (isPalindrome(h, rh, pow, i - middle + 1, i + middle - 1)) { oddCount[i] = middle; left = middle + 1; } else { right = middle - 1; } } } int[] evenCount = new int[n]; for (int i = 0; i < n; i++) { int left = 1, right = min(i, n - i); while (left <= right) { int middle = (left + right) / 2; if (isPalindrome(h, rh, pow, i - middle, i + middle - 1)) { evenCount[i] = middle; left = middle + 1; } else { right = middle - 1; } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これで、たとえば、行内のすべての回文の総数、または最大回文の長さを見つけることができます。 位置iを中心とする最大奇数パリンドロームの長さは2 * oddCount[i] - 1



、最大偶数パリンドロームは2 * evenCount[i]



です。

偶数および奇数の長さの回文にはさらに注意する必要があることをもう一度思い出させてください。原則として、それらは互いに独立して処理されなければなりません。

マトリックスハッシュ

最後に、ハッシュのより洗練された使用を検討してください。 これで、空間が2次元になり、部分行列を比較します。 幸いなことに、ハッシュは2次元の場合に非常によく一般化されています（3次元以上を見たことはありません）。



数字pとpow



配列の代わりに、2つの異なる数字p 、 qと2つのpow1



、 pow2



。それぞれの方向に1つの数字と1つの配列があります。



ハッシュ行列a _{0..n-1、0..m-1}は、量p ⁱ q ^j aのすべてのi = 0、...、n-1 、 j = 0、...、m-1の合計と呼ばれます。 _ij 。



ここで、左上の要素a ₀₀を含む部分行列のハッシュをカウントする方法を学びます。 明らかに、 ハッシュ（a _0..0、0..0 ）= a ₀₀ 。 ほとんどすべてのj = 1、...、m-1 hash（a _0..0、0..j ）= hash（a _{0..0、0..j-1} ）+ q ^j a _0j 、すべてのi = 1、...、n-1 hash（a _0..i、0..0 ）= hash（a _{0..i-1、0..0} ）+ p ⁱ a _i0 。 これは、1次元の場合から直接続きます。



_{サブマトリックス} a _{0..i、0..jの}ハッシュを計算する方法は？ ハッシュ（ _0..i、0..j ）=ハッシュ（a _{0..i-1、0..j} ）+ハッシュ（a _{0..i、0..j-1} ）-ハッシュ（a _{0..i-1、0..j-1} ）+ p ⁱ q ^j a _ij 。 この式は、次の考慮事項から取得できます。 _{サブマトリックス} a _{0..i-1、0..j}および_{0..i、0..j-1の}ハッシュを構成するすべての用語を加算します（ハッシュ、これはいくつかの用語の合計です）。 。 同時に、部分行列a _{0..i-1、0..j-1}を構成する項を2回考慮したので、それらを1回考慮するように減算します。 ここで、要素a _ijに対応するpとqのべき乗を掛けたもののみが欠落しています。



記事の最初の部分とほぼ同じ理由で（包含/除外式の関与にすでに気付いていますか？）、任意の部分行列a _{x1..x2、y1..y2の}ハッシュを計算する関数が構築されます。

 long getMatrixHash(long[][] h, int x1, int x2, int y1, int y2) { long result = h[x2][y2]; if (x1 > 0) result -= h[x1 - 1][y2]; if (y1 > 0) result -= h[x2][y1 - 1]; if (x1 > 0 && y1 > 0) result += h[x1 - 1][y1 - 1]; return result; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この関数は、部分行列a _{x1..x2、y1..y2} ^× p ^x1 q ^y1のハッシュを返します。



2つの部分行列_{ax1..ax2、ay1..ay2}と_{bx1..bx2、by1..by2の比較}は、次の式を使用して実行されます。

 if (getMatrixHash(h, ax1, ax2, ay1, ay2) * pow1[bx1] * pow2[by1] == getMatrixHash(h, bx1, bx2, by1, by2) * pow1[ax1] * pow2[ay1]) { ... }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ハッシュはまた、最大の対称部分行列を見つけることに関連する問題を解決できます。 また、この作業を実行するアルゴリズムが、スピードと単純さの点でハッシュに匹敵するものかどうかもわかりません。 ここでは、1次元の場合のパリンドロームの検索と同じ原理が使用されます（つまり、右から左、下から上へ「逆」ハッシュをカウントし、偶数と奇数の長さの部分行列に対して別々にビン検索を実行します）。 この問題を自分で解決することをお勧めします-この記事は役に立ちます！

おわりに

したがって、自由に使用できる非常に優れた装置があり、可能な限り最高の漸近法を使用するか、専用アルゴリズムよりもわずかに（対数倍）遅いだけで多くのことを実行できます。 悪くないですか？