可変長データのハッシュ技法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/02 09:30 UTC 版)
「ハッシュ関数」の記事における「可変長データのハッシュ技法」の解説
データが非常に長い（または可変長の）文字列の場合（人名、URL、電子メールの中身など）、その分布は一様でないことが多く、複雑な依存関係が存在することが多い。例えば、自然言語の文章では文字の分布は全く一様ではないし、文字の並び方にも相関関係があり、その言語に特有の性質を持っている。その場合、ハッシュ関数は文字列内の全文字を何らかの形で使用し、しかもそれぞれの文字を異なった形で使用するのが望ましい。 そのようなデータをハッシュ値に変換する典型的手法は、入力を小さな単位（数ビット、数バイト、数ワードなど）の並び b[1], b[2], …, b[m] に分割し、それを順に以下のように結合していく。 def make_hash(S0, b) S <- S0 // 状態を初期化 for k in 1..m do // 入力データ単位をスキャン: S <- F(S, b[k]) // データ単位 k を状態に結合 end return G(S, n) // 状態からハッシュ値を抽出end この手法は、テキストのチェックサムやフィンガープリントのアルゴリズムにも利用されている。状態変数 S は32ビットか64ビットの符号無し整数である。例の場合、S0 は 0 でよいし、G(S,n) は単に S mod n でよい。最適な F の選択は難しい問題で、データの性質にも依存する。データ単位 b[k] が1ビットなら、F(S,b) は例えば次のようになる。 def F(S, b) return if highbit(S) == 0 then 2 * S + b else (2 * S + b) ^ Pend ここで highbit(S) は S の最上位ビットを意味し、'*' 演算子は符号無しの整数の乗算でオーバーフローを無視する操作を表す。'^' はビット単位の排他的論理和演算を表し、P は適当な固定のワードである。
※この「可変長データのハッシュ技法」の解説は、「ハッシュ関数」の解説の一部です。
「可変長データのハッシュ技法」を含む「ハッシュ関数」の記事については、「ハッシュ関数」の概要を参照ください。
- 可変長データのハッシュ技法のページへのリンク
