Algorithm::RabinKarp - Rabin-Karp streaming hash

Location : Home > Languages > Perl > Package
Title : Algorithm::RabinKarp

　Algorithm::RabinKarp - Rabin-Karp ストリーミングハッシュを計算

my $text = "A do run run run, a do run run";
my $kgram = Algorithm::RabinKarp->new($window, $text);

　または

my $kgram2 = Algorithm::RabinKarp->new($window, $fh);

　または

my $kgram3 = Algorithm::RabinKarp->new($window, sub {
  ...
  return $num, $position;
});

my ($hash, $start_position, $end_position) = $kgram->next;

my @values = $kgram->values;

my %occurances; # a dictionary of all kgrams.
while (my ($hash, @pos) = @{shift @values}) {
  push @{$occurances{$hash}}, \@pos; 
}

my $needle = Algorithm::RabinKarp->new(6, "needle");
open my $fh, '<', "haystack.txt";
my $haystack = Algorithm::RabinKarp->new(6, $fh);
my $needle_hash = $needle->next;

while (my ($hay_hash, @pos) = $haystack->next) {
  warn "Possible match for 'needle' at @pos" 
    if $needle_hash eq $hay_hash;
}

説明

　これは Rabin 及び Karp が "Winnowing: Local Algorithms for Document Fingerprinting" （Schleimer, Wilkerson, and Aiken 著）で提唱したストリーミングハッシュの実装である。Schleimer の示唆に従い、第2式を採用している。

$H[ $c[2..$k + 1] ] = (( $H[ $c[1..$k] ] - $c[1] ** $k ) + $c[$k+1] ) * $k

　このハッシュの結果は、ストリームにおける次の k 個の値の情報をコード化する（ここから k-gram と言う）。これは長さ n の整数値（または文字）に対し n - k + 1 の長さのハッシュを返すことを意味する。
　最良の結果を出すには、ユーザのデータから不要な情報を削除するフィルタの役目を果たすコード生成器を考えるとよいだろう。たとえば長大な英語の文書から全ての空白と大文字を削除するようなものを考えればよい。

意図

　Rabin Karp ハッシュアルゴリズムでユーザの文書を前処理することにより、文書の「指紋」を作成することが可能になり、複数の文書データベース中に散在している語句を検索することが容易になる。
　Schleimer, Wilkerson, Aiken は（空白などの）不要な情報やや著作権表示など区まり文句などの冗長な情報をを前処理で削除しておくことを示唆している。
　また著者らは選別（winnowing）と呼ばれるテクニックを用いて後処理を施しデータ量を削減することを勧めている。（詳しくは本文書末尾のリンク先を参照のこと。）

メソッド

new($k, [FileHandle|Scalar|Coderef] )

　新たなハッシュ生成器を生成する。callback 関数を陥ればストリームにおける次の整数値を返さねばならない。ストリームにおける元の位置を返してもよい。（すなわち冗長ならば文字をフィルタリングしてもよい。）

next()

　呼び出されるたびに k-gram ハッシュ値・開始位置・終了位置を返す。ストリームの最後に達した場合には () を返す。
　next() は最初に呼び出されたときにはストリームの最初の $k 個の値を取得し、その後は next() は O(1) の計算量である。

values

　データストリームに含まれる n - k + 1 個のハッシュ値及び関連する位置を含む配列を返す。（next|/METHODS と同じフォーマットである。）
　次々に values() 及び next() を呼び出し undef を返すため、values() が呼び出された後ではストリームは最後まで利用される。

注意：
　values() は貪欲に全ての値を利用しようとするので、データストリームが限りなく長いのであるならば next を用いるべきである。

バグ

　現在の乗数や法は非常に貧弱なハッシュしか提供していない。さらによい手法を確認して将来のバージョンで改善する。

参考資料

　"Winnowing: Local Algorithms for Document Fingerprinting"
　http://theory.stanford.edu/~aiken/publications/papers/sigmod03.pdf

著者

　Norman Nunley, nnunley@gmail.com
　Nicholas Clark （私とぺアである）

Updated : 2006/09/26