ローリングハッシュ

ローリング ハッシュ(再帰ハッシュまたはローリング チェックサムとも呼ばれます) は、入力を移動するウィンドウ内で入力がハッシュされる ハッシュ関数です。

いくつかのハッシュ関数を使用すると、ローリング ハッシュを非常に高速に計算できます。つまり、古いハッシュ値、ウィンドウから削除された古い値、ウィンドウに追加される新しい値のみを指定して、新しいハッシュ値を迅速に計算できます。これは、移動平均関数が他のローパス フィルターよりもはるかに高速に計算できる方法と似ています。また、ゾブリスト ハッシュが古いハッシュ値から 迅速に更新される方法と似ています。

主なアプリケーションの 1 つは、以下で説明するローリング ハッシュを使用するRabin–Karp 文字列検索アルゴリズムです。もう 1 つの一般的なアプリケーションは、Mark Adler のadler-32に基づくチェックサムをローリング ハッシュとして使用するrsyncプログラムです。Low Bandwidth Network Filesystem (LBFS) は、Rabin フィンガープリントをローリング ハッシュとして使用します。FastCDC (Fast Content-Defined Chunking) は、計算効率の高い Gear フィンガープリントをローリング ハッシュとして使用します。

ローリングハッシュ値は、せいぜいペアワイズ独立^[1]または強く普遍的である。例えば、 3ワイズ独立であることはできない。

Rabin-Karp 文字列検索アルゴリズムは、乗算と加算のみを使用するローリング ハッシュ関数を使用して説明されることが多いです。

${\displaystyle H=c_{1}a^{k-1}+c_{2}a^{k-2}+c_{3}a^{k-3}+...+c_{k}a^{0}}$、

ここで、 は定数、 は入力文字です (ただし、この関数はRabin フィンガープリントではありません。下記を参照してください)。 ${\displaystyle a}$${\displaystyle c_{1},...,c_{k}}$

巨大な値の操作を避けるため、すべての計算はを法として行われます。 と の選択は、適切なハッシュを得るために重要です。特に、法は通常素数です。詳細については、 線形合同法ジェネレータを参照してください。${\displaystyle H}$ ${\displaystyle n}$${\displaystyle a}$${\displaystyle n}$${\displaystyle n}$

文字の削除と追加は、最初または最後の項を加算または減算するだけです。すべての文字を 1 つ左にシフトするには、合計全体を で乗算する必要があります。すべての文字を 1 つ右にシフトするには、合計全体を で除算する必要があります。モジュロ演算では、 を選択して乗法逆数にすることができ、これを で乗算すると、実際に除算を実行せずに除算の結果を得ることができます。 ${\displaystyle H}$${\displaystyle a}$${\displaystyle H}$${\displaystyle a}$${\displaystyle a}$ ${\displaystyle a^{-1}}$${\displaystyle H}$

ラビンフィンガープリントは別のハッシュで、これも入力を多項式として解釈しますが、ガロア体 GF(2)上の多項式として解釈します。入力をバイトの多項式として見るのではなく、ビットの多項式として見なし、すべての演算は GF(2) で行われます ( CRC32と同様)。ハッシュは、その多項式を GF(2) 上の既約多項式で割った結果です。入力バイトと出力バイトのみを使用してラビン フィンガープリントを更新できるため、実質的にローリング ハッシュになります。

このアルゴリズムは、別のより単純なローリングハッシュで説明されることが多いラビン・カープの文字列検索アルゴリズムと同じ作者によるものであり、このより単純なローリングハッシュも多項式であるため、両方のローリングハッシュはしばしば互いに間違えられる。バックアップソフトウェアresticは、ファイルを分割するためにラビンフィンガープリントを使用し、ブロブサイズは512KiBから8MiBまで変化する。^[2]

巡回多項式^[3]によるハッシュ法（Buzhash と呼ばれることもある）も単純で、乗算を避け、代わりにバレルシフトを使用するという利点がある。これはタブレーションハッシュ法の一種で、区間 内に文字から整数へのハッシュ関数が存在することを前提としている。このハッシュ関数は、文字をランダムな整数にマッピングする単なる配列またはハッシュテーブルである可能性がある。関数 を巡回バイナリ回転（または循環シフト）とする。これはビットを 1 ずつ左に回転し、最新のビットを最初の位置にプッシュする。たとえば、 である。をビットごとの排他的論理和 とする。ハッシュ値は次のように定義される。 ${\displaystyle h}$${\displaystyle [0,2^{L})}$${\displaystyle s}$${\displaystyle s(101)=011}$${\displaystyle \oplus}$

${\displaystyle H=s^{k-1}(h(c_{1}))\oplus s^{k-2}(h(c_{2}))\oplus \ldots \oplus s(h(c_{k-1}))\oplus h(c_{k}),}$

ここで、2 の累乗による乗算は、バイナリ シフトによって実装できます。結果は の数値になります。 ${\displaystyle [0,2^{L})}$

ローリング方式でハッシュ値を計算するには、次のようにします。 を前のハッシュ値とします。 を1 回回転させます: 。が削除する文字である場合、 を回回転させます: 。次に、 と設定します。 ${\displaystyle H}$${\displaystyle H}$${\displaystyle H\leftarrow s(H)}$${\displaystyle c_{1}}$${\displaystyle k}$${\displaystyle s^{k}(h(c_{1}))}$

${\displaystyle H\leftarrow s(H)\oplus s^{k}(h(c_{1}))\oplus h(c_{k+1}),}$

新しいキャラクターは どこですか。${\displaystyle c_{k+1}}$

巡回多項式によるハッシュは、強く普遍的またはペアワイズ独立です。つまり、最初のビットだけを保持します。つまり、結果を取得し、連続するビットを無視します。^[1]実際には、これは整数除算によって実現できます。 ${\displaystyle L-k+1}$${\displaystyle H}$${\displaystyle k-1}$${\displaystyle H\rightarrow H\div 2^{k-1}}$

ローリングハッシュ関数の興味深い使用例の 1 つは、ストリームまたはファイルのコンテンツベースの動的チャンクを作成できることです。これは、大きなファイルの変更されたチャンクのみをネットワーク経由で送信する必要がある場合に特に便利です。ファイルの先頭に単純なバイトを追加すると、通常はすべての固定サイズのウィンドウが更新されますが、実際には最初の「チャンク」のみが変更されます。^[4]

動的チャンクを作成する簡単な方法は、ローリング ハッシュを計算し、ハッシュ値が下位Nビットの任意のパターン (すべてゼロなど) と一致する場合 (ハッシュが均一な確率分布を持つ場合、確率は )、それがチャンク境界として選択されることです。したがって、各チャンクの平均サイズはバイトになります。この方法により、変更されていないデータ (変更からウィンドウ サイズ以上離れているもの) が同じ境界を持つことが保証されます。 ${\textstyle {1 \over 2^{n}}}$${\textstyle 2^{n}}$

境界がわかったら、変更を検出するためにチャンクを暗号ハッシュ値で比較する必要があります。^[5]バックアップソフトウェアBorgは、ファイルストリームを分割するためにカスタマイズ可能なチャンクサイズ範囲を備えたBuzhashアルゴリズムを使用します。^[6]

このようなコンテンツ定義のチャンク化は、データの重複排除によく使用されます。^{[4] [6]}

gzip（--rsyncableオプション付き）やrsyncrytoを含むいくつかのプログラムは、この特定の（重み付けされていない）移動合計に基づいてコンテンツベースのスライスを実行します。^[7]

${\displaystyle S(n)=\sum _{i=n-8195}^{n}c_{i},}$

${\displaystyle H(n)=S(n)\mod 4096,}$

どこ

• ${\displaystyle S(n)}$バイトで終わる8196個の連続バイトの合計です（21ビットの記憶域が必要です）。${\displaystyle n}$
• ${\displaystyle c_{i}}$ファイルのバイト数です。${\displaystyle i}$
• ${\displaystyle H(n)}$は、の下位 12 ビットで構成される「ハッシュ値」です。${\displaystyle S(n)}$

ウィンドウを 1 バイトシフトするには、新しい文字を合計に追加し、最も古い文字 (ウィンドウ内にはもう存在しない文字) を合計から減算するだけです。

の場合、これらのプログラムはファイルをと の間で切り取ります。このアプローチにより、ファイル内の変更が現在のチャンクと次のチャンクにのみ影響し、他のチャンクには影響しないことが保証されます。 ${\displaystyle n}$${\displaystyle H(n)==0}$${\displaystyle n}$${\displaystyle n+1}$

チャンキングは、データ ストリームをチャンクとも呼ばれるブロックのセットに分割する手法です。コンテンツ定義チャンキング (CDC) は、固定サイズのチャンキングのように固定チャンク サイズではなく、そのコンテンツに基づいてデータ ストリームを分割するチャンキング手法です。

コンテンツ定義チャンク化アルゴリズムは、データストリームのハッシュ値をバイトごとに計算し、ハッシュ値が定義済みの値に一致するとデータストリームをチャンクに分割する必要があります。しかし、文字列をバイトごとに比較すると、計算のオーバーヘッドが大きくなります。FastCDC ^[8]は、新しい効率的なコンテンツ定義チャンク化アプローチを提案しています。これは、高速ローリングギアハッシュアルゴリズムを使用し、^[9]最小長をスキップし、チャンクサイズ分布を正規化し、最後に、毎回2バイトをローリングしてCDCアルゴリズムを高速化し、RabinベースのCDCアプローチよりも約10倍高いスループットを実現できます。^[10]

基本バージョンの疑似コードは次のように提供されます。

アルゴリズムFastCDC
    入力:データ バッファsrc、
           データ長n、 
    出力:カットポイントi
    
    MinSize ← 2KB // 分割の最小チャンクサイズは 2 KB
     MaxSize ← 64KB // 分割の最大チャンクサイズは 64 KB
     Mask ← 0x0000d93003530000LL 
    fp ← 0 
    i ← 0
    
    // バッファサイズが最小チャンクサイズより小さい
     n ≤ MinSize の場合は
        nを返し、 n ≥ MaxSizeの場合はn ← MaxSizeを返します。 
      
        
    
    // 最初のMinSizeバイトをスキップし、ハッシュを開始します
    while  i < MinSize  do 
        fp ← ( fp << 1 ) + Gear [ src [ i ]]
         i ← i + 1
     
     i < n の場合、fp ← ( fp << 1 ) + Gear [ src [ i ]]
        を実行し
        、  !( fp & Mask )の場合、i を返します。 i ← i + 1
             
        
   
    戻る ​

ここで、Gear配列は事前に計算されたハッシュ配列です。FastCDCは、ローリングハッシュ結果を迅速に計算し、ハッシュ結果の均一な分布をRabinとして維持できるGearハッシュアルゴリズムを使用します。従来のRabinハッシュアルゴリズムと比較して、はるかに高速です。実験では、データストリームをセグメント化するときに、はるかに短い時間（Rabinベースのチャンク化^[10]の約1/10 ）でほぼ同じチャンクサイズ分布を生成できることが示唆されています。

すべてのローリングハッシュ関数は、文字数に比例した時間で計算でき、文字が1つシフトすると定数時間で更新されます。特に、長さの文字列のRabin-Karpローリングハッシュを計算するにはモジュラー算術演算が必要であり、巡回多項式によるハッシュにはビットごとの排他的論理和と循環シフトが必要です。^[1]${\displaystyle k}$${\displaystyle O(k)}$${\displaystyle O(k)}$

• MinHash  – データマイニング技術
• W-シングル

• MIT 6.006: アルゴリズム入門 2011 - 暗唱 9 - ローリングハッシュ