【アルゴリズム(JS実装)】Knuth Morris Pratt Algorithm

 どうも、わくばです！

　今回はKMP algorithmです。これは意味がわかるまでかなり時間かかってしまいました。なんとなく言いたいことはわかるんですけど、それをアルゴリズムに起こすときにハテナが大量に(笑)

　KMPは前処理部分と探索部分に分かれていて、探索部分はすぐしっくりきたんですが、Longest Proper Prefix which is Suffix (LPS) arrayをつくる前処理部分が何をやってるのか全然わからなくて、、、(笑)。日本語の解説だとテーブルって呼んでるのも見かけますが、LPSと同じものです。

　アルゴリズムそのものの解説はこの記事が非常にわかりやすいのでぜひ。

一週間で身につくアルゴリズムとデータ構造|応用編第2日目：文字列検索のアルゴリズム①(KMP法)

 　またLPS作成部分にピンとこない方は、次の記事にgifがあるので参考にすると良いと思います。

towardsdatascience.com

　LPSの部分を理解するコツはforによるiと、先頭付近の配列を記憶するprefixという2つのカーソルが別々で動いていることを認識することです。特にiは最初から最後まで動く一方、prefixは先頭付近でしか動きません。

　まずはLPSをつくる関数です。ぜひ、上記記事のgifをみながら確認してみてください。

const createLps= pattern => {
    const { length } = pattern;
    let lpsInit = new Array(length);
    let lps = lpsInit.fill(0);
    let prefix = 0; //パターンの開始点
    for (let i=1; i<length; i++) {
        // ②
        // 異なるものがでてきた場合は、前にさかのぼり
        // さかのぼって一致した地点でループを
        while (prefix>0 && pattern[prefix] !== pattern[i]){
            prefix = lps[prefix-1];
        }
        // ①
　　　　 // ifがないとprefix=0かつpattern[prefix] !== pattern[i]を取りこぼすので注意
        // prefixとiの要素が等しい場合はprefixを増やします。
        // prefixが増加している間は、先頭と同じパターンの配列が続いていることを意味します。
        if (pattern[prefix] == pattern[i]) {
           prefix++;            
           //このprefixをlpsに入れる
           lps[i] = prefix;
        }
    } 
    return lps;       
}


let str = "ACABACACD";
 
console.log(createLps(str))

>>>[
    0, 0, 1, 0, 1,
    2, 3, 2, 0
   ]

  　完成した配列の見方ですが、これは探索時に、その地点までパターンがマッチしていたときにどこまで戻すかを意味しています。ACABACACDというパターンを探すとすると、ACABACACDの赤の部分までパターンがマッチしていた場合は、Cのindex=5に該当するlps[5]=2まで戻るという意味になります。つまりpattarn[2]から比較を再開します。

 そして探索部分です。

const KMPSearch = (pattern, text) => {
    const P = pattern.length; 
    const T = text.length
    const lps = createLps(pattern)
    let patIdx = 0; 
    let txtIdx = 0;
    const matches = [];
    while (txtIdx < T) {
        if (pattern[patIdx] === text[txtIdx]) {
            txtIdx ++;
            patIdx ++;
        }
        //全部マッチした場合
        if (patIdx === P) {
            //マッチし始めたスタート地点をpush
            matches.push(txtIdx-patIdx);
            //次の比較開始地点へ飛ぶ
            patIdx = lps[patIdx-1];
        } 

        if (txtIdx < T && pattern[patIdx] !== text[txtIdx]) {
            if (patIdx !== 0) {
                //次の比較開始地点へ
                patIdx = lps[patIdx-1];
            } else {
                txtIdx++;
            }
        }
    }
    return matches;
}

txt = "ABABDABACDABABCABABDKGUSKAAABABCABAB"
pat = "ABABCABAB"
console.log(KMPSearch(pat, txt))

>>>[ 10, 27 ]

 　探索のコードはそんなに難しくないかなと思います。LPSを用いて、パターンの戻る位置を効率的にしていますね。

　時間計算量はLPS配列作成部分で\(O(k)\)(\(k\)=pattern.length)、探索部分では\(O(n)\)(\(n\)=text.length)\)となるので合わせて\(O(k+n)\)と考えられます。

　\(logn\)や\(n^2\)でなく線形時間で処理が終わるパターン検索はKMPアルゴリズムのみのようです。本体より前処理のLPSのほうが複雑なのがネックですが(笑)

　今日は以上です。

　では。