【アルゴリズム(JS実装)】Rabin-Karp Algorithm - 医学生わくばの欲張り技術ブログ

　どうも、わくばです！

　今回はRabin-Karp algorithmです。どんどん重たくなってきたので、日をまたがないとできなくなってきました(汗)。まだまだですね。。。

　Rabin-Karp algorithmはハッシュ関数を用いたマッチングアルゴリズムです。ハッシュ関数というのは暗号化というか何らかの値を返す

たとえば探している文字列をaaabとし、検索対象の文字列をabaaaaabaaababaabなどとした場合、まずは探したいaaabという文字列をハッシュ関数に掛け数値化(出力Xが得られたとする)します。そして

検索対象のアルゴリズムから、最初の4文字をとってきてハッシュ関数にかける。
その値が探したい文字列のハッシュ値Xと等しければ、更にその部分の文字列と、位置文字ずつ照らして本当に等しいか確認する。
ハッシュ値が違えば、一文字ずらして手順1からまた繰り返す。

　ハッシュ関数として用いられる代表的なものは以下のようなものです。

　$f(aaab)=A*n^3+A*n^2+A*n^1+B*n^0$ (Aは文字aの文字コードを意味する)

　n進数的な表現ですね。用いる文字の種類が10種類ならばn=10、26種類ならn=26とするなど、状況に応じて変更可能です。

　このアルゴリズムはRolling Hash Algorithmと呼ばれることもあるのですが、これは検索対象の文字列をスキャンしてハッシュ値を出していくときに、前の値を使いながら計算していくためです。例えばabaaaaabaaababaabをスキャンしていくとき、二回目のbaaaを算出する時に一個前のabaaを用いて算出します。

　より詳細の説明は以下の動画の16分くらいからが非常に参考になります。

youtu.be

　式で言うとこんな感じです。

$$ f(baaa)=(f(abaa)-\color{red}{ A*n^3 })*10+\color{green}{A*n^0} $$

赤い部分は$f(abaa)$の一行目を削除していて、緑の部分で新しいものを足しています。

実際はこれだと桁が大きくなりオーバーフローを起こす場合があるのでコードではmodを用います。

コードは以下のようになります

const d = 256;
const search = (pat, txt, q) => {
    const patL = pat.length;
    const txtL = txt.length;
    let pHash = 0; 
    let tHash = 0;
    let h = 1;
    for (let i=0; i<patL-1; i++) {
        h = (h*d)%q; 
    } 

    //patternとtextのハッシュ値を算出
    //textについては最初のやつのみ。後で漸化的に更新するため
　　 //qで割ったあまりを使うバージョン
    for (let i=0; i<patL; i++) {
        pHash = (d*pHash + pat.charCodeAt(i))%q;
        tHash = (d*tHash + txt.charCodeAt(i))%q; 
    }

    //一致するインデックスを最後に返すための配列
    let result = [];

    //探索を開始
    for (let i=0; i<txtL-patL+1; i++) {
        //最初のハッシュ値が一緒なら
        //それを確かめる。Naiveのやり方と同じ
        if (pHash===tHash) {
            let matchCount =0;
            for (let j=0; j<patL; j++) {
                if (txt[i+j] !== pat[j]) {
                    break;
                } else {
                    matchCount++;
                }
            }
            if (matchCount==patL) {
                result.push(i);
            }
        }
        //最後まで言っていなければtHashを更新して次のループへ
        if (i < txtL-patL) {
            //ここで一個前のtHashを用いて更新
            tHash = (d*(tHash-txt.charCodeAt(i)*h) + txt.charCodeAt(i+patL))%q;
            if (tHash < 0) {
                tHash += q;
            } 
        } 
    }
    return result;
}

　いくつか補足をします。

　まず以下の部分

for (let i=0; i<patL; i++) {
        pHash = (d*pHash + pat.charCodeAt(i))%q;
        tHash = (d*tHash + txt.charCodeAt(i))%q; 
    }

は上で説明したmodバージョンでのことです。%qというのはqで割ったあまりです。こいつはわざわざforループを用いて何をやってるんだと思うかもしれませんが、aaabを例にすると結局$(A*d^3 + A*d^2+A*d^1+B*d^0)\%q$と同じ値になります。この記述だと記述時に文字列の長さをわかってないと書けませんから、入力に応じて動的に算出できません。しかし上のコードのようにすればforループの回数を制御すればよいですから動的に変更できます。

　なぜああ書けるのか説明します。Aをqで割った時の商をu、あまりをvとすると、A = uq + vとかけるので

　pHash_1 = (d * pHash_0 + A) % q

= (d * pHash_0 + A) - uq

= A -uq (pHash_0はもともと0なので)

　pHash_2 = (d * pHash_1 + A) % q

= {d * (A -uq) + A} % q

= {d * (A -uq) + A} - u'q

= d * A + A - q(du + u')

　pHash_3 = (d * pHash_2 + A) % q

= {d *(d * A + A - q(ud + u') )+ A} % q

={ d^{2} A + dA + A - q(d^{2}u + u'd)} % q

= { d^{2} A + dA + A -q(d^{2}u + u'd)} - u''q

= d^{2} A + dA + A - q(d^{2}u + u'd + u'')

　pHash_4 = (d * pHash_3 + B) % q

= {d * {d^{2} A + dA + A - q(d^{2}u + u'd + u'')} + B } % q

= { d^{3} A + d^{2} A + dA + B -q(d^{3}u + u'd^{2} + u''d ) } % q

　したがって

　$(A*d^3 + A*d^2+A*d^1+B*d^0)\%q$と同じ結果になります。

　次は以下の部分です。

 tHash = (d*(tHash-txt.charCodeAt(i)*h) + txt.charCodeAt(i+patL))%q;

　これはmodバージョンによる更新になります。

　基本的には上の方で説明したとおり、ハッシュ値を出すとき一番くらいの大きい項を削除して新しい項を追加しますが、わかりにくいのは以下のhです

　txt.charCodeAt(i)*h

　これは例えば文字列aaabを考えると上のpHashの結果から

　{ d^{3} A + d^{2} A + dA + B -q(d^{3}u + u'd^{2} + u''d ) } % q

　= d^{3} A + d^{2} A + dA + B -q(d^{3}u + u'd^{2} + u''d + u''' )

ここから先頭を差し引くにはd^{3} Aを引かなければなりませんがtxt.charCodeAt(i)のみではAにしかなりませんからd^{3}の部分をhとして計算してあるわけです。以下のコードの部分ですね。

for (let i=0; i<patL-1; i++) {
        h = (h*d)%q; 
    }

長々とした説明になりましたが、理解できましたでしょうか。疑問点や誤植などありましたらお気軽にコメント下さい。

　最後に時間計算量ですが探したい文字列の長さをm、検索対象の文字列の長さをnとすると$O(n+m)$になります。ハッシュがマッチしたときだけ追加でm回ループが必要ってことですね。最悪の場合はいちいちハッシュがマッチするのでほぼNaive アルゴリズムみたいな感じになります。

　では。