2

I'm trying to optimize a program which needs to compute a hash for a constant size window in a data stream at every position (byte) of stream. It is needed for a lookup of repetitions in disk files much larger than available RAM. Currently I compute separate md5 hash for every window, but it costs a lot of time (window size is a few kilobytes, so each byte of data is processed few thousand times). I wonder if there exist a way to compute every subsequent hash in constant (window-size-independent) time (like addition and subtraction of 1 element in moving average)? The hash function may be anything as long as it gives not to long hashes (50-100 bits is ok) and its computation is reasonably fast. It also must give virtually no colisions on up to trillions of not-so-random windows (TB of data) - every collision means a disk access in my case (crc32 is much to weak, md5 is OK in this aspect).

Linux で利用できる既存のライブラリ関数があれば教えていただければ幸いです。

これは私の最初の質問なので、何か間違ったことをした場合はご容赦ください。

よろしく、バルトス

4

2 に答える 2

3

ローリングハッシュに関するウィキペディアの記事には、C++でいくつかの異なる手法を実装するngramhashingへのリンクがあります。

  • ランダム化されたKarp-Rabin（Rabin-Karpと呼ばれることもあります）
  • 循環多項式によるハッシュ（Buzhashとも呼ばれます）
  • 既約多項式によるハッシュ

（GitHubでも利用可能）

于 2013-01-11T15:06:41.123 に答える
2

あなたが説明することは、データ重複排除ストレージで使用される基本的なアプローチにかなり近いものです。

データ重複排除システムでは、通常、Rabinのフィンガープリント方式を高速のローリングハッシュ関数として使用します。ただし、Rabinフィンガープリントは優れた、よく理解されている衝突特性ですが、暗号的に安全ではありません。つまり、衝突が発生します。たとえば、Bentleyetal。彼らの圧縮方法でそのような方法を使用しました。問題は、どの程度の衝突に耐えられるかということです。時折発生する衝突に耐えられる場合は、Rabinフィンガープリントを適切に実装することをお勧めします。優れた実装では、コアあたり1秒あたり200MB以上を処理できます。

私は、衝突が事実上なく（暗号的に安全である）、同時にローリングするアプローチを認識していません。PlasmaHHとして、私はこれが実際に可能であることに深刻な疑問を抱いています。

制限を緩和できるかどうか考えてください。たぶん、あなたはいくつかの重複を見逃すことを許すことができます。このような場合、より高速な方法が可能です。

于 2013-01-11T15:33:12.757 に答える