はじめに
ただの集団 AdventCalendar PtW.2019 9日目の記事です. Merry Golden week 🔔🌲
8日目は pino さんの 多分わかりやすいBi-LSTM-CRF入門 でした.
最近 retrieval という単語に出会うことがよくあります. retrieval は 探索、検索 という意味を持つ単語で、過去の記事で少し触れたトライ木(Trie)も、この retrieval を語源としているようです.
今回は、身近な例である文字列検索について、少し触れてみたいと思います.
結論から言うと、タイトルの通りの話を予定しているので、古いながらも(1977年)有名な部分マッチテーブルアルゴリズムの復習になります.
ゴール
次のようなクイズがあります. 探したい単語のパターンを意識して、全文照合方式で考えていくこと.
長さ N の文字列と、長さ k のパターンが与えられます.
文字列の中のパターンを、最悪の場合でも O(N * k)より短い探索時間で見つけてみましょう.
パターンが見つかったら、始まりのインデックスを返します. なかったら -1 を返します.
ほしい結果 (test)
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)
シンキングタイム
- Input : 長さ N の文字列と、長さ k のパターンです.
- Output : バターンが始まるインデックスです(なかったら -1).
パターンというのがキーワードになりそうですね. ですが、現時点では浮かぶアイデアがありません.
仕方ないので、まずは紙とペンを用意して探索を始めます.
文字列は ABABABABC
パターンは ABABC
です.
ABABABABC
ABABC
ABABまで一致したもののCが違いますね ザンネン 😇
ABABABABC
A
最初からあってませんね. 飛ばしましょうか.
ABABABABC
ABABC
ABAB までは一致しているけど、Cが違いますね
(先ほどもこのザンネンなパターンがあった気が🤔)
この探索は、飽きました. ひと文字あたり、パターンの長さ k の比較が発生して、文字数は N です. O(N * k)
な世界が目に浮かびます.
Input の文字列が ACTTCCAAGGGAAGATGAAGGGC...
などの長い文字列になると、なおさら疲れそうです.
後戻りせずに、不要な探索はスキップしたい
一個一個比べて、一致しなかったらやり直し...いい加減パターンを覚えておきたいです.
「パターンのなかで、ここまで一致していれば、ここまでスキップできる」という情報があれば「次はここから探索を再開すればよい」ということができます.
一文字ずつ見ていく探索そのもののやりかたは既存の 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
A
という一文字だけです.
そもそも一文字のみなので、スキップの意味はなさそうです(つまり0).
パターンが先頭の時点で不一致したら、パターンの先頭から探索を再開する必要があります.
パターンAB
A
で始まりB
で終わるパターンです.
区切れそうなサブパターンが見つからないため、スキップするのはできないでしょう(つまり0).
パターンABA
A
で始まりA
で終わるパターンです. サブパターンとしてA
があると言えます.
A
の長さの分だけ(つまり1)スキップして探索を再開しても良さそうです.
パターンABAB
AB
で始まりAB
で終わるパターンです.
AB
の長さの分だけ(つまり2)スキップして探索を再開しても良さそうです.
パターンABABC
A
で始まりC
で終わるパターンです.
区切れそうなサブパターンが見つからないため、ここでスキップするのはできないでしょう(つまり0).
先頭文字からはじまる全パターンを見ることができました.
上から順番にスキップするインデックスを記録したとすると、[0, 0, 1, 2, 0]
といった配列が求められます.
python code
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である理由ともつながりました.
サブパターン一致判断の流れ (一部)
pattern[0] == pattern[1]
AB
一致する prefix と suffix なし.
pattern[0] == pattern[2]
ABA
prefix A と suffix A が一致.
pattern[1] == pattern[3]
ABAB
prefix B と suffix B が一致.
pattern[0] の A と pattern[2] の A はすでに一致していることがわかっている.
そのため AB と AB が一致しているとも言える.
test
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
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)
です.
部分マッチテーブル作成 といった前処理の複雑性をも考慮すると、実用的な線形探索とは言い難いでしょう. 複雑な気分.
でもやはり、サブパターンを見つけてスキップ数を記録するやり方そのものが、面白いと思います.
以上