自分の勉強用備忘録を兼ねて自分なりの言葉で色々な文字列検索アルゴリズムについて紹介していこうと思います。
本記事では KMP法（Knuth–Morris–Pratt algorithm） について紹介します。
KMP法は文字列探索アルゴリズムの一種で、文字列 $S$ と文字列 $T$ について $T$ が $S$ に含まれているか否かを、また含まれている場合はその位置を $O(|S|+|T|)$ で求めることができます。
他の文字列検索アルゴリズムについてもまとめているので、よければご覧ください。
目次
1. KMP法のアイデア
2. アルゴリズム
3. コード
4. 計算量
5. 参考文献
KMP法のアイデア
まずはひとつずつ位置をずらして順番に一致するかを確かめるといった愚直な方法で文字列探索を行う流れを確認します。
$S = \text{“}aababacababc\text{”}$ と $T= \text{“}ababc\text{”}$ を例に取り、 $T$ が $S$ に含まれているかを考えます。
下記アニメーションは $T$ が $S$ に含まれているかを愚直に前から調べたときのアニメーションです。このようにして $S[7:12] = T$ より、 $T$ が $S$ に含まれているということが分かります。
このアニメーションのように愚直に調べると、ひとつの $i\left(0 \le i \le |S|-|T|\right)$ に対して $S[i:i+|T|]$ と $T$ が一致するかの確認で最悪 $|T|$ 回の比較が必要になり、合計で計算量は $O(|S||T|)$ となってしまいます。
ここで上記のアニメーションの $i=1$ における文字列比較に着目してみます。
$S[1:5] = T[0:4] = \text{“}abab\text{”}$ というように $T$ の4文字目までは一致していることが確認できます。 $S[2] = T[1] = \text{“}b\text{”}$ より、この段階で $S[2] \neq T[0] = \text{“}a\text{”}$ と分かるので、 $i=2$ については文字列の比較を行わずに飛ばしてしまって良いです。
また $S[3:5] = T[2:4] = T[0:2] = \text{“}ab\text{”}$ より、 $i=3$ における文字列比較において、先頭2つはすでに一致することが分かっているので、先頭から比較せずに $S[5:8]$ と $T[2:5]$ が一致するか否かを調べれば良いです。
同様に比較を飛ばせるところを全て飛ばして文字列探索を行うと以下のアニメーションのような流れになります。灰色は既に一致することが分かっているため比較を行わない部分を表しています。
愚直な方法では比較の回数は21回、こちらのアニメーションの手法では16回となっており、愚直な手法よりも少ない比較の回数で文字列探索を行えていることが確認できます。
このように比較が不要なところを全て飛ばして文字列探索を行うというのがKMP法のアイデアとなります。
アルゴリズム
KMP法では検索パターンである文字列 $T$ について 部分マッチテーブルという配列を生成し、それを元に比較を飛ばせるところを飛ばすという流れで文字列探索を行います。
部分マッチテーブル $A$ とは $1 \le i \lt |T|$ に対して $T[0:i]$ の真の接頭辞（proper prefix）と接尾辞（suffix）が最大で先頭から何文字一致するかという値を持つ配列です。
なお proper prefix とはその文字列自身を含まない prefix のことです。例えば $\text{“}abc\text{”}$ の proper prefix は $\text{“}\text{”}, \text{“}a\text{”}, \text{“}ab\text{”}$ となります。 $\text{“}abc\text{”}$ は含まれないことに注意してください。単純に $A[i] \lt i$ が成り立つと考えれば大丈夫です。
また便宜上 $i=0$ については $A[0] = -1$ と定めます。
例えば $T= \text{“}ababc\text{”}$ の場合、 $T[0:i]$ の値がそれぞれ $\text{“}\text{”}, \text{“}a\text{”}, \text{“}ab\text{”}, \text{“}aba\text{”}, \text{“}abab\text{”}$ であることから、部分マッチテーブル $A$ は $$A = [-1,0,0,1,2]$$ となります。
まずは、この部分マッチテーブル $A$ を使ってどのように文字列探索を実現するかについて考えてみます。
部分マッチテーブルを用いた文字列探索
文字列 $S,T$ について $T$ が $S$ に含まれているかを前方から確認しているとして、 $i,j\left(0 \le i \le |S| - |T|, 1 \le j \lt |T|\right)$ において $S[i:i+j] = T[0:j]$ は成り立つが、 $S[i+j] \ne T[j]$ となってしまったとします。
このとき、 $k\left(i \lt k \lt i+j-A[j]\right)$ について $S[k:i+j]$ は $S[i:i+j]$ の部分文字列であるため $S[i:i+j] = T[0:j]$ より、 $$S[k:i+j] = T[k-i:j]$$ が成り立つはずです。
ここで $S[k:k+|T|] = T$ となって文字列探索が終了すると仮定すると、$i+j \lt k+|T|$ より、部分文字列について、 $$S[k:i+j] = T[0:i+j-k]$$ が成り立ちます。よって、 $$T[0:i+j-k] = T[k-i:j]$$ となるのですが、$i+j-k \gt j \gt A[j]$ より、 $T[0:j]$ の proper prefix と suffix が先頭から最大で $A[j]$ だけ一致するということに矛盾します。
そのため、 $k\left(i \lt k \lt i+j-A[j]\right)$ については常に $S[k:k+|T|] \ne T$ が成り立つため、 $i := i+j-A[j]$ と更新して一部の文字列比較を飛ばすことができます。
また部分マッチテーブル $A$ の定義より、 $T[0:j]$ の proper prefix と suffix は先頭から最大で長さ $A[j]$ だけ一致するはずなので、 $$T[0:A[j]] = T[j-A[j]:j]$$ が成り立ちます。
さらに $S[i:i+j] = T[0:j]$ より部分文字列について $$S[i+j-A[j]:i+j] = T[j-A[j]:j]$$ も成り立つはずです。これらのことから $$S[i+j-A[j]:i+j] = T[0:A[j]]$$ が成り立ちます。
よって $i := i+j-A[j]$ と更新して $S[i:i+|T|]$ と $T$ が一致するかを確認する際に、先頭 $A[j]$ 文字は既に一致することは分かっているため比較を飛ばしてしまって良いです。
このようにして部分マッチテーブル $A$ を用いて文字列探索を行うことができます。なお、 $1 \le j \lt |T|$ において $S[i+j] \ne T[j]$ となってしまったときと仮定しましたが、 $j = 0$ で $S[i+j] \ne T[j]$ となってしまった場合は、文字列探索を飛ばすことができず、 $i:=i+1$ と更新して、 $S[i:i+|T|]$ と $T$ を先頭から比較する必要があるのですが、 $A[0] = -1$ と定めたことから $i$ については $1 \le j \lt |T|$ のときと同様に $i := i+j-A[j] = i+1$ と更新することができます。
まとめると以下のような手順になります。
- 部分マッチテーブル $A$ を求める
- $i = j = 0$ に初期化
- $i+j \lt |S|$ の間ステップ3a.3b.を繰り返す
3a. $S[i+j] = T[j]$ であれば、 $j := j+1$ と更新して、 $S[i:i+|T|]$ と $T$ の文字列比較を続行する、この際 $j = |T|$ となれば、 $S[i:i+|T|] = T$ であるため、 $i$ を返して終了
3b. $S[i+j] \ne T[j]$ であれば、 $S[i:i+|T|] \ne T$ であるため、 $i := i+j-A[j]$ と更新して次の文字列比較に進む、また $j \gt 0$ であれば、 $j := A[j]$ と更新して先頭の不要な文字列比較を飛ばす - ステップ3.を繰り返して $S[i:i+|T|] = T$ となる $i$ が見つからなければ $T$ は $S$ に含まれないため、 $-1$ を返して終了
では続いてどのようにして部分マッチテーブル $A$ を求めるかについて考えていきます。
部分マッチテーブルの構築
前から値を計算していて、既に $A[i]$ は分かっているものとします。 $A[i]$ の定義から $$T[0:A[i]] = T[i-A[i]:i]$$ が成り立ちます。ここで $T[i] = T[A[i]]$ であるとすると、 $$T[0:A[i]+1] = T[i-A[i]:i+1]$$ が成り立つため、 $A[i+1] = A[i]+1$ と簡単に求めることができます。
そうでない場合、つまり $T[i] \ne T[A[i]]$ となっているときについて考えます。
$A[i]$ の定義より、以下が成り立ちます。 $$T[0:A[i+1]] = T[i+1-A[i+1]:i+1]$$ ここで、 $A[i+1] := j+1 \left(j \lt i\right)$ と置くと以下のように変形できます。
T[0:j+1] = T[i-j:i+1] \\ \Longleftrightarrow T[0:j] = T[i-j:i] \land T[j] = T[i]
$T[0:j] = T[i-j:i]$ の部分に着目してみると、部分マッチテーブル $A[i]$ がこのような $j$ の最大値であるため、 $j \le A[i]$ であると分かります。
また、 $T[j] = T[i]$ の部分に着目すると、 $T[i] \ne T[A[i]]$ と仮定を置いていることから、 $j \ne A[i]$ であると分かります。
ここで $A[i]$ の定義より、 $T[0:A[i]] = T[i-A[i]:i]$ が成り立つはずです。 $j \le A[i]$ より、部分文字列について、 $$T[A[i]-j:A[i]] = T[i-j:i]$$ が言えます。これにより、 $T[0:j] = T[i-j:i] \land T[j] = T[i]$ は、 $$T[0:j] = T[A[i]-j:A[i]] \land T[j] = T[i]$$ と言い換えられます。
$j \le A[i]$ 、また、 $j \ne A[i]$ であったため、 $j \lt A[i]$ が成り立ちます。よって、 $T[0:j] = T[A[i]-j:A[i]]$ は $T[:A[i]]$ の proper prefix と suffix が先頭から長さ $j$ だけ一致することを示しているため、部分マッチテーブル $A[i]$ の定義より、 $j \le A[A[i]]$ が成り立ちます。
よって $j = A[A[i]]$ と置いて、 $T[j] = T[A[A[i]] = T[i]$ が成り立てば、 $A[i+1] = j+1 = A[A[i]]+1$ と求めることができます。
もし $T[A[A[i]] \ne T[i]$ であれば、同様にして $j \lt A[A[i]]$ から $j \le A[A[A[i]]]$ を導けるため、 $T[A[A[A[i]]] = T[i]$ を検証すればよいです。それ以降も同様です。 $j = A[A[...[i]...]]=-1$ となってしまったときはこれ以上続けることができないので、終了する必要がある点に注意してください。なおこの場合は $A[i+1] = 0$ なので、 $A[i+1] = j+1 = A[A[...[i]...]]+1 = -1+1 = 0$ と同じように代入できます。
まとめると以下のような手順になります。
- $j=-1,A=[-1,0,0,...,0]$ で初期化（$|A|=|T|$）
- $i=0$ から始め、 $i$ を $1$ ずつ増やし $i \lt |T|-1$ の範囲でステップ3.4.を繰り返す
- $j \ge 0$ かつ $T[i] \ne T[j]$ の間、 $j := A[j]$ と更新
- $A[i+1] = j+1$ を代入し、 $j := j+1 \left(=A[i+1]\right)$ と更新
コード
def create_partial_match_table(t):
table = [0]*len(t)
table[0] = -1
j = -1
for i in range(len(t)-1):
while j >= 0 and t[i] != t[j]:
j = table[j]
table[i+1] = j+1
j += 1
return table
def kmp_search(s,t):
table = create_partial_match_table(t)
i = j = 0
while i+j < len(s):
if s[i+j] == t[j]:
j += 1
if j == len(t):
return i
else:
i = i+j-table[j]
if j > 0:
j = table[j]
return -1
計算量
部分マッチテーブルを用いた文字列探索の計算量
まず部分マッチテーブルを利用した文字列探索の計算量について考えていきます。
while ループに着目すると、内部の処理自体は $O(1)$ なのでループの繰り返し回数の最大数が分かればよさそうです。
while ループの内部の処理において $S[i+j] = T[j]$ （前節のステップ3a.）であれば、 $j := j+1$ に更新され、そうでない場合（前節のステップ3b.）は、 $i := i+j-A[j]$ に更新されます。
ここで、部分マッチテーブルの定義から $A[j] \lt j$ であったため、 $i \lt i+j-A[j]$ が成り立ちます。
よってステップ3a.ならば $i+j$ が $1$ だけ増加し、ステップ3b.ならば $i$ が $j-A[j]$ だけ増加しているため、 while ループの内部の処理後において、 $i$ と $i+j$ の少なくとも一方はかならず処理前よりも大きくなるということが言えます。
while ループの繰り返しの条件は $i+j \lt |S|$ となっています。また $j \ge 0$ より、ループ中に $i \ge |S|$ となっても $i+j \ge i \ge |S|$ なのでループは終了します。
以上のことから、ループの内部の処理前後で $i$ と $i+j$ が常に片方だけ $1$ ずつ増加するとしても、どちらも $|S|$ が最大値であるため、 $2|S|$ 回繰り返しを行ったタイミングで while ループは終了します。
よって部分マッチテーブルを利用した文字列探索の計算量は $O(|S|)$ となります。
部分マッチテーブルの構築の計算量
次に部分マッチテーブルの構築の計算量について考えていきます。
これは for ループと while ループの二重ループに関して、内側の while ループの繰り返し回数が全体を通して最大でどれくらいかが分かれば良さそうです。
while ループにおける $j := A[j]$ の更新について $A[j] < j$ より、この更新を行う度に $j$ は減少していきます。
このことから 外側の for ループの $j := j+1$ の更新回数と内側の while ループにおける $j := A[j]$ の更新回数を比較すると、必ず後者の方が小さくなっているということが言えます。
なぜなら $j := A[j]$ の更新を行うためには $j$ を増加させていく必要があるのですが、 $j := j+1$ の更新では $1$ ずつしか増えないため、 $j := A[j]$ を $k$ 回行いたい場合は、事前に $j := j+1$ も $k$ 回以上は行っておく必要があるからです。
よって while ループの繰り返し回数は for ループの繰り返し回数未満であるため、最大でも $|T|$ 回程度しか行われません。よって部分マッチテーブルの構築の計算量は $O(|T|)$ となります。
以上のことから全体を通して計算量は $O(|S|+|T|)$ となります。
参考文献