【アルゴリズム】文字列照合問題 KMP法とは

今回は、文字列照合問題におけるKMP法を書き溜め、
新しく計算機科学を学ぶ人のためのマイルストーンを残していく。

KMP法

テーブルを用いテキストを後戻りしないで照合をする

KMP方とは文字列検索アルゴリズムの一種で、
Donald KnuthとVaughan Pratt、J.H.Morris が発明し3人共同で発表したものである。

テキスト（文字列）Sから単語Wを探すにあたり、不一致となった位置と単語自身の情報から次に照合を試すべき位置を決定することで検索を効率化するアルゴリズムである。(Wikipediaより)

過去、素朴な文字列照合について書き溜めたが、
照合に失敗した際に後戻りする点で効率が悪いと書いた。

素朴な文字列照合アルゴリズムにおいて，照合に失敗した際に
添字を（一文字分だけでなく）もっとずらすことができれば文字の比較を減らすことができるのではないか？
という視点がKMP方では存在するため、素朴な文字列照合アルゴリズムより基本的に効率が良い。

KMP法の基本的な考え方

KMP法は大きく２つの段階がある。
「前処理」と「本処理」である。

前処理: 不一致時にずらすパターンの文字数を計算しテーブル(パターン照合テーブル)に格納する
本処理: テーブルを活用し、テキストを後戻りしないで照合を進める

パターン照合テーブルの作り方

パターン照合テーブルとは、
テキスト中の文字と照合元の文字の照合に失敗したときに、
照合文字の参照位置をいくつ戻せばよいのかを格納したテーブル(配列)のことである。

パターン照合テーブルは下記の要領でつくれる。
文字列を複数の部分文字列にわけ比較していく。

def main():
  W="tested"
  S = "testingmytested"
  T = []
  T.insert(0, -1)
  j = 1
  while 1 &lt;= j and j &lt;= len(W)-1:
    k = j-1
    while W[0:k-1] != W[j-k:j-1] and k &gt; 0:
      k = k-1
    T.insert(j, k)
    j = j+1
  return T

def main():

W="tested"

S = "testingmytested"

T = []

T.insert(0, -1)

j = 1

while 1 <= j and j <= len(W)-1:

k = j-1

while W[0:k-1] != W[j-k:j-1] and k > 0:

k = k-1

T.insert(j, k)

j = j+1

return T

パターン照合テーブルを活用した照合

先程作成したパターン照合テーブルを活用し照合を行っていく。
ポイントとしては、
照合に失敗した位置(=i)より左の部分が
一致しているような最初の（最も左の）位置にiを移動させることである。

def main():
  W="tested"
  S = "testingmytested"
  T = []
  T.insert(0, -1)
  j = 1
  while 1 <= j and j <= len(W)-1:
    k = j-1
    while W[0:k-1] != W[j-k:j-1] and k > 0:
      k = k-1
    T.insert(j, k)
    j = j+1
  i = 0
  j = 0
  while i+j < len(S):
    if W[j] == S[i+j]:
      j+=1
      if j == len(W):
        return i
    else:
      i = i+j-T[j]
      if j>0:
        j = T[j]
  retrun 0

def main():

W="tested"

S = "testingmytested"

T = []

T.insert(0, -1)

j = 1

while 1 <= j and j <= len(W)-1:

k = j-1

while W[0:k-1] != W[j-k:j-1] and k > 0:

k = k-1

T.insert(j, k)

j = j+1

i = 0

j = 0

while i+j < len(S):

if W[j] == S[i+j]:

j+=1

if j == len(W):

return i

else:

i = i+j-T[j]

if j>0:

j = T[j]

retrun 0

文字列照合アルゴリズム KMP法を説明してください。

さて、先程の説明を読んだ人は、KMP法を説明できますね。
素朴な文字列照合との違いは？計算量は？大丈夫でしょうか。

ノートやメモに書くでも、Twitterに呟くでもYoutubeにアップロードするでも構いません。
今日知った情報をアウトプットしてみましょう。

正直文字列照合がうまく説明できていない気がする。
なので、詳しくは、参考をどうぞ。

資料1
資料2
wiki

じゃあね〜〜〜。