パターン部分一致の文字列検索 (KMP法)

# はじめに

<a href="https://gw-advent.9wick.com/calendars/21">ただの集団 AdventCalendar PtW.2019</a> 9日目の記事です. Merry Golden week 🔔🌲
8日目は pino さんの <a href="https://qiita.com/wakafar/items/c9a05713f579f436d36d">多分わかりやすいBi-LSTM-CRF入門</a> でした.


最近 <b>retrieval</b> という単語に出会うことがよくあります. retrieval は 探索、検索 という意味を持つ単語で、過去の記事で少し触れたトライ木(Trie)も、この re<b>trie</b>val を語源としているようです. 

今回は、身近な例である文字列検索について、少し触れてみたいと思います.
結論から言うと、タイトルの通りの話を予定しているので、古いながらも(1977年)有名な部分マッチテーブルアルゴリズムの復習になります.


# ゴール
次のようなクイズがあります. 探したい単語の<b>パターン</b>を意識して、全文照合方式で考えていくこと.
<i>
長さ N の文字列と、長さ k のパターンが与えられます.
文字列の中のパターンを、最悪の場合でも O(N * k)より短い探索時間で見つけてみましょう. 
パターンが見つかったら、始まりのインデックスを返します. なかったら -1 を返します.
</i>
### ほしい結果 (test)
```.py
def test_kmp_search(self):
    text = "ABABABABC"
    word = "ABABC"

    expected = 4  # text[4] から word が始まる
    actual = kmp_search(text, word)

    self.assertEqual(expected, actual)

def test_kmp_search_same_prefix_suffix(self):
    text = "ababbabcababababcabaabbb"
    word = "abababcaba"

    expected = 10
    actual = kmp_search(text, word)

    self.assertEqual(expected, actual)
```

# シンキングタイム

- <b>Input : </b> 長さ N の文字列と、長さ k のパターンです.
- <b>Output : </b> バターンが始まるインデックスです(なかったら -1).

<b>パターン</b>というのがキーワードになりそうですね. ですが、現時点では浮かぶアイデアがありません.

仕方ないので、まずは紙とペンを用意して探索を始めます.
文字列は `ABABABABC` パターンは `ABABC` です.

```
ABABABABC
ABABC
```

ABABまで一致したものの<b>C</b>が違いますね ｻﾞﾝﾈﾝ 😇

```
ABABABABC
 A
```

最初からあってませんね. 飛ばしましょうか.

```
ABABABABC
  ABABC
```

ABAB までは一致しているけど、<b>C</b>が違いますね
(先ほどもこのｻﾞﾝﾈﾝなパターンがあった気が🤔)

この探索は、飽きました. ひと文字あたり、パターンの長さ k の比較が発生して、文字数は N です. `O(N * k)`な世界が目に浮かびます. 

Input の文字列が `ACTTCCAAGGGAAGATGAAGGGC...` などの長い文字列になると、なおさら疲れそうです.

# 後戻りせずに、不要な探索はスキップしたい

一個一個比べて、一致しなかったらやり直し...いい加減パターンを<b>覚えて</b>おきたいです.

「パターンのなかで、ここまで一致していれば、ここまでスキップできる」という情報があれば「次はここから探索を再開すればよい」ということができます.

一文字ずつ見ていく探索そのもののやりかたは既存の brute force と大きく変わりません. 
ただ、一致しなかった場合、1文字あたり最大 k 回(パターンの長さ)存在していた「後戻り」をせずに、探索を再開することが可能なため、無駄(重複)な探索を減らせそうです.

重複して探索しうるサブパターン(パターンの内部でパターン化できるもの)を覚えて、再利用します. つまり、探索中に不一致が出た場合、パターンを先頭から見ずに、何文字(インデックス)スキップできるかを記録していこうと思います.

Knuth-Morris-Pratt アルゴリズム(KMP法)は、このような考えを背景としています.

## やりたいこと

ホップ

```
ABABABABC # index 4 で一致しない
ABABC
```

ステップ

```
ABABABABC # index 4 から再開, index 6 で一致しない
  __ABC   # ひとつ前の探索で一致していた部分(AB の2文字)は見ない
```

ジャンプ

```
ABABABABC # index 6 から再開
    __ABC # ひとつ前の探索で一致していた部分(AB の2文字)は見ない
```

見つけた 👀

# Partial match table (部分一致テーブル)

`パターンの中のサブパターン`と`スキップできる文字数`を意識して、
`スキップできる文字数`を1次元配列として部分マッチテーブルを作成したいと思います.

さきほどの検索対象のパターンは`ABABC`です. 例として以下に着目します.

- `ABAB`に`AB`が重複して構成されている点
- `ABA`に`A`が重複している点

先頭の`A`からスタートして、右に進めてパターンの部分を見ていきます.

#### パターン`A`<br>
`A`という一文字だけです.
そもそも一文字のみなので、スキップの意味はなさそうです(つまり0).

パターンが先頭の時点で不一致したら、パターンの先頭から探索を再開する必要があります.

#### パターン`AB`<br>
`A`で始まり`B`で終わるパターンです. 
区切れそうなサブパターンが見つからないため、スキップするのはできないでしょう(つまり0). 

#### パターン`ABA`<br>
`A`で始まり`A`で終わるパターンです. サブパターンとして`A`があると言えます.
`A`の長さの分だけ(つまり1)スキップして探索を再開しても良さそうです.

#### パターン`ABAB`<br>
`AB`で始まり`AB`で終わるパターンです.
`AB`の長さの分だけ(つまり2)スキップして探索を再開しても良さそうです.

#### パターン`ABABC`<br>
`A`で始まり`C`で終わるパターンです.
区切れそうなサブパターンが見つからないため、ここでスキップするのはできないでしょう(つまり0). 

先頭文字からはじまる全パターンを見ることができました.

上から順番にスキップするインデックスを記録したとすると、`[0, 0, 1, 2, 0]`といった配列が求められます.

## python code

```.py
def partial_match_table(word):
    table = [0] * (len(word) + 1)
    table[0] = -1
    i, j = 0, 1

    while j < len(word):
        matched = word[i] == word[j]

        if not matched and i > 0:
            i = table[i]
        else:
            if matched:
                i += 1
            j += 1
            table[j] = i

    return table
```
この実装では`[-1, 0, 0, 1, 2, 0]`が得られます.
`j`が 1 から操作を始めるため、便宜上、長さを +1 とってあります. `table[0]`に意味はないので`-1`を入れました.

上記の例のパターンだと、`table[1]`が、パターン`A` 
>そもそも一文字のみなので、スキップの意味はなさそうです(つまり0) ...

に該当します.

#### `j`を1から始める理由
どれくらいスキップできるか (パターン内の重複した文字の並び) を知るために、パターンとパターン自身を比較する方法があります.
パターンとパターン自身を比較するために、二つを重ねてみます.

```
[A]BABC
[X]BABC
```

実際の探索で、そもそもパターンが1文字目から一致しない場合、2文字以上のスキップができないので、

```
[A]BABC
_[B]ABC

[A]BABC
_B[A]BC

A[B]ABC
_BA[B]C
```

2文字目から比較を始めるためです. `table[1]`は初期値の0である理由ともつながりました.

#### サブパターン一致判断の流れ (一部)

```.py
pattern[0] == pattern[1]
```

`AB`
一致する prefix と suffix なし.

```.py
pattern[0] == pattern[2]
```

`ABA`
prefix A と suffix A が一致.

```.py
pattern[1] == pattern[3]
```

`ABAB`
prefix B と suffix B が一致.
pattern[0] の A と pattern[2] の A はすでに一致していることがわかっている.
そのため AB と AB が一致しているとも言える.

### test
```.py
def test_partial_match_table(self):
    pattern = "ABABC"

    expected = [-1, 0, 0, 1, 2, 0]
    actual = partial_match_table(pattern)

    self.assertEqual(expected, actual)

def test_partial_match_table_same_prefix_suffix(self):
    pattern = "abababcaba"

    expected = [-1, 0, 0, 1, 2, 3, 4, 0, 1, 2, 3]
    actual = partial_match_table(pattern)

    self.assertEqual(expected, actual)
```

# 作成したテーブルを用いて探索
文章の中を探索して、不一致の場合、文章の中のカーソルを戻さず探索を続けます.
準備した部分マッチテーブルを活用します.

## python code

```.py
def kmp_search(text, word):
    table = partial_match_table(word)
    i, p = 0, 0

    while i < len(text) and p < len(word):
        if text[i] == word[p]:
            i += 1
            p += 1
        elif p == 0:
            i += 1
        else:
            p = table[p]

    return (-1, i - p)[p == len(word)]
```

文章(text)をなぞるカーソル`i`は、左から右へ進む間に、パターン(word)をなぞるカーソル`p`が再開を始める位置を決めます.
`i`と`p`がそれぞれ文章と単語の末尾インデックスに到達する間に、三つの分岐を行います.

- 文字が一致する場合 (両カーソルを右に進める)
- 文字が一致せず、スキップできない場合 (文章内カーソルを右に進める. パターンは先頭文字から照合を再開する)
- 文字が一致せず、スキップできる場合 (照合を再開するパターン内文字の位置をテーブルから取得する)

どちらかのカーソルが末尾に到達したら、
パターンの最後まで探索ができた `p == len(word)` 場合のみ、その距離をリターンします.

文章の中の文字を一度見たら、またそこに戻ることはありません.
文章の長さを N とおくと、この関数は`O(N)`の探索時間で動いていると言えます.


# おわりまして
文字列探索を線形時間で行えたアルゴリズムは KMP 法が初だそうです.
ただ、すべての工程 `部分マッチテーブル作成 + 検索` を合わせると、厳密には `O(k + N)`です. 
部分マッチテーブル作成 といった前処理の複雑性をも考慮すると、実用的な線形探索とは言い難いでしょう. 複雑な気分.

でもやはり、サブパターンを見つけてスキップ数を記録するやり方そのものが、面白いと思います. 


以上