KMPアルゴリズムの精解とPython版のコード例
KMPアルゴリズムは古典的な文字列整合アルゴリズムであり、文字列Sからモード文字列Mを検索する問題を解決する。アルゴリズム名は、発明者Knuth、Morris、Pratに由来する。
文字列SからM，Sの長さls，Mの長さlmを検索し（ls＞lm）とする。
シンプルな文字列の検索方法
文字列Sの最初の文字からMとの比較を開始し、もし一致が失敗したら。次の文字から、再比較します。第(ls-lm)文字の指導を行います。
この方法は考えやすく、理解しやすく、効率が高くない。
問題は毎回マッチングが失敗した後、移動の歩調が1に固定されていますが、もっと大きく歩けるということです。
KMPの文字列の検索方法
パターンストリングの連続する文字列M［0，i］およびi＜lmは、文字列Sとのマッチングに成功したと仮定する。あいにくi＋1文字目が失敗しました。どうすればいいですか？文字を移動して、もう一度来ますか？もちろんよくないです。それは素朴なコースです。転んだところから歩き続けてもいいですか？
文字列M[0-i]がマッチした以上、この文字列から文章を作ります。くりを一つあげる
S番号
j
j+1
j+2
j+3
j+4
j+5
j+6
j+7
です。
S列
a.
b
c
a.
b
c
d
e
です。
M串
a.
b
c
a.
b
d
M番号
0
1
2
3
4
5
このとき、M列の5番目の文字にマッチできませんでした。最初の4文字がマッチしました。
転倒したところから出発すると、M[0,4]のサブシリアルM[0,k]==S[j+4-k，j+4]が必要です。
M[0,4]==S[j， j+4は文字列S[j+4-k，j+4]==M[4-k，4]があります。以上、M[0,k]==M[4-k，4]があります。
このようなkが存在しないなら、素直で素朴です。
上の表からは、次のマッチはM列をj＋3位置に移動するだけで、j＋5からマッチングすればいいと直感的に見られます。すでにマッチングした文字列M[0,4]の中で一番長いサブストリング(M[0,1]==M[3,4]があることが分かりやすいです。これが問題の鍵です。
したがって、KMPのコア部分は、各サブストリングのkを計算することである。
実例
まず文字列のシンプルなマッチングを見てみます。
文字列sを固定して、パターン列pはsの一番左から揃え始めます。配置部分が完全に同じであれば、マッチングに成功します。失敗したら、パターン列p全体を右に1桁移動して、配置部分を引き続きチェックします。このように繰り返します。
実際には、パターンストリップpを前処理して、前のサフィックスの部分マッチングテーブルを得て、私達は既知の情報を利用して、右のシフトができるビット数を算出することができます。つまり、kmp=シンプルなマッチング+移動ビットです。
もっと細かいところは阮一峰の文章を見てください。ここでは展開しません。
pythonのコードを以下に示します。
文字列SからM，Sの長さls，Mの長さlmを検索し（ls＞lm）とする。
シンプルな文字列の検索方法
文字列Sの最初の文字からMとの比較を開始し、もし一致が失敗したら。次の文字から、再比較します。第(ls-lm)文字の指導を行います。
この方法は考えやすく、理解しやすく、効率が高くない。
問題は毎回マッチングが失敗した後、移動の歩調が1に固定されていますが、もっと大きく歩けるということです。
KMPの文字列の検索方法
パターンストリングの連続する文字列M［0，i］およびi＜lmは、文字列Sとのマッチングに成功したと仮定する。あいにくi＋1文字目が失敗しました。どうすればいいですか？文字を移動して、もう一度来ますか？もちろんよくないです。それは素朴なコースです。転んだところから歩き続けてもいいですか？
文字列M[0-i]がマッチした以上、この文字列から文章を作ります。くりを一つあげる
S番号
j
j+1
j+2
j+3
j+4
j+5
j+6
j+7
です。
S列
a.
b
c
a.
b
c
d
e
です。
M串
a.
b
c
a.
b
d
M番号
0
1
2
3
4
5
このとき、M列の5番目の文字にマッチできませんでした。最初の4文字がマッチしました。
転倒したところから出発すると、M[0,4]のサブシリアルM[0,k]==S[j+4-k，j+4]が必要です。
M[0,4]==S[j， j+4は文字列S[j+4-k，j+4]==M[4-k，4]があります。以上、M[0,k]==M[4-k，4]があります。
このようなkが存在しないなら、素直で素朴です。
上の表からは、次のマッチはM列をj＋3位置に移動するだけで、j＋5からマッチングすればいいと直感的に見られます。すでにマッチングした文字列M[0,4]の中で一番長いサブストリング(M[0,1]==M[3,4]があることが分かりやすいです。これが問題の鍵です。
したがって、KMPのコア部分は、各サブストリングのkを計算することである。
実例
まず文字列のシンプルなマッチングを見てみます。
文字列sを固定して、パターン列pはsの一番左から揃え始めます。配置部分が完全に同じであれば、マッチングに成功します。失敗したら、パターン列p全体を右に1桁移動して、配置部分を引き続きチェックします。このように繰り返します。
#
def naive_match(s, p):
m = len(s); n = len(p)
for i in range(m-n+1):# i
if s[i:i+n] == p:
return True
return False
実際には、パターンストリップpを前処理して、前のサフィックスの部分マッチングテーブルを得て、私達は既知の情報を利用して、右のシフトができるビット数を算出することができます。つまり、kmp=シンプルなマッチング+移動ビットです。
もっと細かいところは阮一峰の文章を見てください。ここでは展開しません。
pythonのコードを以下に示します。
#KMP
def kmp_match(s, p):
m = len(s); n = len(p)
cur = 0# cur
table = partial_table(p)
while cur<=m-n:
for i in range(n):
if s[i+cur]!=p[i]:
cur += max(i - table[i-1], 1)# , 1 1 ,
break
else:
return True
return False
#
def partial_table(p):
'''''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'''
prefix = set()
postfix = set()
ret = [0]
for i in range(1,len(p)):
prefix.add(p[:i])
postfix = {p[j:i+1] for j in range(1,i+1)}
ret.append(len((prefix&postfix or {''}).pop()))
return ret
print naive_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD")
print partial_table("ABCDABD")
print kmp_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD")