おうちでKMP法

posts/2020-04-25diary

文字列を検索するアルゴリズムにKMP法というものがある。名前とざっくりとしたアイディアしか知らなかったけど、ちょうど5分LTする予定があったのでいい機会だしちゃんと調べた。

コードはこんな感じ。

# ずらし表を作る
def table(pattern)
  i = 0
  j = 1
  memo = [0]
  while j < pattern.size
    if pattern[i] == pattern[j]
      memo[j] = memo[j - 1] + 1
      i += 1
      j += 1
    else
      memo[j] = 0
      i = 0
      j += 1
    end
  end

  memo
end

# text中にあるpatternの位置を返す
def search(text, pattern)
  i = 0
  j = 0
  memo = table(pattern)

  # 先頭に番兵を入れておく
  pattern = ' ' + pattern
  memo.unshift 0

  count = 0
  while j < pattern.size - 1 && i < text.size
    if text[i] == pattern[j + 1]
      # 一致する時はそれぞれのポインタを進める
      i += 1
      j += 1
    elsif j == 0
      # パターン文字列の先頭で不一致の場合は、テキスト文字列の次の文字へ進む
      i += 1
    else
      # パターン文字列の途中で不一致の場合は、ずらし表をみてパターン文字列のポインタを戻す
      j = memo[j]
    end
  end

  if j == pattern.size - 1
    return i - j
  end

  nil
end

text文字列の中にpattern文字列が出現する位置が知りたい、つまりtext.index(pattern)ということがしたいとき、

まずpattern文字列から「ずらし表」という参照用のテーブルを作る
- ずらし表はpattern文字列の先頭から順にみていったとき、prefixとその時点でのsuffixがいくつ一致するかをメモしたもの
- ざっくり言うと、pattern文字列にある重複する部分文字列の長さをメモしてる
textとpatternを先頭から1文字ずつ順に比較していき、不一致だった時に、次にpatternのどの文字から比較を再開するかをずらし表をみて決める
ずらし表をみることで、すでに一致すると分かりきってる部分文字列の無駄な比較をスキップできる
力まかせ法と違って、text文字列のインデックス(着目してる文字の位置)が後戻りすることはない

という感じで進んでいく。

スライドから抜粋すると、
力まかせ法（素朴な比較）だとこんな感じで brute-force

KMP法だとこんな感じ kmp

文字だけ見てもよくわからないと思うのでこの動画をオススメしたい。

9.1 Knuth-Morris-Pratt KMP String Matching Algorithm - YouTube

↑実際に動画でインデックスの動きを見てみるとよくわかる。はじめに載せてるコードはこの動画の説明を単純に書き下したもの。

個人的にはKMP法はこのあたりがポイントだと思った。

一致するとわかってるところをスキップさせる
pattern文字列中の重複する部分文字列に着目
力まかせ法と違って、KMP法ではtext, patternそれぞれにインデックス(現在の文字位置)を持たせる
textのインデックスを後戻りさせず、patternのインデックスを後戻りさせる

スライドにも書いてるけど、実用上は力まかせ法のほうが速いってのはおもしろい。理由を考えればそれはそうって感じだけど。

ということで次は理論的にもすごくて実用上も速いBM法をやります。